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 88c4e98..610208f 100644
--- a/src/main/java/com/android/tools/r8/graph/GraphLens.java
+++ b/src/main/java/com/android/tools/r8/graph/GraphLens.java
@@ -15,9 +15,7 @@
 import com.android.tools.r8.utils.SetUtils;
 import com.android.tools.r8.utils.collections.BidirectionalManyToOneRepresentativeHashMap;
 import com.android.tools.r8.utils.collections.BidirectionalManyToOneRepresentativeMap;
-import com.android.tools.r8.utils.collections.BidirectionalOneToOneHashMap;
 import com.android.tools.r8.utils.collections.MutableBidirectionalManyToOneRepresentativeMap;
-import com.android.tools.r8.utils.collections.MutableBidirectionalOneToOneMap;
 import com.android.tools.r8.utils.collections.ProgramMethodSet;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
@@ -231,17 +229,15 @@
     }
   }
 
-  public static class Builder {
+  public abstract static class Builder {
 
-    protected Builder() {}
-
-    protected final Map<DexType, DexType> typeMap = new IdentityHashMap<>();
-    protected final Map<DexMethod, DexMethod> methodMap = new IdentityHashMap<>();
     protected final MutableBidirectionalManyToOneRepresentativeMap<DexField, DexField> fieldMap =
         BidirectionalManyToOneRepresentativeHashMap.newIdentityHashMap();
+    protected final MutableBidirectionalManyToOneRepresentativeMap<DexMethod, DexMethod> methodMap =
+        BidirectionalManyToOneRepresentativeHashMap.newIdentityHashMap();
+    protected final Map<DexType, DexType> typeMap = new IdentityHashMap<>();
 
-    protected final MutableBidirectionalOneToOneMap<DexMethod, DexMethod> originalMethodSignatures =
-        new BidirectionalOneToOneHashMap<>();
+    protected Builder() {}
 
     public void map(DexType from, DexType to) {
       if (from == to) {
@@ -250,19 +246,11 @@
       typeMap.put(from, to);
     }
 
-    public void map(DexMethod from, DexMethod to) {
-      if (from == to) {
-        return;
-      }
-      methodMap.put(from, to);
-    }
-
     public void move(DexMethod from, DexMethod to) {
       if (from == to) {
         return;
       }
-      map(from, to);
-      originalMethodSignatures.put(to, from);
+      methodMap.put(from, to);
     }
 
     public void move(DexField from, DexField to) {
@@ -272,17 +260,7 @@
       fieldMap.put(from, to);
     }
 
-    public GraphLens build(DexItemFactory dexItemFactory) {
-      return build(dexItemFactory, getIdentityLens());
-    }
-
-    public GraphLens build(DexItemFactory dexItemFactory, GraphLens previousLens) {
-      if (typeMap.isEmpty() && methodMap.isEmpty() && fieldMap.isEmpty()) {
-        return previousLens;
-      }
-      return new LegacyNestedGraphLens(
-          typeMap, methodMap, fieldMap, originalMethodSignatures, previousLens, dexItemFactory);
-    }
+    public abstract GraphLens build(AppView<?> appView);
   }
 
   /**
diff --git a/src/main/java/com/android/tools/r8/graph/LegacyNestedGraphLens.java b/src/main/java/com/android/tools/r8/graph/LegacyNestedGraphLens.java
deleted file mode 100644
index f6720fd..0000000
--- a/src/main/java/com/android/tools/r8/graph/LegacyNestedGraphLens.java
+++ /dev/null
@@ -1,292 +0,0 @@
-// Copyright (c) 2021, 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.graph;
-
-import com.android.tools.r8.graph.GraphLens.NonIdentityGraphLens;
-import com.android.tools.r8.ir.code.Invoke.Type;
-import com.android.tools.r8.utils.IterableUtils;
-import com.android.tools.r8.utils.collections.BidirectionalManyToManyRepresentativeMap;
-import com.android.tools.r8.utils.collections.BidirectionalManyToOneRepresentativeMap;
-import java.util.Map;
-import java.util.stream.Collectors;
-
-/**
- * GraphLens implementation with a parent lens using a simple mapping for type, method and field
- * mapping.
- *
- * <p>Subclasses can override the lookup methods.
- *
- * <p>For method mapping where invocation type can change just override {@link
- * #mapInvocationType(DexMethod, DexMethod, Type)} if the default name mapping applies, and only
- * invocation type might need to change.
- */
-public class LegacyNestedGraphLens extends NonIdentityGraphLens {
-
-  protected final DexItemFactory dexItemFactory;
-
-  protected final Map<DexType, DexType> typeMap;
-  protected final Map<DexMethod, DexMethod> methodMap;
-  protected final BidirectionalManyToOneRepresentativeMap<DexField, DexField> fieldMap;
-
-  // Map that store the original signature of methods that have been affected, for example, by
-  // vertical class merging. Needed to generate a correct Proguard map in the end.
-  protected BidirectionalManyToManyRepresentativeMap<DexMethod, DexMethod> originalMethodSignatures;
-
-  // Overrides this if the sub type needs to be a nested lens while it doesn't have any mappings
-  // at all, e.g., publicizer lens that changes invocation type only.
-  protected boolean isLegitimateToHaveEmptyMappings() {
-    return false;
-  }
-
-  public LegacyNestedGraphLens(
-      Map<DexType, DexType> typeMap,
-      Map<DexMethod, DexMethod> methodMap,
-      BidirectionalManyToOneRepresentativeMap<DexField, DexField> fieldMap,
-      BidirectionalManyToManyRepresentativeMap<DexMethod, DexMethod> originalMethodSignatures,
-      GraphLens previousLens,
-      DexItemFactory dexItemFactory) {
-    super(dexItemFactory, previousLens);
-    assert !typeMap.isEmpty()
-        || !methodMap.isEmpty()
-        || !fieldMap.isEmpty()
-        || isLegitimateToHaveEmptyMappings();
-    this.typeMap = typeMap.isEmpty() ? null : typeMap;
-    this.methodMap = methodMap;
-    this.fieldMap = fieldMap;
-    this.originalMethodSignatures = originalMethodSignatures;
-    this.dexItemFactory = dexItemFactory;
-  }
-
-  public static Builder builder() {
-    return new Builder();
-  }
-
-  protected DexType internalGetOriginalType(DexType previous) {
-    return previous;
-  }
-
-  protected Iterable<DexType> internalGetOriginalTypes(DexType previous) {
-    return IterableUtils.singleton(internalGetOriginalType(previous));
-  }
-
-  @Override
-  public DexType getOriginalType(DexType type) {
-    return getPrevious().getOriginalType(internalGetOriginalType(type));
-  }
-
-  @Override
-  public Iterable<DexType> getOriginalTypes(DexType type) {
-    return IterableUtils.flatMap(internalGetOriginalTypes(type), getPrevious()::getOriginalTypes);
-  }
-
-  @Override
-  public DexField getOriginalFieldSignature(DexField field) {
-    DexField originalField = fieldMap.getRepresentativeKeyOrDefault(field, field);
-    return getPrevious().getOriginalFieldSignature(originalField);
-  }
-
-  @Override
-  public DexMethod getOriginalMethodSignature(DexMethod method) {
-    DexMethod originalMethod = internalGetPreviousMethodSignature(method);
-    return getPrevious().getOriginalMethodSignature(originalMethod);
-  }
-
-  @Override
-  public DexField getRenamedFieldSignature(DexField originalField) {
-    DexField renamedField = getPrevious().getRenamedFieldSignature(originalField);
-    return internalGetNextFieldSignature(renamedField);
-  }
-
-  @Override
-  public DexMethod getRenamedMethodSignature(DexMethod originalMethod, GraphLens applied) {
-    if (this == applied) {
-      return originalMethod;
-    }
-    DexMethod renamedMethod = getPrevious().getRenamedMethodSignature(originalMethod, applied);
-    return internalGetNextMethodSignature(renamedMethod);
-  }
-
-  @Override
-  protected DexType internalDescribeLookupClassType(DexType previous) {
-    return typeMap != null ? typeMap.getOrDefault(previous, previous) : previous;
-  }
-
-  @Override
-  protected FieldLookupResult internalDescribeLookupField(FieldLookupResult previous) {
-    if (previous.hasReboundReference()) {
-      // Rewrite the rebound reference and then "fixup" the non-rebound reference.
-      DexField rewrittenReboundReference = previous.getRewrittenReboundReference(fieldMap);
-      DexField rewrittenNonReboundReference =
-          previous.getReference() == previous.getReboundReference()
-              ? rewrittenReboundReference
-              : rewrittenReboundReference.withHolder(
-                  internalDescribeLookupClassType(previous.getReference().getHolderType()),
-                  dexItemFactory);
-      return FieldLookupResult.builder(this)
-          .setReboundReference(rewrittenReboundReference)
-          .setReference(rewrittenNonReboundReference)
-          .setCastType(previous.getRewrittenCastType(this::internalDescribeLookupClassType))
-          .build();
-    } else {
-      // TODO(b/168282032): We should always have the rebound reference, so this should become
-      //  unreachable.
-      DexField rewrittenReference = previous.getRewrittenReference(fieldMap);
-      return FieldLookupResult.builder(this)
-          .setReference(rewrittenReference)
-          .setCastType(previous.getRewrittenCastType(this::internalDescribeLookupClassType))
-          .build();
-    }
-  }
-
-  @Override
-  public MethodLookupResult internalDescribeLookupMethod(
-      MethodLookupResult previous, DexMethod context) {
-    if (previous.hasReboundReference()) {
-      // TODO(sgjesse): Should we always do interface to virtual mapping? Is it a performance win
-      //  that only subclasses which are known to need it actually do it?
-      DexMethod rewrittenReboundReference = previous.getRewrittenReboundReference(methodMap);
-      DexMethod rewrittenReference =
-          previous.getReference() == previous.getReboundReference()
-              ? rewrittenReboundReference
-              : // This assumes that the holder will always be moved in lock-step with the method!
-              rewrittenReboundReference.withHolder(
-                  internalDescribeLookupClassType(previous.getReference().getHolderType()),
-                  dexItemFactory);
-      return MethodLookupResult.builder(this)
-          .setReference(rewrittenReference)
-          .setReboundReference(rewrittenReboundReference)
-          .setPrototypeChanges(
-              internalDescribePrototypeChanges(
-                  previous.getPrototypeChanges(), rewrittenReboundReference))
-          .setType(
-              mapInvocationType(
-                  rewrittenReboundReference, previous.getReference(), previous.getType()))
-          .build();
-    } else {
-      // TODO(b/168282032): We should always have the rebound reference, so this should become
-      //  unreachable.
-      DexMethod newMethod = methodMap.get(previous.getReference());
-      if (newMethod == null) {
-        return previous;
-      }
-      // TODO(sgjesse): Should we always do interface to virtual mapping? Is it a performance win
-      //  that only subclasses which are known to need it actually do it?
-      return MethodLookupResult.builder(this)
-          .setReference(newMethod)
-          .setPrototypeChanges(
-              internalDescribePrototypeChanges(previous.getPrototypeChanges(), newMethod))
-          .setType(mapInvocationType(newMethod, previous.getReference(), previous.getType()))
-          .build();
-    }
-  }
-
-  @Override
-  public RewrittenPrototypeDescription lookupPrototypeChangesForMethodDefinition(DexMethod method) {
-    DexMethod previous = internalGetPreviousMethodSignature(method);
-    RewrittenPrototypeDescription lookup =
-        getPrevious().lookupPrototypeChangesForMethodDefinition(previous);
-    return internalDescribePrototypeChanges(lookup, method);
-  }
-
-  protected RewrittenPrototypeDescription internalDescribePrototypeChanges(
-      RewrittenPrototypeDescription prototypeChanges, DexMethod method) {
-    return prototypeChanges;
-  }
-
-  protected DexField internalGetNextFieldSignature(DexField field) {
-    return fieldMap.getOrDefault(field, field);
-  }
-
-  @Override
-  protected DexMethod internalGetPreviousMethodSignature(DexMethod method) {
-    return originalMethodSignatures.getRepresentativeValueOrDefault(method, method);
-  }
-
-  protected DexMethod internalGetNextMethodSignature(DexMethod method) {
-    return originalMethodSignatures.getRepresentativeKeyOrDefault(method, method);
-  }
-
-  @Override
-  public DexMethod lookupGetFieldForMethod(DexField field, DexMethod context) {
-    return getPrevious().lookupGetFieldForMethod(field, context);
-  }
-
-  @Override
-  public DexMethod lookupPutFieldForMethod(DexField field, DexMethod context) {
-    return getPrevious().lookupPutFieldForMethod(field, context);
-  }
-
-  /**
-   * Default invocation type mapping.
-   *
-   * <p>This is an identity mapping. If a subclass need invocation type mapping either override this
-   * method or {@link #lookupMethod(DexMethod, DexMethod, Type)}
-   */
-  protected Type mapInvocationType(DexMethod newMethod, DexMethod originalMethod, Type type) {
-    return type;
-  }
-
-  /**
-   * Standard mapping between interface and virtual invoke type.
-   *
-   * <p>Handle methods moved from interface to class or class to interface.
-   */
-  public static Type mapVirtualInterfaceInvocationTypes(
-      DexDefinitionSupplier definitions, DexMethod newMethod, DexMethod originalMethod, Type type) {
-    if (type == Type.VIRTUAL || type == Type.INTERFACE) {
-      // Get the invoke type of the actual definition.
-      DexClass newTargetClass = definitions.definitionFor(newMethod.getHolderType());
-      if (newTargetClass == null) {
-        return type;
-      }
-      DexClass originalTargetClass = definitions.definitionFor(originalMethod.getHolderType());
-      if (originalTargetClass != null
-          && (originalTargetClass.isInterface() ^ (type == Type.INTERFACE))) {
-        // The invoke was wrong to start with, so we keep it wrong. This is to ensure we get
-        // the IncompatibleClassChangeError the original invoke would have triggered.
-        return newTargetClass.accessFlags.isInterface() ? Type.VIRTUAL : Type.INTERFACE;
-      }
-      return newTargetClass.accessFlags.isInterface() ? Type.INTERFACE : Type.VIRTUAL;
-    }
-    return type;
-  }
-
-  @Override
-  public boolean isContextFreeForMethods() {
-    return getPrevious().isContextFreeForMethods();
-  }
-
-  @Override
-  public boolean verifyIsContextFreeForMethod(DexMethod method) {
-    assert getPrevious().verifyIsContextFreeForMethod(method);
-    return true;
-  }
-
-  @Override
-  public String toString() {
-    StringBuilder builder = new StringBuilder();
-    if (typeMap != null) {
-      for (Map.Entry<DexType, DexType> entry : typeMap.entrySet()) {
-        builder.append(entry.getKey().toSourceString()).append(" -> ");
-        builder.append(entry.getValue().toSourceString()).append(System.lineSeparator());
-      }
-    }
-    for (Map.Entry<DexMethod, DexMethod> entry : methodMap.entrySet()) {
-      builder.append(entry.getKey().toSourceString()).append(" -> ");
-      builder.append(entry.getValue().toSourceString()).append(System.lineSeparator());
-    }
-    fieldMap.forEachManyToOneMapping(
-        (keys, value) -> {
-          builder.append(
-              keys.stream()
-                  .map(DexField::toSourceString)
-                  .collect(Collectors.joining("," + System.lineSeparator())));
-          builder.append(" -> ");
-          builder.append(value.toSourceString()).append(System.lineSeparator());
-        });
-    builder.append(getPrevious().toString());
-    return builder.toString();
-  }
-}
diff --git a/src/main/java/com/android/tools/r8/graph/NestedGraphLens.java b/src/main/java/com/android/tools/r8/graph/NestedGraphLens.java
index 3d5900d..8eaa46f 100644
--- a/src/main/java/com/android/tools/r8/graph/NestedGraphLens.java
+++ b/src/main/java/com/android/tools/r8/graph/NestedGraphLens.java
@@ -87,10 +87,6 @@
     this.newMethodSignatures = newMethodSignatures;
   }
 
-  public static Builder builder() {
-    return new Builder();
-  }
-
   protected DexType internalGetOriginalType(DexType previous) {
     return previous;
   }
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMergerGraphLens.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMergerGraphLens.java
index 4a8d718..4358dc8 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMergerGraphLens.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMergerGraphLens.java
@@ -8,14 +8,12 @@
 import com.android.tools.r8.graph.DexField;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexType;
-import com.android.tools.r8.graph.LegacyNestedGraphLens;
+import com.android.tools.r8.graph.NestedGraphLens;
 import com.android.tools.r8.ir.conversion.ExtraParameter;
 import com.android.tools.r8.utils.IterableUtils;
 import com.android.tools.r8.utils.collections.BidirectionalManyToOneHashMap;
 import com.android.tools.r8.utils.collections.BidirectionalManyToOneRepresentativeHashMap;
 import com.android.tools.r8.utils.collections.BidirectionalManyToOneRepresentativeMap;
-import com.android.tools.r8.utils.collections.BidirectionalOneToManyRepresentativeHashMap;
-import com.android.tools.r8.utils.collections.BidirectionalOneToManyRepresentativeMap;
 import com.android.tools.r8.utils.collections.MutableBidirectionalManyToOneRepresentativeMap;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Streams;
@@ -25,7 +23,7 @@
 import java.util.Map;
 import java.util.Set;
 
-public class HorizontalClassMergerGraphLens extends LegacyNestedGraphLens {
+public class HorizontalClassMergerGraphLens extends NestedGraphLens {
 
   private final Map<DexMethod, List<ExtraParameter>> methodExtraParameters;
   private final HorizontallyMergedClasses mergedClasses;
@@ -36,14 +34,8 @@
       Map<DexMethod, List<ExtraParameter>> methodExtraParameters,
       BidirectionalManyToOneRepresentativeMap<DexField, DexField> fieldMap,
       Map<DexMethod, DexMethod> methodMap,
-      BidirectionalOneToManyRepresentativeMap<DexMethod, DexMethod> originalMethodSignatures) {
-    super(
-        mergedClasses.getForwardMap(),
-        methodMap,
-        fieldMap,
-        originalMethodSignatures,
-        appView.graphLens(),
-        appView.dexItemFactory());
+      BidirectionalManyToOneRepresentativeMap<DexMethod, DexMethod> newMethodSignatures) {
+    super(appView, fieldMap, methodMap, mergedClasses.getForwardMap(), newMethodSignatures);
     this.methodExtraParameters = methodExtraParameters;
     this.mergedClasses = mergedClasses;
   }
@@ -94,29 +86,30 @@
         BidirectionalManyToOneRepresentativeHashMap.newIdentityHashMap();
     private final BidirectionalManyToOneHashMap<DexMethod, DexMethod> methodMap =
         BidirectionalManyToOneHashMap.newIdentityHashMap();
-    private final BidirectionalOneToManyRepresentativeHashMap<DexMethod, DexMethod>
-        originalMethodSignatures = new BidirectionalOneToManyRepresentativeHashMap<>();
+    private final BidirectionalManyToOneRepresentativeHashMap<DexMethod, DexMethod>
+        newMethodSignatures = BidirectionalManyToOneRepresentativeHashMap.newIdentityHashMap();
     private final Map<DexMethod, List<ExtraParameter>> methodExtraParameters =
         new IdentityHashMap<>();
 
     private final BidirectionalManyToOneHashMap<DexMethod, DexMethod> pendingMethodMapUpdates =
         BidirectionalManyToOneHashMap.newIdentityHashMap();
-    private final BidirectionalOneToManyRepresentativeHashMap<DexMethod, DexMethod>
-        pendingOriginalMethodSignatureUpdates = new BidirectionalOneToManyRepresentativeHashMap<>();
+    private final BidirectionalManyToOneRepresentativeHashMap<DexMethod, DexMethod>
+        pendingNewMethodSignatureUpdates =
+            BidirectionalManyToOneRepresentativeHashMap.newIdentityHashMap();
 
     Builder() {}
 
     HorizontalClassMergerGraphLens build(
         AppView<?> appView, HorizontallyMergedClasses mergedClasses) {
       assert pendingMethodMapUpdates.isEmpty();
-      assert pendingOriginalMethodSignatureUpdates.isEmpty();
+      assert pendingNewMethodSignatureUpdates.isEmpty();
       return new HorizontalClassMergerGraphLens(
           appView,
           mergedClasses,
           methodExtraParameters,
           fieldMap,
           methodMap.getForwardMap(),
-          originalMethodSignatures);
+          newMethodSignatures);
     }
 
     void recordNewFieldSignature(DexField oldFieldSignature, DexField newFieldSignature) {
@@ -161,7 +154,7 @@
     }
 
     void recordNewMethodSignature(DexMethod oldMethodSignature, DexMethod newMethodSignature) {
-      originalMethodSignatures.put(newMethodSignature, oldMethodSignature);
+      newMethodSignatures.put(oldMethodSignature, newMethodSignature);
     }
 
     void fixupMethod(DexMethod oldMethodSignature, DexMethod newMethodSignature) {
@@ -182,12 +175,12 @@
 
     private void fixupOriginalMethodSignatures(
         DexMethod oldMethodSignature, DexMethod newMethodSignature) {
-      Set<DexMethod> oldMethodSignatures = originalMethodSignatures.getValues(oldMethodSignature);
+      Set<DexMethod> oldMethodSignatures = newMethodSignatures.getKeys(oldMethodSignature);
       if (oldMethodSignatures.isEmpty()) {
-        pendingOriginalMethodSignatureUpdates.put(newMethodSignature, oldMethodSignature);
+        pendingNewMethodSignatureUpdates.put(oldMethodSignature, newMethodSignature);
       } else {
         for (DexMethod originalMethodSignature : oldMethodSignatures) {
-          pendingOriginalMethodSignatureUpdates.put(newMethodSignature, originalMethodSignature);
+          pendingNewMethodSignatureUpdates.put(originalMethodSignature, newMethodSignature);
         }
       }
     }
@@ -199,9 +192,9 @@
       pendingMethodMapUpdates.clear();
 
       // Commit pending original method signatures updates.
-      originalMethodSignatures.removeAll(pendingOriginalMethodSignatureUpdates.keySet());
-      pendingOriginalMethodSignatureUpdates.forEachOneToManyMapping(originalMethodSignatures::put);
-      pendingOriginalMethodSignatureUpdates.clear();
+      newMethodSignatures.removeAll(pendingNewMethodSignatureUpdates.keySet());
+      pendingNewMethodSignatureUpdates.forEachManyToOneMapping(newMethodSignatures::put);
+      pendingNewMethodSignatureUpdates.clear();
     }
 
     /**
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 0ed24b2..f6a653b 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
@@ -1245,8 +1245,7 @@
         InterfaceProcessorNestedGraphLens.builder();
     Map<DexClass, DexProgramClass> classMapping =
         processInterfaces(builder, flavour, graphLensBuilder, synthesizedMethods::add);
-    InterfaceProcessorNestedGraphLens graphLens =
-        graphLensBuilder.build(appView.dexItemFactory(), appView.graphLens());
+    InterfaceProcessorNestedGraphLens graphLens = graphLensBuilder.build(appView);
     if (appView.enableWholeProgramOptimizations() && graphLens != null) {
       appView.setGraphLens(graphLens);
     }
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/InterfaceMethodRewriterFixup.java b/src/main/java/com/android/tools/r8/ir/desugar/InterfaceMethodRewriterFixup.java
index ed8077a..bb0de67 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/InterfaceMethodRewriterFixup.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/InterfaceMethodRewriterFixup.java
@@ -53,8 +53,7 @@
       return null;
     }
     // Map default methods to their companion methods.
-    DexMethod mappedMethod =
-        graphLens.getExtraOriginalMethodSignatures().getRepresentativeKey(method);
+    DexMethod mappedMethod = graphLens.getExtraNewMethodSignatures().getRepresentativeValue(method);
     if (mappedMethod != null) {
       return mappedMethod;
     }
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/InterfaceProcessor.java b/src/main/java/com/android/tools/r8/ir/desugar/InterfaceProcessor.java
index 5051001..0199730 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/InterfaceProcessor.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/InterfaceProcessor.java
@@ -37,9 +37,9 @@
 import com.android.tools.r8.graph.GenericSignature.FieldTypeSignature;
 import com.android.tools.r8.graph.GenericSignature.MethodTypeSignature;
 import com.android.tools.r8.graph.GraphLens;
-import com.android.tools.r8.graph.LegacyNestedGraphLens;
 import com.android.tools.r8.graph.MethodAccessFlags;
 import com.android.tools.r8.graph.MethodCollection;
+import com.android.tools.r8.graph.NestedGraphLens;
 import com.android.tools.r8.graph.ParameterAnnotationsList;
 import com.android.tools.r8.graph.ProgramMethod;
 import com.android.tools.r8.ir.code.Invoke.Type;
@@ -325,7 +325,8 @@
       newFlags.promoteToStatic();
 
       DexMethod companionMethod =
-          rewriter.privateAsMethodOfCompanionClass(oldMethod, appView.dexItemFactory());
+          InterfaceMethodRewriter.privateAsMethodOfCompanionClass(
+              oldMethod, appView.dexItemFactory());
 
       Code code = definition.getCode();
       if (code == null) {
@@ -440,27 +441,18 @@
 
   // Specific lens which remaps invocation types to static since all rewrites performed here
   // are to static companion methods.
-  public static class InterfaceProcessorNestedGraphLens extends LegacyNestedGraphLens {
+  public static class InterfaceProcessorNestedGraphLens extends NestedGraphLens {
 
-    private BidirectionalManyToManyRepresentativeMap<DexMethod, DexMethod>
-        extraOriginalMethodSignatures;
+    private BidirectionalManyToManyRepresentativeMap<DexMethod, DexMethod> extraNewMethodSignatures;
 
     public InterfaceProcessorNestedGraphLens(
-        Map<DexType, DexType> typeMap,
-        Map<DexMethod, DexMethod> methodMap,
+        AppView<?> appView,
         BidirectionalManyToOneRepresentativeMap<DexField, DexField> fieldMap,
-        BidirectionalOneToOneMap<DexMethod, DexMethod> originalMethodSignatures,
-        BidirectionalOneToOneMap<DexMethod, DexMethod> extraOriginalMethodSignatures,
-        GraphLens previousLens,
-        DexItemFactory dexItemFactory) {
-      super(
-          typeMap,
-          methodMap,
-          fieldMap,
-          originalMethodSignatures,
-          previousLens,
-          dexItemFactory);
-      this.extraOriginalMethodSignatures = extraOriginalMethodSignatures;
+        BidirectionalManyToOneRepresentativeMap<DexMethod, DexMethod> methodMap,
+        Map<DexType, DexType> typeMap,
+        BidirectionalOneToOneMap<DexMethod, DexMethod> extraNewMethodSignatures) {
+      super(appView, fieldMap, methodMap, typeMap);
+      this.extraNewMethodSignatures = extraNewMethodSignatures;
     }
 
     public static InterfaceProcessorNestedGraphLens find(GraphLens lens) {
@@ -478,14 +470,14 @@
     }
 
     public void toggleMappingToExtraMethods() {
-      BidirectionalManyToManyRepresentativeMap<DexMethod, DexMethod> tmp = originalMethodSignatures;
-      this.originalMethodSignatures = extraOriginalMethodSignatures;
-      this.extraOriginalMethodSignatures = tmp;
+      BidirectionalManyToManyRepresentativeMap<DexMethod, DexMethod> tmp = newMethodSignatures;
+      this.newMethodSignatures = extraNewMethodSignatures;
+      this.extraNewMethodSignatures = tmp;
     }
 
     public BidirectionalManyToManyRepresentativeMap<DexMethod, DexMethod>
-        getExtraOriginalMethodSignatures() {
-      return extraOriginalMethodSignatures;
+        getExtraNewMethodSignatures() {
+      return extraNewMethodSignatures;
     }
 
     @Override
@@ -505,14 +497,14 @@
 
     @Override
     protected DexMethod internalGetPreviousMethodSignature(DexMethod method) {
-      return extraOriginalMethodSignatures.getRepresentativeValueOrDefault(
-          method, originalMethodSignatures.getRepresentativeValueOrDefault(method, method));
+      return extraNewMethodSignatures.getRepresentativeKeyOrDefault(
+          method, newMethodSignatures.getRepresentativeKeyOrDefault(method, method));
     }
 
     @Override
     protected DexMethod internalGetNextMethodSignature(DexMethod method) {
-      return originalMethodSignatures.getRepresentativeKeyOrDefault(
-          method, extraOriginalMethodSignatures.getRepresentativeKeyOrDefault(method, method));
+      return newMethodSignatures.getRepresentativeValueOrDefault(
+          method, extraNewMethodSignatures.getRepresentativeValueOrDefault(method, method));
     }
 
     @Override
@@ -524,33 +516,24 @@
       return new Builder();
     }
 
-    public static class Builder extends LegacyNestedGraphLens.Builder {
+    public static class Builder extends GraphLens.Builder {
 
-      private final MutableBidirectionalOneToOneMap<DexMethod, DexMethod>
-          extraOriginalMethodSignatures = new BidirectionalOneToOneHashMap<>();
+      private final MutableBidirectionalOneToOneMap<DexMethod, DexMethod> extraNewMethodSignatures =
+          new BidirectionalOneToOneHashMap<>();
 
       public void recordCodeMovedToCompanionClass(DexMethod from, DexMethod to) {
         assert from != to;
-        originalMethodSignatures.put(from, from);
-        extraOriginalMethodSignatures.put(to, from);
+        methodMap.put(from, from);
+        extraNewMethodSignatures.put(from, to);
       }
 
       @Override
-      public InterfaceProcessorNestedGraphLens build(
-          DexItemFactory dexItemFactory, GraphLens previousLens) {
-        if (fieldMap.isEmpty()
-            && originalMethodSignatures.isEmpty()
-            && extraOriginalMethodSignatures.isEmpty()) {
+      public InterfaceProcessorNestedGraphLens build(AppView<?> appView) {
+        if (fieldMap.isEmpty() && methodMap.isEmpty() && extraNewMethodSignatures.isEmpty()) {
           return null;
         }
         return new InterfaceProcessorNestedGraphLens(
-            typeMap,
-            methodMap,
-            fieldMap,
-            originalMethodSignatures,
-            extraOriginalMethodSignatures,
-            previousLens,
-            dexItemFactory);
+            appView, fieldMap, methodMap, typeMap, extraNewMethodSignatures);
       }
     }
   }
diff --git a/src/main/java/com/android/tools/r8/optimize/MemberRebindingLens.java b/src/main/java/com/android/tools/r8/optimize/MemberRebindingLens.java
index f2830ad..4310236 100644
--- a/src/main/java/com/android/tools/r8/optimize/MemberRebindingLens.java
+++ b/src/main/java/com/android/tools/r8/optimize/MemberRebindingLens.java
@@ -4,7 +4,7 @@
 
 package com.android.tools.r8.optimize;
 
-import static com.android.tools.r8.graph.LegacyNestedGraphLens.mapVirtualInterfaceInvocationTypes;
+import static com.android.tools.r8.graph.NestedGraphLens.mapVirtualInterfaceInvocationTypes;
 
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexField;
diff --git a/src/main/java/com/android/tools/r8/shaking/VerticalClassMergerGraphLens.java b/src/main/java/com/android/tools/r8/shaking/VerticalClassMergerGraphLens.java
index adc2ca0..467c168 100644
--- a/src/main/java/com/android/tools/r8/shaking/VerticalClassMergerGraphLens.java
+++ b/src/main/java/com/android/tools/r8/shaking/VerticalClassMergerGraphLens.java
@@ -11,8 +11,7 @@
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexProto;
 import com.android.tools.r8.graph.DexType;
-import com.android.tools.r8.graph.GraphLens;
-import com.android.tools.r8.graph.LegacyNestedGraphLens;
+import com.android.tools.r8.graph.NestedGraphLens;
 import com.android.tools.r8.graph.RewrittenPrototypeDescription;
 import com.android.tools.r8.graph.classmerging.VerticallyMergedClasses;
 import com.android.tools.r8.ir.code.Invoke.Type;
@@ -52,7 +51,7 @@
 // invocation will hit the same implementation as the original super.m() call.
 //
 // For the invocation "invoke-virtual A.m()" in B.m2, this graph lens will return the method B.m.
-public class VerticalClassMergerGraphLens extends LegacyNestedGraphLens {
+public class VerticalClassMergerGraphLens extends NestedGraphLens {
 
   interface GraphLensLookupResultProvider {
 
@@ -75,16 +74,9 @@
       Set<DexMethod> mergedMethods,
       Map<DexType, Map<DexMethod, GraphLensLookupResultProvider>>
           contextualVirtualToDirectMethodMaps,
-      BidirectionalOneToOneMap<DexMethod, DexMethod> originalMethodSignatures,
-      Map<DexMethod, DexMethod> originalMethodSignaturesForBridges,
-      GraphLens previousLens) {
-    super(
-        mergedClasses.getForwardMap(),
-        methodMap,
-        fieldMap,
-        originalMethodSignatures,
-        previousLens,
-        appView.dexItemFactory());
+      BidirectionalOneToOneMap<DexMethod, DexMethod> newMethodSignatures,
+      Map<DexMethod, DexMethod> originalMethodSignaturesForBridges) {
+    super(appView, fieldMap, methodMap, mergedClasses.getForwardMap(), newMethodSignatures);
     this.appView = appView;
     this.mergedClasses = mergedClasses;
     this.contextualVirtualToDirectMethodMaps = contextualVirtualToDirectMethodMaps;
@@ -172,7 +164,7 @@
     private final Map<DexType, Map<DexMethod, GraphLensLookupResultProvider>>
         contextualVirtualToDirectMethodMaps = new IdentityHashMap<>();
 
-    private final MutableBidirectionalOneToOneMap<DexMethod, DexMethod> originalMethodSignatures =
+    private final MutableBidirectionalOneToOneMap<DexMethod, DexMethod> newMethodSignatures =
         new BidirectionalOneToOneHashMap<>();
     private final Map<DexMethod, DexMethod> originalMethodSignaturesForBridges =
         new IdentityHashMap<>();
@@ -216,8 +208,8 @@
               context);
         }
       }
-      builder.originalMethodSignatures.forEach(
-          (renamedMethodSignature, originalMethodSignature) ->
+      builder.newMethodSignatures.forEach(
+          (originalMethodSignature, renamedMethodSignature) ->
               newBuilder.recordMove(
                   originalMethodSignature,
                   builder.getMethodSignatureAfterClassMerging(
@@ -244,9 +236,8 @@
           methodMap,
           mergedMethodsBuilder.build(),
           contextualVirtualToDirectMethodMaps,
-          originalMethodSignatures,
-          originalMethodSignaturesForBridges,
-          appView.graphLens());
+          newMethodSignatures,
+          originalMethodSignaturesForBridges);
     }
 
     private DexField getFieldSignatureAfterClassMerging(
@@ -309,7 +300,7 @@
     }
 
     public boolean hasOriginalSignatureMappingFor(DexMethod method) {
-      return originalMethodSignatures.containsKey(method)
+      return newMethodSignatures.containsValue(method)
           || originalMethodSignaturesForBridges.containsKey(method);
     }
 
@@ -327,7 +318,7 @@
     }
 
     public void recordMove(DexMethod from, DexMethod to) {
-      originalMethodSignatures.put(to, from);
+      newMethodSignatures.put(from, to);
     }
 
     public void recordCreationOfBridgeMethod(DexMethod from, DexMethod to) {
@@ -345,7 +336,7 @@
       fieldMap.putAll(builder.fieldMap);
       methodMap.putAll(builder.methodMap);
       mergedMethodsBuilder.addAll(builder.mergedMethodsBuilder.build());
-      originalMethodSignatures.putAll(builder.originalMethodSignatures);
+      newMethodSignatures.putAll(builder.newMethodSignatures);
       originalMethodSignaturesForBridges.putAll(builder.originalMethodSignaturesForBridges);
       for (DexType context : builder.contextualVirtualToDirectMethodMaps.keySet()) {
         Map<DexMethod, GraphLensLookupResultProvider> current =