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 d177af2..0922cd2 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
@@ -103,10 +103,9 @@
   }
 
   private DexType vivifiedTypeFor(DexType type) {
-    // doubleDollarTypes are fake types to work around rewriting.
     DexType vivifiedType =
         factory.createType(DescriptorUtils.javaTypeToDescriptor(VIVIFIED_PREFIX + type.toString()));
-    appView.rewritePrefix.addPrefix(vivifiedType.toString(), type.toString());
+    appView.rewritePrefix.rewriteType(vivifiedType, type);
     return vivifiedType;
   }
 
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 320935f..db8f582 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
@@ -156,12 +156,15 @@
   }
 
   private void addRewritePrefix(DexType interfaceType, String rewrittenType) {
-    appView.rewritePrefix.addPrefix(
-        getCompanionClassType(interfaceType).toString(),
-        rewrittenType + COMPANION_CLASS_NAME_SUFFIX);
-    appView.rewritePrefix.addPrefix(
-        getEmulateLibraryInterfaceClassType(interfaceType, factory).toString(),
-        rewrittenType + EMULATE_LIBRARY_CLASS_NAME_SUFFIX);
+    appView.rewritePrefix.rewriteType(
+        getCompanionClassType(interfaceType),
+        factory.createType(
+            DescriptorUtils.javaTypeToDescriptor(rewrittenType + COMPANION_CLASS_NAME_SUFFIX)));
+    appView.rewritePrefix.rewriteType(
+        getEmulateLibraryInterfaceClassType(interfaceType, factory),
+        factory.createType(
+            DescriptorUtils.javaTypeToDescriptor(
+                rewrittenType + EMULATE_LIBRARY_CLASS_NAME_SUFFIX)));
   }
 
   boolean isEmulatedInterface(DexType itf) {
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 65eb486..454085b 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
@@ -30,6 +30,7 @@
 import com.android.tools.r8.ir.code.StaticGet;
 import com.android.tools.r8.ir.code.Value;
 import com.android.tools.r8.ir.conversion.IRConverter;
+import com.android.tools.r8.utils.DescriptorUtils;
 import com.google.common.collect.BiMap;
 import com.google.common.collect.HashBiMap;
 import com.google.common.collect.ImmutableSet;
@@ -298,8 +299,11 @@
     String rewrittenString = rewritten.toString();
     String actualRewrittenPrefix = rewrittenString.substring(0, rewrittenString.lastIndexOf('.'));
     assert javaName.startsWith(actualPrefix);
-    appView.rewritePrefix.addPrefix(
-        javaName, actualRewrittenPrefix + javaName.substring(actualPrefix.length()));
+    appView.rewritePrefix.rewriteType(
+        lambdaClassType,
+        factory.createType(
+            DescriptorUtils.javaTypeToDescriptor(
+                actualRewrittenPrefix + javaName.substring(actualPrefix.length()))));
   }
 
   private static <K, V> V getKnown(Map<K, V> map, K key) {
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 3f7402f..244dfaf 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
@@ -23,7 +23,7 @@
 
   public abstract DexType rewrittenType(DexType type);
 
-  public abstract void addPrefix(String prefix, String rewrittenPrefix);
+  public abstract void rewriteType(DexType type, DexType rewrittenType);
 
   public boolean hasRewrittenType(DexType type) {
     return rewrittenType(type) != null;
@@ -35,9 +35,7 @@
 
     private final Set<DexType> notRewritten = Sets.newConcurrentHashSet();
     private final Map<DexType, DexType> rewritten = new ConcurrentHashMap<>();
-    // Prefix is IdentityHashMap, additionalPrefixes requires however concurrent read and writes.
     private final Map<DexString, DexString> initialPrefixes;
-    private final Map<DexString, DexString> additionalPrefixes = new ConcurrentHashMap<>();
     private final DexItemFactory factory;
 
     public DesugarPrefixRewritingMapper(Map<String, String> prefixes, DexItemFactory factory) {
@@ -97,20 +95,25 @@
     }
 
     @Override
-    public void addPrefix(String prefix, String rewrittenPrefix) {
-      additionalPrefixes.putIfAbsent(
-          toDescriptorPrefix(prefix), toDescriptorPrefix(rewrittenPrefix));
+    public void rewriteType(DexType type, DexType rewrittenType) {
+      assert !notRewritten.contains(type)
+          : "New rewriting rule for "
+              + type
+              + " but the compiler has already made decisions based on the fact that this type was"
+              + " not rewritten";
+      assert !rewritten.containsKey(type) || rewritten.get(type) == rewrittenType
+          : "New rewriting rule for "
+              + type
+              + " but the compiler has already made decisions based on a different rewriting rule"
+              + " for this type";
+      rewritten.put(type, rewrittenType);
     }
 
     private DexType computePrefix(DexType type) {
       DexString prefixToMatch = type.descriptor.withoutArray(factory);
-      DexType result1 = lookup(type, prefixToMatch, initialPrefixes);
-      if (result1 != null) {
-        return result1;
-      }
-      DexType result2 = lookup(type, prefixToMatch, additionalPrefixes);
-      if (result2 != null) {
-        return result2;
+      DexType result = lookup(type, prefixToMatch, initialPrefixes);
+      if (result != null) {
+        return result;
       }
       notRewritten.add(type);
       return null;
@@ -123,7 +126,7 @@
           DexString rewrittenTypeDescriptor =
               type.descriptor.withNewPrefix(prefix, map.get(prefix), factory);
           DexType rewrittenType = factory.createType(rewrittenTypeDescriptor);
-          rewritten.put(type, rewrittenType);
+          rewriteType(type, rewrittenType);
           return rewrittenType;
         }
       }
@@ -144,7 +147,7 @@
     }
 
     @Override
-    public void addPrefix(String prefix, String rewrittenPrefix) {}
+    public void rewriteType(DexType type, DexType rewrittenType) {}
 
     @Override
     public boolean isRewriting() {