diff --git a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
index 00dfa0b..cfccc2b 100644
--- a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
+++ b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
@@ -2261,7 +2261,6 @@
         });
   }
 
-  @Deprecated
   synchronized public void forAllTypes(Consumer<DexType> f) {
     new ArrayList<>(types.values()).forEach(f);
   }
diff --git a/src/main/java/com/android/tools/r8/graph/DexString.java b/src/main/java/com/android/tools/r8/graph/DexString.java
index b5d50f0..602a6b7 100644
--- a/src/main/java/com/android/tools/r8/graph/DexString.java
+++ b/src/main/java/com/android/tools/r8/graph/DexString.java
@@ -500,11 +500,4 @@
     }
     return arrayDim;
   }
-
-  public DexString toArrayDescriptor(int dimensions, DexItemFactory dexItemFactory) {
-    byte[] newContent = new byte[content.length + dimensions];
-    Arrays.fill(newContent, 0, dimensions, (byte) '[');
-    System.arraycopy(content, 0, newContent, dimensions, content.length);
-    return dexItemFactory.createString(size + dimensions, newContent);
-  }
 }
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 b1892bf..f21e965 100644
--- a/src/main/java/com/android/tools/r8/graph/DexType.java
+++ b/src/main/java/com/android/tools/r8/graph/DexType.java
@@ -52,10 +52,6 @@
     this.descriptor = descriptor;
   }
 
-  public DexString getDescriptor() {
-    return descriptor;
-  }
-
   @Override
   public int computeHashCode() {
     return descriptor.hashCode();
@@ -435,7 +431,11 @@
   }
 
   public DexType toArrayType(int dimensions, DexItemFactory dexItemFactory) {
-    return dexItemFactory.createType(descriptor.toArrayDescriptor(dimensions, dexItemFactory));
+    byte[] content = new byte[descriptor.content.length + dimensions];
+    Arrays.fill(content, 0, dimensions, (byte) '[');
+    System.arraycopy(descriptor.content, 0, content, dimensions, descriptor.content.length);
+    DexString newDesc = dexItemFactory.createString(descriptor.size + dimensions, content);
+    return dexItemFactory.createType(newDesc);
   }
 
   public DexType toArrayElementType(DexItemFactory dexItemFactory) {
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 20c918c..b276437 100644
--- a/src/main/java/com/android/tools/r8/graph/GraphLens.java
+++ b/src/main/java/com/android/tools/r8/graph/GraphLens.java
@@ -331,7 +331,9 @@
   }
 
   /** Lookup a rebound or non-rebound method reference using the current graph lens. */
-  public abstract MethodLookupResult lookupMethod(DexMethod method, DexMethod context, Type type);
+  public MethodLookupResult lookupMethod(DexMethod method, DexMethod context, Type type) {
+    return internalLookupMethod(method, context, type, result -> result);
+  }
 
   protected abstract MethodLookupResult internalLookupMethod(
       DexMethod reference, DexMethod context, Type type, LookupMethodContinuation continuation);
@@ -608,10 +610,6 @@
       this.previousLens = previousLens;
     }
 
-    public final DexItemFactory dexItemFactory() {
-      return dexItemFactory;
-    }
-
     public final GraphLens getPrevious() {
       return previousLens;
     }
@@ -624,20 +622,6 @@
     }
 
     @Override
