diff --git a/src/main/java/com/android/tools/r8/JarSizeCompare.java b/src/main/java/com/android/tools/r8/JarSizeCompare.java
index aa16b1f..2aa124a 100644
--- a/src/main/java/com/android/tools/r8/JarSizeCompare.java
+++ b/src/main/java/com/android/tools/r8/JarSizeCompare.java
@@ -332,7 +332,7 @@
             MethodSignature originalSignature =
                 proguardMap == null
                     ? null
-                    : ((MethodSignature) proguardMap.originalSignatureOf(dexEncodedMethod.method));
+                    : proguardMap.originalSignatureOf(dexEncodedMethod.method);
             MethodSignature signature = MethodSignature.fromDexMethod(dexEncodedMethod.method);
             consumer.accept(
                 originalSignature == null ? signature : originalSignature, dexEncodedMethod);
diff --git a/src/main/java/com/android/tools/r8/R8.java b/src/main/java/com/android/tools/r8/R8.java
index ee45cf4..737505c 100644
--- a/src/main/java/com/android/tools/r8/R8.java
+++ b/src/main/java/com/android/tools/r8/R8.java
@@ -630,6 +630,13 @@
       // Validity checks.
       assert application.classes().stream().allMatch(DexClass::isValid);
       assert rootSet.verifyKeptItemsAreKept(application, appView.appInfo(), options);
+      assert appView
+          .graphLense()
+          .verifyMappingToOriginalProgram(
+              application.classesWithDeterministicOrder(),
+              new ApplicationReader(inputApp.withoutMainDexList(), options, timing)
+                  .read(executorService),
+              appView.dexItemFactory());
 
       // Report synthetic rules (only for testing).
       // TODO(b/120959039): Move this to being reported through the graph consumer.
