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 a24eb49..f4407b4 100644
--- a/src/main/java/com/android/tools/r8/graph/AppView.java
+++ b/src/main/java/com/android/tools/r8/graph/AppView.java
@@ -214,7 +214,7 @@
   }
 
   public GraphLens clearCodeRewritings() {
-    return graphLens = graphLens.withCodeRewritingsApplied();
+    return graphLens = graphLens.withCodeRewritingsApplied(dexItemFactory());
   }
 
   public AppServices appServices() {
diff --git a/src/main/java/com/android/tools/r8/graph/AppliedGraphLens.java b/src/main/java/com/android/tools/r8/graph/AppliedGraphLens.java
index f3515e9..dac8f8b 100644
--- a/src/main/java/com/android/tools/r8/graph/AppliedGraphLens.java
+++ b/src/main/java/com/android/tools/r8/graph/AppliedGraphLens.java
@@ -5,12 +5,16 @@
 package com.android.tools.r8.graph;
 
 import com.android.tools.r8.graph.GraphLens.NonIdentityGraphLens;
+import com.android.tools.r8.graph.classmerging.VerticallyMergedClasses;
 import com.android.tools.r8.ir.code.Invoke;
 import com.android.tools.r8.utils.MapUtils;
+import com.android.tools.r8.utils.collections.BidirectionalManyToOneMap;
 import com.google.common.collect.BiMap;
 import com.google.common.collect.HashBiMap;
 import java.util.IdentityHashMap;
+import java.util.List;
 import java.util.Map;
+import java.util.Set;
 
 /**
  * A graph lens that will not lead to any code rewritings in the {@link
@@ -21,9 +25,8 @@
  */
 public final class AppliedGraphLens extends NonIdentityGraphLens {
 
-  private final AppView<?> appView;
-
-  private final BiMap<DexType, DexType> originalTypeNames = HashBiMap.create();
+  private final BidirectionalManyToOneMap<DexType, DexType> renamedTypeNames =
+      new BidirectionalManyToOneMap<>();
   private final BiMap<DexField, DexField> originalFieldSignatures = HashBiMap.create();
   private final BiMap<DexMethod, DexMethod> originalMethodSignatures = HashBiMap.create();
 
@@ -33,22 +36,10 @@
   private final Map<DexMethod, DexMethod> extraOriginalMethodSignatures = new IdentityHashMap<>();
 
   public AppliedGraphLens(AppView<? extends AppInfoWithClassHierarchy> appView) {
-    super(GraphLens.getIdentityLens());
-    this.appView = appView;
-
+    super(appView.dexItemFactory(), GraphLens.getIdentityLens());
     for (DexProgramClass clazz : appView.appInfo().classes()) {
       // Record original type names.
-      {
-        DexType type = clazz.type;
-        if (appView.verticallyMergedClasses() != null
-            && !appView.verticallyMergedClasses().hasBeenMergedIntoSubtype(type)) {
-          DexType original = appView.graphLens().getOriginalType(type);
-          if (original != type) {
-            DexType existing = originalTypeNames.forcePut(type, original);
-            assert existing == null;
-          }
-        }
-      }
+      recordOriginalTypeNames(clazz, appView);
 
       // Record original field signatures.
       for (DexEncodedField encodedField : clazz.fields()) {
@@ -84,6 +75,29 @@
     MapUtils.removeIdentityMappings(extraOriginalMethodSignatures);
   }
 
+  private void recordOriginalTypeNames(
+      DexProgramClass clazz, AppView<? extends AppInfoWithClassHierarchy> appView) {
+    DexType type = clazz.getType();
+    VerticallyMergedClasses verticallyMergedClasses = appView.verticallyMergedClasses();
+    if (verticallyMergedClasses != null && verticallyMergedClasses.hasBeenMergedIntoSubtype(type)) {
+      return;
+    }
+
+    DexType original = appView.graphLens().getOriginalType(type);
+    if (verticallyMergedClasses != null) {
+      List<DexType> sources = verticallyMergedClasses.getSourcesFor(type);
+      if (!sources.isEmpty()) {
+        renamedTypeNames.put(original, type);
+        sources.forEach(source -> renamedTypeNames.put(source, type));
+        return;
+      }
+    }
+
+    if (original != type) {
+      renamedTypeNames.put(original, type);
+    }
+  }
+
   @Override
   public boolean isAppliedLens() {
     return true;
@@ -91,7 +105,11 @@
 
   @Override
   public DexType getOriginalType(DexType type) {
-    return originalTypeNames.getOrDefault(type, type);
+    Set<DexType> originalTypeNames = renamedTypeNames.getKeys(type);
+    if (!originalTypeNames.isEmpty()) {
+      return originalTypeNames.iterator().next();
+    }
+    return type;
   }
 
   @Override
@@ -120,12 +138,8 @@
   }
 
   @Override
-  public DexType lookupType(DexType type) {
-    if (appView.verticallyMergedClasses() != null
-        && appView.verticallyMergedClasses().hasBeenMergedIntoSubtype(type)) {
-      return lookupType(appView.verticallyMergedClasses().getTargetFor(type));
-    }
-    return originalTypeNames.inverse().getOrDefault(type, type);
+  public DexType internalDescribeLookupClassType(DexType previous) {
+    return renamedTypeNames.getOrDefault(previous, previous);
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/graph/DexType.java b/src/main/java/com/android/tools/r8/graph/DexType.java
index 23fa997..c4e2701 100644
--- a/src/main/java/com/android/tools/r8/graph/DexType.java
+++ b/src/main/java/com/android/tools/r8/graph/DexType.java
@@ -252,6 +252,12 @@
     return descriptor.content[0] == 'D';
   }
 
+  public boolean isNullValueType() {
+    boolean isNullValueType = descriptor.content[0] == 'N';
+    assert !isNullValueType || this == DexItemFactory.nullValueType;
+    return isNullValueType;
+  }
+
   public boolean isArrayType() {
     char firstChar = (char) descriptor.content[0];
     return firstChar == '[';
diff --git a/src/main/java/com/android/tools/r8/graph/GraphLens.java b/src/main/java/com/android/tools/r8/graph/GraphLens.java
index ad7cd8b..b459207 100644
--- a/src/main/java/com/android/tools/r8/graph/GraphLens.java
+++ b/src/main/java/com/android/tools/r8/graph/GraphLens.java
@@ -22,6 +22,7 @@
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
+import java.util.concurrent.ConcurrentHashMap;
 
 /**
  * A GraphLens implements a virtual view on top of the graph, used to delay global rewrites until
@@ -262,6 +263,8 @@
     return holder.lookupProgramMethod(newMethod);
   }
 
+  public abstract DexType lookupClassType(DexType type);
+
   public abstract DexType lookupType(DexType type);
 
   // This overload can be used when the graph lens is known to be context insensitive.
@@ -354,9 +357,9 @@
     return null;
   }
 
-  public GraphLens withCodeRewritingsApplied() {
+  public GraphLens withCodeRewritingsApplied(DexItemFactory dexItemFactory) {
     if (hasCodeRewritings()) {
-      return new ClearCodeRewritingGraphLens(this);
+      return new ClearCodeRewritingGraphLens(dexItemFactory, this);
     }
     return this;
   }
@@ -514,9 +517,13 @@
 
   public abstract static class NonIdentityGraphLens extends GraphLens {
 
+    private final DexItemFactory dexItemFactory;
     private GraphLens previousLens;
 
-    public NonIdentityGraphLens(GraphLens previousLens) {
+    private final Map<DexType, DexType> arrayTypeCache = new ConcurrentHashMap<>();
+
+    public NonIdentityGraphLens(DexItemFactory dexItemFactory, GraphLens previousLens) {
+      this.dexItemFactory = dexItemFactory;
       this.previousLens = previousLens;
     }
 
@@ -532,6 +539,30 @@
     }
 
     @Override
+    public final DexType lookupType(DexType type) {
+      if (type.isPrimitiveType() || type.isVoidType() || type.isNullValueType()) {
+        return type;
+      }
+      if (type.isArrayType()) {
+        DexType result = arrayTypeCache.get(type);
+        if (result == null) {
+          DexType baseType = type.toBaseType(dexItemFactory);
+          DexType newType = lookupType(baseType);
+          result = baseType == newType ? type : type.replaceBaseType(newType, dexItemFactory);
+          arrayTypeCache.put(type, result);
+        }
+        return result;
+      }
+      return lookupClassType(type);
+    }
+
+    @Override
+    public final DexType lookupClassType(DexType type) {
+      assert type.isClassType() : "Expected class type, but was `" + type.toSourceString() + "`";
+      return internalDescribeLookupClassType(getPrevious().lookupClassType(type));
+    }
+
+    @Override
     protected final DexField internalLookupField(
         DexField reference, LookupFieldContinuation continuation) {
       return previousLens.internalLookupField(
@@ -540,6 +571,8 @@
 
     protected abstract FieldLookupResult internalDescribeLookupField(FieldLookupResult previous);
 
+    protected abstract DexType internalDescribeLookupClassType(DexType previous);
+
     @Override
     public final boolean isIdentityLens() {
       return false;
@@ -607,6 +640,12 @@
     }
 
     @Override
+    public DexType lookupClassType(DexType type) {
+      assert type.isClassType();
+      return type;
+    }
+
+    @Override
     public GraphLensLookupResult lookupMethod(DexMethod method, DexMethod context, Type type) {
       return new GraphLensLookupResult(method, type, RewrittenPrototypeDescription.none());
     }
@@ -641,8 +680,8 @@
   // relies on the previous lens for names (getRenamed/Original methods).
   public static class ClearCodeRewritingGraphLens extends NonIdentityGraphLens {
 
-    public ClearCodeRewritingGraphLens(GraphLens previous) {
-      super(previous);
+    public ClearCodeRewritingGraphLens(DexItemFactory dexItemFactory, GraphLens previousLens) {
+      super(dexItemFactory, previousLens);
     }
 
     @Override
@@ -673,8 +712,8 @@
     }
 
     @Override
-    public DexType lookupType(DexType type) {
-      return getPrevious().lookupType(type);
+    public final DexType internalDescribeLookupClassType(DexType previous) {
+      return previous;
     }
 
     @Override
@@ -714,7 +753,6 @@
     protected final DexItemFactory dexItemFactory;
 
     protected final Map<DexType, DexType> typeMap;
-    private final Map<DexType, DexType> arrayTypeCache = new IdentityHashMap<>();
     protected final Map<DexMethod, DexMethod> methodMap;
     protected final Map<DexField, DexField> fieldMap;
 
@@ -737,7 +775,7 @@
         BiMap<DexMethod, DexMethod> originalMethodSignatures,
         GraphLens previousLens,
         DexItemFactory dexItemFactory) {
-      super(previousLens);
+      super(dexItemFactory, previousLens);
       assert !typeMap.isEmpty()
           || !methodMap.isEmpty()
           || !fieldMap.isEmpty()
@@ -797,28 +835,7 @@
     }
 
     @Override
-    public DexType lookupType(DexType type) {
-      if (type.isArrayType()) {
-        synchronized (this) {
-          // This block need to be synchronized due to arrayTypeCache.
-          DexType result = arrayTypeCache.get(type);
-          if (result == null) {
-            DexType baseType = type.toBaseType(dexItemFactory);
-            DexType newType = lookupType(baseType);
-            if (baseType == newType) {
-              result = type;
-            } else {
-              result = type.replaceBaseType(newType, dexItemFactory);
-            }
-            arrayTypeCache.put(type, result);
-          }
-          return result;
-        }
-      }
-      return internalDescribeLookupType(getPrevious().lookupType(type));
-    }
-
-    private DexType internalDescribeLookupType(DexType previous) {
+    protected DexType internalDescribeLookupClassType(DexType previous) {
       return typeMap != null ? typeMap.getOrDefault(previous, previous) : previous;
     }
 
@@ -921,7 +938,7 @@
             .setReboundReference(rewrittenReboundReference)
             .setReference(
                 rewrittenReboundReference.withHolder(
-                    internalDescribeLookupType(previous.getReference().getHolderType()),
+                    internalDescribeLookupClassType(previous.getReference().getHolderType()),
                     dexItemFactory))
             .build();
       } else {
diff --git a/src/main/java/com/android/tools/r8/optimize/MemberRebindingIdentityLens.java b/src/main/java/com/android/tools/r8/optimize/MemberRebindingIdentityLens.java
index 70b14cd..48c94cb 100644
--- a/src/main/java/com/android/tools/r8/optimize/MemberRebindingIdentityLens.java
+++ b/src/main/java/com/android/tools/r8/optimize/MemberRebindingIdentityLens.java
@@ -5,6 +5,7 @@
 package com.android.tools.r8.optimize;
 
 import com.android.tools.r8.graph.DexField;
+import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.FieldAccessInfo;
@@ -25,8 +26,10 @@
   private final Map<DexField, DexField> nonReboundFieldReferenceToDefinitionMap;
 
   private MemberRebindingIdentityLens(
-      Map<DexField, DexField> nonReboundFieldReferenceToDefinitionMap, GraphLens previousLens) {
-    super(previousLens);
+      Map<DexField, DexField> nonReboundFieldReferenceToDefinitionMap,
+      DexItemFactory dexItemFactory,
+      GraphLens previousLens) {
+    super(dexItemFactory, previousLens);
     assert !previousLens.hasCodeRewritings();
     this.nonReboundFieldReferenceToDefinitionMap = nonReboundFieldReferenceToDefinitionMap;
   }
@@ -74,8 +77,8 @@
   }
 
   @Override
-  public DexType lookupType(DexType type) {
-    return getPrevious().lookupType(type);
+  public final DexType internalDescribeLookupClassType(DexType previous) {
+    return previous;
   }
 
   @Override
@@ -109,11 +112,12 @@
       nonReboundFieldReferenceToDefinitionMap.put(nonReboundFieldReference, reboundFieldReference);
     }
 
-    MemberRebindingIdentityLens build(GraphLens previousLens) {
+    MemberRebindingIdentityLens build(DexItemFactory dexItemFactory, GraphLens previousLens) {
       // This intentionally does not return null when the maps are empty. In this case there are no
       // non-rebound field or method references, but the member rebinding lens is still needed to
       // populate the rebound reference during field and method lookup.
-      return new MemberRebindingIdentityLens(nonReboundFieldReferenceToDefinitionMap, previousLens);
+      return new MemberRebindingIdentityLens(
+          nonReboundFieldReferenceToDefinitionMap, dexItemFactory, previousLens);
     }
   }
 }
diff --git a/src/main/java/com/android/tools/r8/optimize/MemberRebindingIdentityLensFactory.java b/src/main/java/com/android/tools/r8/optimize/MemberRebindingIdentityLensFactory.java
index 48a01f8..0172114 100644
--- a/src/main/java/com/android/tools/r8/optimize/MemberRebindingIdentityLensFactory.java
+++ b/src/main/java/com/android/tools/r8/optimize/MemberRebindingIdentityLensFactory.java
@@ -8,6 +8,7 @@
 import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexField;
+import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.FieldAccessInfoCollection;
@@ -45,14 +46,16 @@
                 && testingOptions.alwaysUseExistingFieldAccessInfoCollectionInMemberRebinding
             ? appView.appInfo().withLiveness().getFieldAccessInfoCollection()
             : createFieldAccessInfoCollectionForMemberRebinding(appView, executorService);
-    return create(fieldAccessInfoCollection, appView.graphLens());
+    return create(fieldAccessInfoCollection, appView.dexItemFactory(), appView.graphLens());
   }
 
   public static MemberRebindingIdentityLens create(
-      FieldAccessInfoCollection<?> fieldAccessInfoCollection, GraphLens previousLens) {
+      FieldAccessInfoCollection<?> fieldAccessInfoCollection,
+      DexItemFactory dexItemFactory,
+      GraphLens previousLens) {
     MemberRebindingIdentityLens.Builder builder = MemberRebindingIdentityLens.builder();
     fieldAccessInfoCollection.forEach(builder::recordNonReboundFieldAccesses);
-    return builder.build(previousLens);
+    return builder.build(dexItemFactory, previousLens);
   }
 
   /**
diff --git a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
index 729a1d8..774c954 100644
--- a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
+++ b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
@@ -1700,7 +1700,7 @@
     private final DexProgramClass target;
 
     public SingleTypeMapperGraphLens(DexType source, DexProgramClass target) {
-      super(GraphLens.getIdentityLens());
+      super(appView.dexItemFactory(), GraphLens.getIdentityLens());
       this.source = source;
       this.target = target;
     }
@@ -1731,8 +1731,8 @@
     }
 
     @Override
-    public DexType lookupType(DexType type) {
-      return type == source ? target.type : mergedClasses.getOrDefault(type, type);
+    public final DexType internalDescribeLookupClassType(DexType previous) {
+      return previous == source ? target.type : mergedClasses.getOrDefault(previous, previous);
     }
 
     @Override
diff --git a/src/main/java/com/android/tools/r8/utils/collections/BidirectionalManyToOneMap.java b/src/main/java/com/android/tools/r8/utils/collections/BidirectionalManyToOneMap.java
new file mode 100644
index 0000000..ad65701
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/utils/collections/BidirectionalManyToOneMap.java
@@ -0,0 +1,30 @@
+// 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.utils.collections;
+
+import java.util.Collections;
+import java.util.IdentityHashMap;
+import java.util.LinkedHashSet;
+import java.util.Map;
+import java.util.Set;
+
+public class BidirectionalManyToOneMap<K, V> {
+
+  private final Map<K, V> backing = new IdentityHashMap<>();
+  private final Map<V, Set<K>> inverse = new IdentityHashMap<>();
+
+  public V getOrDefault(K key, V value) {
+    return backing.getOrDefault(key, value);
+  }
+
+  public Set<K> getKeys(V value) {
+    return inverse.getOrDefault(value, Collections.emptySet());
+  }
+
+  public void put(K key, V value) {
+    backing.put(key, value);
+    inverse.computeIfAbsent(value, ignore -> new LinkedHashSet<>()).add(key);
+  }
+}