-    public MethodLookupResult lookupMethod(DexMethod method, DexMethod context, Type type) {
-      if (method.getHolderType().isArrayType()) {
-        assert method.getName() == dexItemFactory.cloneMethodName;
-        assert method.getReturnType() == dexItemFactory.objectType;
-        return MethodLookupResult.builder(this)
-            .setReference(method.withHolder(lookupType(method.getHolderType()), dexItemFactory))
-            .setType(type)
-            .build();
-      }
-      assert method.getHolderType().isClassType();
-      return internalLookupMethod(method, context, type, result -> result);
-    }
-
-    @Override
     public final DexType lookupType(DexType type) {
       if (type.isPrimitiveType() || type.isVoidType() || type.isNullValueType()) {
         return type;
@@ -760,11 +744,6 @@
     }
 
     @Override
-    public MethodLookupResult lookupMethod(DexMethod method, DexMethod context, Type type) {
-      return MethodLookupResult.builder(this).setReference(method).setType(type).build();
-    }
-
-    @Override
     public RewrittenPrototypeDescription lookupPrototypeChangesForMethodDefinition(
         DexMethod method) {
       return RewrittenPrototypeDescription.none();
diff --git a/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java b/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java
index ac21dd8..6f5a765 100644
--- a/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java
@@ -32,6 +32,8 @@
 import java.util.Map;
 import java.util.Map.Entry;
 import java.util.Set;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.ExecutorService;
 import java.util.function.Predicate;
 
 class ClassNameMinifier {
@@ -112,11 +114,14 @@
     }
   }
 
-  ClassRenaming computeRenaming(Timing timing) {
-    return computeRenaming(timing, Collections.emptyMap());
+  ClassRenaming computeRenaming(Timing timing, ExecutorService executorService)
+      throws ExecutionException {
+    return computeRenaming(timing, executorService, Collections.emptyMap());
   }
 
-  ClassRenaming computeRenaming(Timing timing, Map<DexType, DexString> syntheticClasses) {
+  ClassRenaming computeRenaming(
+      Timing timing, ExecutorService executorService, Map<DexType, DexString> syntheticClasses)
+      throws ExecutionException {
     // Externally defined synthetic classes populate an initial renaming.
     renaming.putAll(syntheticClasses);
 
@@ -154,6 +159,10 @@
     }
     timing.end();
 
+    timing.begin("rename-arrays");
+    appView.dexItemFactory().forAllTypes(this::renameArrayTypeIfNeeded);
+    timing.end();
+
     return new ClassRenaming(Collections.unmodifiableMap(renaming), getPackageRenaming());
   }
 
@@ -350,6 +359,23 @@
     return state;
   }
 
+  private void renameArrayTypeIfNeeded(DexType type) {
+    if (type.isArrayType()) {
+      DexType base = type.toBaseType(appView.dexItemFactory());
+      DexString value = renaming.get(base);
+      if (value != null) {
+        int dimensions = type.descriptor.numberOfLeadingSquareBrackets();
+        StringBuilder builder = new StringBuilder();
+        for (int i = 0; i < dimensions; i++) {
+          builder.append('[');
+        }
+        builder.append(value.toString());
+        DexString descriptor = appView.dexItemFactory().createString(builder.toString());
+        renaming.put(type, descriptor);
+      }
+    }
+  }
+
   protected class Namespace implements InternalNamingState {
 
     private final String packageName;
diff --git a/src/main/java/com/android/tools/r8/naming/MinifiedRenaming.java b/src/main/java/com/android/tools/r8/naming/MinifiedRenaming.java
index b7bfcdb..42a9287 100644
--- a/src/main/java/com/android/tools/r8/naming/MinifiedRenaming.java
+++ b/src/main/java/com/android/tools/r8/naming/MinifiedRenaming.java
@@ -17,7 +17,6 @@
 import com.android.tools.r8.naming.ClassNameMinifier.ClassRenaming;
 import com.android.tools.r8.naming.FieldNameMinifier.FieldRenaming;
 import com.android.tools.r8.naming.MethodNameMinifier.MethodRenaming;
-import com.android.tools.r8.naming.NamingLens.NonIdentityNamingLens;
 import com.android.tools.r8.utils.DescriptorUtils;
 import com.android.tools.r8.utils.InternalOptions;
 import com.google.common.collect.ImmutableMap;
@@ -28,7 +27,7 @@
 import java.util.function.Function;
 import java.util.function.Predicate;
 
-class MinifiedRenaming extends NonIdentityNamingLens {
+class MinifiedRenaming extends NamingLens {
 
   final AppView<? extends AppInfoWithClassHierarchy> appView;
   private final Map<String, String> packageRenaming;
@@ -39,7 +38,6 @@
       ClassRenaming classRenaming,
       MethodRenaming methodRenaming,
       FieldRenaming fieldRenaming) {
-    super(appView.dexItemFactory());
     this.appView = appView;
     this.packageRenaming = classRenaming.packageRenaming;
     renaming.putAll(classRenaming.classRenaming);
@@ -53,7 +51,7 @@
   }
 
   @Override
-  protected DexString internalLookupClassDescriptor(DexType type) {
+  public DexString lookupDescriptor(DexType type) {
     return renaming.getOrDefault(type, type.descriptor);
   }
 
diff --git a/src/main/java/com/android/tools/r8/naming/Minifier.java b/src/main/java/com/android/tools/r8/naming/Minifier.java
index b886f2b..3d27387 100644
--- a/src/main/java/com/android/tools/r8/naming/Minifier.java
+++ b/src/main/java/com/android/tools/r8/naming/Minifier.java
@@ -58,7 +58,7 @@
             new MinificationPackageNamingStrategy(appView),
             // Use deterministic class order to make sure renaming is deterministic.
             appView.appInfo().classesWithDeterministicOrder());
-    ClassRenaming classRenaming = classNameMinifier.computeRenaming(timing);
+    ClassRenaming classRenaming = classNameMinifier.computeRenaming(timing, executorService);
     timing.end();
 
     assert new MinifiedRenaming(
diff --git a/src/main/java/com/android/tools/r8/naming/NamingLens.java b/src/main/java/com/android/tools/r8/naming/NamingLens.java
index 9147b84..77b5b12 100644
--- a/src/main/java/com/android/tools/r8/naming/NamingLens.java
+++ b/src/main/java/com/android/tools/r8/naming/NamingLens.java
@@ -45,13 +45,6 @@
 
   public abstract DexString lookupDescriptor(DexType type);
 
-  public DexString lookupClassDescriptor(DexType type) {
-    assert type.isClassType();
-    return internalLookupClassDescriptor(type);
-  }
-
-  protected abstract DexString internalLookupClassDescriptor(DexType type);
-
   public abstract DexString lookupInnerName(InnerClassAttribute attribute, InternalOptions options);
 
   public abstract DexString lookupName(DexMethod method);
@@ -123,7 +116,7 @@
       return type.replaceBaseType(newBaseType, dexItemFactory);
     }
     assert type.isClassType();
-    return dexItemFactory.createType(lookupClassDescriptor(type));
+    return dexItemFactory.createType(lookupDescriptor(type));
   }
 
   public boolean hasPrefixRewritingLogic() {
@@ -186,34 +179,7 @@
     return true;
   }
 
-  public abstract static class NonIdentityNamingLens extends NamingLens {
-
-    private final DexItemFactory dexItemFactory;
-
-    protected NonIdentityNamingLens(DexItemFactory dexItemFactory) {
-      this.dexItemFactory = dexItemFactory;
-    }
-
-    protected DexItemFactory dexItemFactory() {
-      return dexItemFactory;
-    }
-
-    @Override
-    public final DexString lookupDescriptor(DexType type) {
-      if (type.isPrimitiveType() || type.isVoidType() || type.isNullValueType()) {
-        return type.getDescriptor();
-      }
-      if (type.isArrayType()) {
-        DexType baseType = type.toBaseType(dexItemFactory);
-        DexString desc = lookupDescriptor(baseType);
-        return desc.toArrayDescriptor(type.getNumberOfLeadingSquareBrackets(), dexItemFactory);
-      }
-      assert type.isClassType();
-      return lookupClassDescriptor(type);
-    }
-  }
-
-  private static final class IdentityLens extends NamingLens {
+  private static class IdentityLens extends NamingLens {
 
     private IdentityLens() {
       // Intentionally left empty.
@@ -225,11 +191,6 @@
     }
 
     @Override
-    protected DexString internalLookupClassDescriptor(DexType type) {
-      return type.descriptor;
-    }
-
-    @Override
     public DexString lookupInnerName(InnerClassAttribute attribute, InternalOptions options) {
       return attribute.getInnerName();
     }
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 e987def..a1451fc 100644
--- a/src/main/java/com/android/tools/r8/naming/PrefixRewritingNamingLens.java
+++ b/src/main/java/com/android/tools/r8/naming/PrefixRewritingNamingLens.java
@@ -11,7 +11,6 @@
 import com.android.tools.r8.graph.DexString;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.InnerClassAttribute;
-import com.android.tools.r8.naming.NamingLens.NonIdentityNamingLens;
 import com.android.tools.r8.utils.InternalOptions;
 import java.util.Collections;
 import java.util.HashMap;
@@ -22,7 +21,7 @@
 import java.util.stream.Stream;
 
 // Naming lens for rewriting type prefixes.
-public class PrefixRewritingNamingLens extends NonIdentityNamingLens {
+public class PrefixRewritingNamingLens extends NamingLens {
 
   final NamingLens namingLens;
   final InternalOptions options;
@@ -41,7 +40,6 @@
   }
 
   public PrefixRewritingNamingLens(NamingLens namingLens, AppView<?> appView) {
-    super(appView.dexItemFactory());
     this.appView = appView;
     this.namingLens = namingLens;
     this.options = appView.options();
@@ -70,7 +68,7 @@
   }
 
   @Override
-  protected DexString internalLookupClassDescriptor(DexType type) {
+  public DexString lookupDescriptor(DexType type) {
     DexString renaming = getRenaming(type);
     return renaming != null ? renaming : namingLens.lookupDescriptor(type);
   }
diff --git a/src/main/java/com/android/tools/r8/naming/ProguardMapMinifier.java b/src/main/java/com/android/tools/r8/naming/ProguardMapMinifier.java
index fab1147..a29f8ef 100644
--- a/src/main/java/com/android/tools/r8/naming/ProguardMapMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/ProguardMapMinifier.java
@@ -143,7 +143,7 @@
             new MinificationPackageNamingStrategy(appView),
             mappedClasses);
     ClassRenaming classRenaming =
-        classNameMinifier.computeRenaming(timing, syntheticCompanionClasses);
+        classNameMinifier.computeRenaming(timing, executorService, syntheticCompanionClasses);
     timing.end();
 
     ApplyMappingMemberNamingStrategy nameStrategy =
@@ -578,9 +578,9 @@
     }
 
     @Override
-    protected DexString internalLookupClassDescriptor(DexType type) {
+    public DexString lookupDescriptor(DexType type) {
       checkForUseOfNotMappedReference(type);
-      return super.internalLookupClassDescriptor(type);
+      return super.lookupDescriptor(type);
     }
 
     private void checkForUseOfNotMappedReference(DexType type) {
diff --git a/src/main/java/com/android/tools/r8/relocator/SimplePackagesRewritingMapper.java b/src/main/java/com/android/tools/r8/relocator/SimplePackagesRewritingMapper.java
index 09ca5bd..50a6e69 100644
--- a/src/main/java/com/android/tools/r8/relocator/SimplePackagesRewritingMapper.java
+++ b/src/main/java/com/android/tools/r8/relocator/SimplePackagesRewritingMapper.java
@@ -15,7 +15,6 @@
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.InnerClassAttribute;
 import com.android.tools.r8.naming.NamingLens;
-import com.android.tools.r8.naming.NamingLens.NonIdentityNamingLens;
 import com.android.tools.r8.references.PackageReference;
 import com.android.tools.r8.utils.DescriptorUtils;
 import com.android.tools.r8.utils.InternalOptions;
@@ -96,18 +95,23 @@
     return new RelocatorNamingLens(typeMappings, packingMappings.build(), appView.dexItemFactory());
   }
 
-  private static class RelocatorNamingLens extends NonIdentityNamingLens {
+  Map<DexType, DexString> getTypeMappings() {
+    return typeMappings;
+  }
+
+  private static class RelocatorNamingLens extends NamingLens {
 
     private final Map<DexType, DexString> typeMappings;
     private final Map<String, String> packageMappings;
+    private final DexItemFactory factory;
 
     private RelocatorNamingLens(
         Map<DexType, DexString> typeMappings,
         Map<String, String> packageMappings,
         DexItemFactory factory) {
-      super(factory);
       this.typeMappings = typeMappings;
       this.packageMappings = packageMappings;
+      this.factory = factory;
     }
 
     @Override
@@ -116,7 +120,20 @@
     }
 
     @Override
-    protected DexString internalLookupClassDescriptor(DexType type) {
+    public DexString lookupDescriptor(DexType type) {
+      if (type.isPrimitiveType() || type.isVoidType()) {
+        return type.descriptor;
+      }
+      if (type.isArrayType()) {
+        DexType baseType = type.toBaseType(factory);
+        if (baseType == null || baseType.isPrimitiveType()) {
+          return type.descriptor;
+        }
+        String baseDescriptor = typeMappings.getOrDefault(baseType, baseType.descriptor).toString();
+        return factory.createString(
+            DescriptorUtils.toArrayDescriptor(
+                type.getNumberOfLeadingSquareBrackets(), baseDescriptor));
+      }
       return typeMappings.getOrDefault(type, type.descriptor);
     }
 
diff --git a/src/test/java/com/android/tools/r8/repackage/RepackageWithArrayMethodTest.java b/src/test/java/com/android/tools/r8/repackage/RepackageWithArrayMethodTest.java
deleted file mode 100644
index 0216990..0000000
--- a/src/test/java/com/android/tools/r8/repackage/RepackageWithArrayMethodTest.java
+++ /dev/null
@@ -1,54 +0,0 @@
-// 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.repackage;
-
-import com.android.tools.r8.NeverInline;
-import com.android.tools.r8.TestParameters;
-import com.android.tools.r8.utils.codeinspector.CodeInspector;
-import org.junit.Test;
-import org.junit.runner.RunWith;
-import org.junit.runners.Parameterized;
-
-@RunWith(Parameterized.class)
-public class RepackageWithArrayMethodTest extends RepackageTestBase {
-
-  public RepackageWithArrayMethodTest(
-      String flattenPackageHierarchyOrRepackageClasses, TestParameters parameters) {
-    super(flattenPackageHierarchyOrRepackageClasses, parameters);
-  }
-
-  @Test
-  public void test() throws Exception {
-    testForR8(parameters.getBackend())
-        .addInnerClasses(getClass())
-        .addKeepMainRule(TestClass.class)
-        .apply(this::configureRepackaging)
-        .enableInliningAnnotations()
-        .setMinApi(parameters.getApiLevel())
-        .compile()
-        .inspect(this::inspect)
-        .run(parameters.getRuntime(), TestClass.class)
-        .assertSuccessWithOutputLines("Hello world!");
-  }
-
-  private void inspect(CodeInspector inspector) {}
-
-  public static class TestClass {
-
-    public static void main(String[] args) {
-      A[] array = new A[1];
-      array[0] = new A();
-      array.clone()[0].greet();
-    }
-  }
-
-  public static class A {
-
-    @NeverInline
-    public void greet() {
-      System.out.println("Hello world!");
-    }
-  }
-}