diff --git a/src/main/java/com/android/tools/r8/cf/CfPrinter.java b/src/main/java/com/android/tools/r8/cf/CfPrinter.java
index 79ea482..5be17c6 100644
--- a/src/main/java/com/android/tools/r8/cf/CfPrinter.java
+++ b/src/main/java/com/android/tools/r8/cf/CfPrinter.java
@@ -716,7 +716,7 @@
 
   private void appendMethod(DexMethod method) {
     if (mapper != null) {
-      MethodSignature signature = (MethodSignature) mapper.originalSignatureOf(method);
+      MethodSignature signature = mapper.originalSignatureOf(method);
       builder.append(mapper.originalNameOf(method.holder)).append('.');
       builder.append(signature.name).append(signature.toDescriptor());
       return;
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 1d7555d..31edee9 100644
--- a/src/main/java/com/android/tools/r8/graph/DexType.java
+++ b/src/main/java/com/android/tools/r8/graph/DexType.java
@@ -3,10 +3,16 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.graph;
 
+import static com.android.tools.r8.ir.desugar.InterfaceMethodRewriter.COMPANION_CLASS_NAME_SUFFIX;
+import static com.android.tools.r8.ir.desugar.InterfaceMethodRewriter.DISPATCH_CLASS_NAME_SUFFIX;
+import static com.android.tools.r8.ir.desugar.LambdaRewriter.LAMBDA_CLASS_NAME_PREFIX;
+import static com.android.tools.r8.ir.desugar.LambdaRewriter.LAMBDA_GROUP_CLASS_NAME_PREFIX;
+
 import com.android.tools.r8.dex.IndexedItemCollection;
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.utils.DescriptorUtils;
+import com.android.tools.r8.utils.InternalOptions.OutlineOptions;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Sets;
@@ -441,6 +447,15 @@
     return isPrimitiveType((char) descriptor.content[1]);
   }
 
+  public boolean isD8R8SynthesizedClassType() {
+    String name = toSourceString();
+    return name.contains(COMPANION_CLASS_NAME_SUFFIX)
+        || name.contains(DISPATCH_CLASS_NAME_SUFFIX)
+        || name.contains(LAMBDA_CLASS_NAME_PREFIX)
+        || name.contains(LAMBDA_GROUP_CLASS_NAME_PREFIX)
+        || name.contains(OutlineOptions.CLASS_NAME);
+  }
+
   public int elementSizeForPrimitiveArrayType() {
     assert isPrimitiveArrayType();
     switch (descriptor.content[1]) {
diff --git a/src/main/java/com/android/tools/r8/graph/GraphLense.java b/src/main/java/com/android/tools/r8/graph/GraphLense.java
index 247a5fe..50c91eb 100644
--- a/src/main/java/com/android/tools/r8/graph/GraphLense.java
+++ b/src/main/java/com/android/tools/r8/graph/GraphLense.java
@@ -12,9 +12,12 @@
 import com.google.common.collect.HashBiMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.ImmutableSortedSet;
+import com.google.common.collect.Sets;
 import it.unimi.dsi.fastutil.objects.Object2BooleanArrayMap;
 import it.unimi.dsi.fastutil.objects.Object2BooleanMap;
+import java.util.ArrayDeque;
 import java.util.Collections;
+import java.util.Deque;
 import java.util.HashSet;
 import java.util.IdentityHashMap;
 import java.util.LinkedList;
@@ -521,6 +524,82 @@
     return builder.build();
   }
 
+  public boolean verifyMappingToOriginalProgram(
+      Iterable<DexProgramClass> classes,
+      DexApplication originalApplication,
+      DexItemFactory dexItemFactory) {
+    // Collect all original fields and methods for efficient querying.
+    Set<DexField> originalFields = Sets.newIdentityHashSet();
+    Set<DexMethod> originalMethods = Sets.newIdentityHashSet();
+    for (DexProgramClass clazz : originalApplication.classes()) {
+      for (DexEncodedField field : clazz.fields()) {
+        originalFields.add(field.field);
+      }
+      for (DexEncodedMethod method : clazz.methods()) {
+        originalMethods.add(method.method);
+      }
+    }
+
+    // Check that all fields and methods in the generated program can be mapped back to one of the
+    // original fields or methods.
+    for (DexProgramClass clazz : classes) {
+      if (clazz.type.isD8R8SynthesizedClassType()) {
+        continue;
+      }
+      for (DexEncodedField field : clazz.fields()) {
+        DexField originalField = getOriginalFieldSignature(field.field);
+        assert originalFields.contains(originalField)
+            : "Unable to map field `" + field.field.toSourceString() + "` back to original program";
+      }
+      for (DexEncodedMethod method : clazz.methods()) {
+        if (method.accessFlags.isSynthetic()) {
+          // This could be a bridge that has been inserted, for example, as a result of member
+          // rebinding. Consider only skipping the check below for methods that have been
+          // synthesized by R8.
+          continue;
+        }
+        DexMethod originalMethod = getOriginalMethodSignature(method.method);
+        assert originalMethods.contains(originalMethod)
+                || verifyIsBridgeMethod(
+                    originalMethod, originalApplication, originalMethods, dexItemFactory)
+            : "Unable to map method `"
+                + originalMethod.toSourceString()
+                + "` back to original program";
+      }
+    }
+
+    return true;
+  }
+
+  // Check if `method` is a bridge method for a method that is in the original application.
+  // This is needed because member rebinding synthesizes bridge methods for visibility.
+  private static boolean verifyIsBridgeMethod(
+      DexMethod method,
+      DexApplication originalApplication,
+      Set<DexMethod> originalMethods,
+      DexItemFactory dexItemFactory) {
+    Deque<DexType> worklist = new ArrayDeque<>();
+    Set<DexType> visited = Sets.newIdentityHashSet();
+    worklist.add(method.holder);
+    while (!worklist.isEmpty()) {
+      DexType holder = worklist.removeFirst();
+      if (!visited.add(holder)) {
+        // Already visited previously.
+        continue;
+      }
+      DexMethod targetMethod = dexItemFactory.createMethod(holder, method.proto, method.name);
+      if (originalMethods.contains(targetMethod)) {
+        return true;
+      }
+      DexClass clazz = originalApplication.definitionFor(holder);
+      if (clazz != null) {
+        worklist.add(clazz.superType);
+        Collections.addAll(worklist, clazz.interfaces.values);
+      }
+    }
+    return false;
+  }
+
   private static class IdentityGraphLense extends GraphLense {
 
     private static IdentityGraphLense INSTANCE = new IdentityGraphLense();
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
index 4ecda95..e96acfb 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
@@ -1176,8 +1176,11 @@
     }
     if (paramsCheckedForNull.length() > 0) {
       // Check if collected information conforms to non-null parameter hints in Kotlin metadata.
+      // These hints are on the original holder. To find the original holder, we first find the
+      // original method signature (this could have changed as a result of, for example, class
+      // merging). Then, we find the type that now corresponds to the the original holder.
       DexMethod originalSignature = graphLense().getOriginalMethodSignature(method.method);
-      DexClass originalHolder = definitionFor(originalSignature.holder);
+      DexClass originalHolder = definitionFor(graphLense().lookupType(originalSignature.holder));
       if (originalHolder.hasKotlinInfo()) {
         KotlinInfo kotlinInfo = originalHolder.getKotlinInfo();
         if (kotlinInfo.hasNonNullParameterHints()) {
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 08e4ee5..707078f 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
@@ -52,6 +52,7 @@
 
   // Public for testing.
   public static final String LAMBDA_CLASS_NAME_PREFIX = "-$$Lambda$";
+  public static final String LAMBDA_GROUP_CLASS_NAME_PREFIX = "-$$LambdaGroup$";
   static final String EXPECTED_LAMBDA_METHOD_PREFIX = "lambda$";
   static final String LAMBDA_INSTANCE_FIELD_NAME = "INSTANCE";
 
diff --git a/src/main/java/com/android/tools/r8/naming/ClassNameMapper.java b/src/main/java/com/android/tools/r8/naming/ClassNameMapper.java
index 9cdb95c..bcc0af3 100644
--- a/src/main/java/com/android/tools/r8/naming/ClassNameMapper.java
+++ b/src/main/java/com/android/tools/r8/naming/ClassNameMapper.java
@@ -244,7 +244,7 @@
     return classNaming.originalName + " " + memberNaming.signature.toString();
   }
 
-  public Signature originalSignatureOf(DexMethod method) {
+  public MethodSignature originalSignatureOf(DexMethod method) {
     String decoded = descriptorToJavaType(method.holder.descriptor.toString());
     MethodSignature memberSignature = getRenamedMethodSignature(method);
     ClassNaming classNaming = getClassNaming(decoded);
@@ -255,7 +255,7 @@
     if (memberNaming == null) {
       return memberSignature;
     }
-    return memberNaming.signature;
+    return (MethodSignature) memberNaming.signature;
   }
 
   public FieldSignature originalSignatureOf(DexField field) {
diff --git a/src/main/java/com/android/tools/r8/naming/ProguardMapApplier.java b/src/main/java/com/android/tools/r8/naming/ProguardMapApplier.java
index 6232fb3..d5add45 100644
--- a/src/main/java/com/android/tools/r8/naming/ProguardMapApplier.java
+++ b/src/main/java/com/android/tools/r8/naming/ProguardMapApplier.java
@@ -214,7 +214,7 @@
               applyClassMappingOnTheFly(originalField.clazz),
               applyClassMappingOnTheFly(originalField.type),
               appInfo.dexItemFactory.createString(appliedSignature.name));
-      lenseBuilder.map(originalField, appliedField);
+      lenseBuilder.move(originalField, appliedField);
     }
 
     private void applyMethodMapping(DexMethod originalMethod, MemberNaming memberNaming) {
@@ -224,7 +224,7 @@
               applyClassMappingOnTheFly(originalMethod.holder),
               applyClassMappingOnTheFly(originalMethod.proto),
               appInfo.dexItemFactory.createString(appliedSignature.name));
-      lenseBuilder.map(originalMethod, appliedMethod);
+      lenseBuilder.move(originalMethod, appliedMethod);
     }
 
     private DexType applyClassMappingOnTheFly(DexType from) {
@@ -336,7 +336,7 @@
         if (newHolderType != appliedMethod.holder || newProto != appliedMethod.proto) {
           newMethod = appInfo.dexItemFactory.createMethod(
               substituteType(newHolderType, encodedMethod), newProto, appliedMethod.name);
-          lenseBuilder.map(encodedMethod.method, newMethod);
+          lenseBuilder.move(encodedMethod.method, newMethod);
         } else {
           newMethod = appliedMethod;
         }
@@ -359,7 +359,7 @@
         if (newHolderType != appliedField.clazz || newFieldType != appliedField.type) {
           newField = appInfo.dexItemFactory.createField(
               substituteType(newHolderType, null), newFieldType, appliedField.name);
-          lenseBuilder.map(encodedField.field, newField);
+          lenseBuilder.move(encodedField.field, newField);
         } else {
           newField = appliedField;
         }
diff --git a/src/main/java/com/android/tools/r8/utils/AndroidApp.java b/src/main/java/com/android/tools/r8/utils/AndroidApp.java
index 49573db..28d1628 100644
--- a/src/main/java/com/android/tools/r8/utils/AndroidApp.java
+++ b/src/main/java/com/android/tools/r8/utils/AndroidApp.java
@@ -279,6 +279,19 @@
     return mainDexClasses;
   }
 
+  /** Returns a copy of this AndroidApp that does not have a main dex list. */
+  public AndroidApp withoutMainDexList() {
+    return new AndroidApp(
+        programResourceProviders,
+        programResourcesMainDescriptor,
+        classpathResourceProviders,
+        libraryResourceProviders,
+        archiveProvidersToClose,
+        proguardMapOutputData,
+        ImmutableList.of(),
+        ImmutableList.of());
+  }
+
   /**
    * Write the dex program resources and proguard resource to @code{output}.
    */
diff --git a/src/test/java/com/android/tools/r8/cf/BootstrapCurrentEqualityTest.java b/src/test/java/com/android/tools/r8/cf/BootstrapCurrentEqualityTest.java
index aeeb0ec..092d06e 100644
--- a/src/test/java/com/android/tools/r8/cf/BootstrapCurrentEqualityTest.java
+++ b/src/test/java/com/android/tools/r8/cf/BootstrapCurrentEqualityTest.java
@@ -71,12 +71,13 @@
               .compile()
               .outputJar();
     } else {
-      jar = testFolder.newFolder().toPath().resolve("out.zip");
+      jar = testFolder.newFolder().toPath().resolve("out.jar");
       R8.run(
           R8Command.builder()
-              .setMode(CompilationMode.RELEASE)
-              .addLibraryFiles(runtimeJar(Backend.CF))
+              .setMode(mode)
               .addProgramFiles(ToolHelper.R8_WITH_RELOCATED_DEPS_JAR)
+              .addProguardConfigurationFiles(MAIN_KEEP)
+              .addLibraryFiles(runtimeJar(Backend.CF))
               .setOutput(jar, OutputMode.ClassFile)
               .build());
     }