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 096de5a..2c12a90 100644
--- a/src/main/java/com/android/tools/r8/graph/GraphLense.java
+++ b/src/main/java/com/android/tools/r8/graph/GraphLense.java
@@ -99,6 +99,25 @@
     return this instanceof IdentityGraphLense;
   }
 
+  public boolean assertNotModified(Iterable<DexItem> items) {
+    for (DexItem item : items) {
+      if (item instanceof DexClass) {
+        DexType type = ((DexClass) item).type;
+        assert lookupType(type) == type;
+      } else if (item instanceof DexEncodedMethod) {
+        DexEncodedMethod method = (DexEncodedMethod) item;
+        // We allow changes to bridge methods as these get retargeted even if they are kept.
+        assert method.accessFlags.isBridge() || lookupMethod(method.method) == method.method;
+      } else if (item instanceof DexEncodedField) {
+        DexField field = ((DexEncodedField) item).field;
+        assert lookupField(field) == field;
+      } else {
+        assert false;
+      }
+    }
+    return true;
+  }
+
   private static class IdentityGraphLense extends GraphLense {
 
     @Override
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/LensCodeRewriter.java b/src/main/java/com/android/tools/r8/ir/conversion/LensCodeRewriter.java
index 0e4be8b..4c0be09 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/LensCodeRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/LensCodeRewriter.java
@@ -11,6 +11,7 @@
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexMethodHandle;
 import com.android.tools.r8.graph.DexMethodHandle.MethodHandleType;
+import com.android.tools.r8.graph.DexProto;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.DexValue;
 import com.android.tools.r8.graph.DexValue.DexValueMethodHandle;
@@ -73,6 +74,13 @@
         if (current.isInvokeCustom()) {
           InvokeCustom invokeCustom = current.asInvokeCustom();
           DexCallSite callSite = invokeCustom.getCallSite();
+          DexType[] newParameters = new DexType[callSite.methodProto.parameters.size()];
+          for (int i = 0; i < callSite.methodProto.parameters.size(); i++) {
+            newParameters[i] = graphLense.lookupType(callSite.methodProto.parameters.values[i]);
+          }
+          DexProto newMethodProto =
+              appInfo.dexItemFactory.createProto(
+                  graphLense.lookupType(callSite.methodProto.returnType), newParameters);
           DexMethodHandle newBootstrapMethod = rewriteDexMethodHandle(method,
               callSite.bootstrapMethod);
           List<DexValue> newArgs = callSite.bootstrapArgs.stream().map(
@@ -85,10 +93,12 @@
               })
               .collect(Collectors.toList());
 
-          if (newBootstrapMethod != callSite.bootstrapMethod
+          if (!newMethodProto.equals(callSite.methodProto)
+              || newBootstrapMethod != callSite.bootstrapMethod
               || !newArgs.equals(callSite.bootstrapArgs)) {
-            DexCallSite newCallSite = appInfo.dexItemFactory.createCallSite(
-                callSite.methodName, callSite.methodProto, newBootstrapMethod, newArgs);
+            DexCallSite newCallSite =
+                appInfo.dexItemFactory.createCallSite(
+                    callSite.methodName, newMethodProto, newBootstrapMethod, newArgs);
             InvokeCustom newInvokeCustom = new InvokeCustom(newCallSite, invokeCustom.outValue(),
                 invokeCustom.inValues());
             iterator.replaceCurrentInstruction(newInvokeCustom);
diff --git a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
index dae98ad..d42c68b 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -1659,18 +1659,18 @@
       this.staticInvokes = rewriteMethodsConservatively(previous.staticInvokes, lense);
       this.prunedTypes = rewriteItems(previous.prunedTypes, lense::lookupType);
       // TODO(herhut): Migrate these to Descriptors, as well.
-      assert assertNotModifiedByLense(previous.noSideEffects.keySet(), lense);
+      assert lense.assertNotModified(previous.noSideEffects.keySet());
       this.noSideEffects = previous.noSideEffects;
-      assert assertNotModifiedByLense(previous.assumedValues.keySet(), lense);
+      assert lense.assertNotModified(previous.assumedValues.keySet());
       this.assumedValues = previous.assumedValues;
-      assert assertNotModifiedByLense(previous.alwaysInline, lense);
+      assert lense.assertNotModified(previous.alwaysInline);
       this.alwaysInline = previous.alwaysInline;
       this.identifierNameStrings =
           rewriteMixedItemsConservatively(previous.identifierNameStrings, lense);
       // Switchmap classes should never be affected by renaming.
-      assert assertNotModifiedByLense(
+      assert lense.assertNotModified(
           previous.switchMaps.keySet().stream().map(this::definitionFor).filter(Objects::nonNull)
-              .collect(Collectors.toList()), lense);
+              .collect(Collectors.toList()));
       this.switchMaps = previous.switchMaps;
       this.ordinalsMaps = rewriteKeys(previous.ordinalsMaps, lense::lookupType);
       this.protoLiteFields = previous.protoLiteFields;
@@ -1735,27 +1735,6 @@
       return true;
     }
 
-    private boolean assertNotModifiedByLense(Iterable<DexItem> items, GraphLense lense) {
-      for (DexItem item : items) {
-        if (item instanceof DexClass) {
-          DexType type = ((DexClass) item).type;
-          assert lense.lookupType(type) == type;
-        } else if (item instanceof DexEncodedMethod) {
-          DexEncodedMethod method = (DexEncodedMethod) item;
-          // We only allow changes to bridge methods, as these get retargeted even if they
-          // are kept.
-          assert method.accessFlags.isBridge()
-              || lense.lookupMethod(method.method) == method.method;
-        } else if (item instanceof DexEncodedField) {
-          DexField field = ((DexEncodedField) item).field;
-          assert lense.lookupField(field) == field;
-        } else {
-          assert false;
-        }
-      }
-      return true;
-    }
-
     private SortedSet<DexMethod> joinInvokedMethods(Map<DexType, Set<DexMethod>> invokes) {
       return joinInvokedMethods(invokes, Function.identity());
     }
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 637f763..08722c3 100644
--- a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
+++ b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
@@ -96,8 +96,7 @@
     extractPinnedItems(appInfo.pinnedItems, pinnedTypes);
 
     // TODO(christofferqa): Remove the invariant that the graph lense should not modify any
-    // methods from the sets alwaysInline and noSideEffects (see use of assertNotModifiedBy-
-    // Lense).
+    // methods from the sets alwaysInline and noSideEffects (see use of assertNotModified).
     extractPinnedItems(appInfo.alwaysInline, pinnedTypes);
     extractPinnedItems(appInfo.noSideEffects.keySet(), pinnedTypes);
 
@@ -139,36 +138,41 @@
 
   private void extractPinnedItems(Iterable<DexItem> items, Set<DexType> pinnedTypes) {
     for (DexItem item : items) {
-      // Note: Nothing to do for the case where item is a DexType, since we check for this case
-      // using appInfo.isPinned.
-      if (item instanceof DexField) {
-        // Pin the type of the field.
-        DexField field = (DexField) item;
-        DexClass clazz = appInfo.definitionFor(field.type);
-        if (clazz != null && clazz.isProgramClass()) {
-          pinnedTypes.add(clazz.type);
+      if (item instanceof DexType || item instanceof DexClass) {
+        DexType type = item instanceof DexType ? (DexType) item : ((DexClass) item).type;
+        // We check for the case where the type is pinned according to appInfo.isPinned, so only
+        // add it here if it is not the case.
+        if (!appInfo.isPinned(type)) {
+          markTypeAsPinned(type, pinnedTypes);
         }
-      } else if (item instanceof DexMethod) {
-        // Pin the return type and the parameter types of the method.
-        DexMethod method = (DexMethod) item;
-        DexClass clazz = appInfo.definitionFor(method.proto.returnType);
-        if (clazz != null && clazz.isProgramClass()) {
-          // If we were to merge [other] into its sub class, then we would implicitly change the
-          // signature of this method, and therefore break the invariant.
-          pinnedTypes.add(clazz.type);
-        }
+      } else if (item instanceof DexField || item instanceof DexEncodedField) {
+        // Pin the holder and the type of the field.
+        DexField field =
+            item instanceof DexField ? (DexField) item : ((DexEncodedField) item).field;
+        markTypeAsPinned(field.clazz, pinnedTypes);
+        markTypeAsPinned(field.type, pinnedTypes);
+      } else if (item instanceof DexMethod || item instanceof DexEncodedMethod) {
+        // Pin the holder, the return type and the parameter types of the method. If we were to
+        // merge any of these types into their sub classes, then we would implicitly change the
+        // signature of this method.
+        DexMethod method =
+            item instanceof DexMethod ? (DexMethod) item : ((DexEncodedMethod) item).method;
+        markTypeAsPinned(method.holder, pinnedTypes);
+        markTypeAsPinned(method.proto.returnType, pinnedTypes);
         for (DexType parameterType : method.proto.parameters.values) {
-          clazz = appInfo.definitionFor(parameterType);
-          if (clazz != null && clazz.isProgramClass()) {
-            // If we were to merge [other] into its sub class, then we would implicitly change the
-            // signature of this method, and therefore break the invariant.
-            pinnedTypes.add(clazz.type);
-          }
+          markTypeAsPinned(parameterType, pinnedTypes);
         }
       }
     }
   }
 
+  private void markTypeAsPinned(DexType type, Set<DexType> pinnedTypes) {
+    DexClass clazz = appInfo.definitionFor(type);
+    if (clazz != null && clazz.isProgramClass()) {
+      pinnedTypes.add(type);
+    }
+  }
+
   private boolean isMergeCandidate(DexProgramClass clazz, Set<DexType> pinnedTypes) {
     if (appInfo.instantiatedTypes.contains(clazz.type)
         || appInfo.isPinned(clazz.type)
@@ -269,6 +273,10 @@
     timing.begin("fixup");
     GraphLense result = new TreeFixer().fixupTypeReferences(mergingGraphLense);
     timing.end();
+    assert result.assertNotModified(appInfo.alwaysInline);
+    assert result.assertNotModified(appInfo.noSideEffects.keySet());
+    // TODO(christofferqa): Enable this assert.
+    // assert result.assertNotModified(appInfo.pinnedItems);
     return result;
   }
 
diff --git a/src/test/examplesAndroidO/classmerging/LambdaRewritingTest.java b/src/test/examplesAndroidO/classmerging/LambdaRewritingTest.java
new file mode 100644
index 0000000..79e98d1
--- /dev/null
+++ b/src/test/examplesAndroidO/classmerging/LambdaRewritingTest.java
@@ -0,0 +1,38 @@
+// Copyright (c) 2018, 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 classmerging;
+
+public class LambdaRewritingTest {
+
+  public static void main(String[] args) {
+    Interface obj = new InterfaceImpl();
+
+    // Leads to an invoke-custom instruction that mentions the type of `obj` since it is captured.
+    invoke(() -> obj.foo());
+  }
+
+  private static void invoke(Function f) {
+    f.accept();
+  }
+
+  public interface Function {
+
+    void accept();
+  }
+
+  // Will be merged into InterfaceImpl.
+  public interface Interface {
+
+    void foo();
+  }
+
+  public static class InterfaceImpl implements Interface {
+
+    @Override
+    public void foo() {
+      System.out.println("In InterfaceImpl.foo()");
+    }
+  }
+}
diff --git a/src/test/examplesAndroidO/classmerging/keep-rules.txt b/src/test/examplesAndroidO/classmerging/keep-rules.txt
new file mode 100644
index 0000000..9868dcf
--- /dev/null
+++ b/src/test/examplesAndroidO/classmerging/keep-rules.txt
@@ -0,0 +1,12 @@
+# Copyright (c) 2018, 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.
+
+# Keep the application entry point. Get rid of everything that is not
+# reachable from there.
+-keep public class classmerging.LambdaRewritingTest {
+  public static void main(...);
+}
+
+# TODO(herhut): Consider supporting merging of inner-class attributes.
+# -keepattributes *
\ No newline at end of file
diff --git a/src/test/java/com/android/tools/r8/classmerging/ClassMergingTest.java b/src/test/java/com/android/tools/r8/classmerging/ClassMergingTest.java
index 1e71a82..2e983bd 100644
--- a/src/test/java/com/android/tools/r8/classmerging/ClassMergingTest.java
+++ b/src/test/java/com/android/tools/r8/classmerging/ClassMergingTest.java
@@ -35,6 +35,7 @@
 import java.util.Set;
 import java.util.concurrent.ExecutionException;
 import java.util.function.Consumer;
+import java.util.function.Predicate;
 import org.junit.Ignore;
 import org.junit.Test;
 
@@ -44,11 +45,15 @@
 public class ClassMergingTest extends TestBase {
 
   private static final Path CF_DIR =
-      Paths.get(ToolHelper.BUILD_DIR).resolve("classes/examples/classmerging");
+      Paths.get(ToolHelper.BUILD_DIR).resolve("test/examples/classes/classmerging");
+  private static final Path JAVA8_CF_DIR =
+      Paths.get(ToolHelper.BUILD_DIR).resolve("test/examplesAndroidO/classes/classmerging");
   private static final Path EXAMPLE_JAR = Paths.get(ToolHelper.EXAMPLES_BUILD_DIR)
       .resolve("classmerging.jar");
   private static final Path EXAMPLE_KEEP = Paths.get(ToolHelper.EXAMPLES_DIR)
       .resolve("classmerging").resolve("keep-rules.txt");
+  private static final Path JAVA8_EXAMPLE_KEEP = Paths.get(ToolHelper.EXAMPLES_ANDROID_O_DIR)
+      .resolve("classmerging").resolve("keep-rules.txt");
   private static final Path DONT_OPTIMIZE = Paths.get(ToolHelper.EXAMPLES_DIR)
       .resolve("classmerging").resolve("keep-rules-dontoptimize.txt");
 
@@ -109,6 +114,28 @@
   }
 
   @Test
+  public void testLambdaRewriting() throws Exception {
+    String main = "classmerging.LambdaRewritingTest";
+    Path[] programFiles =
+        new Path[] {
+          JAVA8_CF_DIR.resolve("LambdaRewritingTest.class"),
+          JAVA8_CF_DIR.resolve("LambdaRewritingTest$Function.class"),
+          JAVA8_CF_DIR.resolve("LambdaRewritingTest$Interface.class"),
+          JAVA8_CF_DIR.resolve("LambdaRewritingTest$InterfaceImpl.class")
+        };
+    Set<String> preservedClassNames =
+        ImmutableSet.of(
+            "classmerging.LambdaRewritingTest",
+            "classmerging.LambdaRewritingTest$Function",
+            "classmerging.LambdaRewritingTest$InterfaceImpl");
+    runTest(
+        main,
+        programFiles,
+        name -> preservedClassNames.contains(name) || name.contains("$Lambda$"),
+        getProguardConfig(JAVA8_EXAMPLE_KEEP));
+  }
+
+  @Test
   public void testSuperCallWasDetected() throws Exception {
     String main = "classmerging.SuperCallRewritingTest";
     Path[] programFiles =
@@ -121,7 +148,7 @@
         ImmutableSet.of(
             "classmerging.SubClassThatReferencesSuperMethod",
             "classmerging.SuperCallRewritingTest");
-    runTest(main, programFiles, preservedClassNames);
+    runTest(main, programFiles, preservedClassNames::contains);
   }
 
   // When a subclass A has been merged into its subclass B, we rewrite invoke-super calls that hit
@@ -177,7 +204,7 @@
     runTestOnInput(
         main,
         builder.build(),
-        preservedClassNames,
+        preservedClassNames::contains,
         // Prevent class merging, such that the generated code would be invalid if we rewrite the
         // invoke-super instruction into an invoke-direct instruction.
         getProguardConfig(EXAMPLE_KEEP, "-keep class *"));
@@ -197,7 +224,7 @@
         ImmutableSet.of(
             "classmerging.ConflictingInterfaceSignaturesTest",
             "classmerging.ConflictingInterfaceSignaturesTest$InterfaceImpl");
-    runTest(main, programFiles, preservedClassNames);
+    runTest(main, programFiles, preservedClassNames::contains);
   }
 
   // If an exception class A is merged into another exception class B, then all exception tables
@@ -218,7 +245,7 @@
             "classmerging.ExceptionTest",
             "classmerging.ExceptionTest$ExceptionB",
             "classmerging.ExceptionTest$Exception2");
-    DexInspector inspector = runTest(main, programFiles, preservedClassNames);
+    DexInspector inspector = runTest(main, programFiles, preservedClassNames::contains);
 
     ClassSubject mainClass = inspector.clazz(main);
     assertThat(mainClass, isPresent());
@@ -256,7 +283,7 @@
             "classmerging.SimpleInterfaceAccessTest",
             "classmerging.pkg.SimpleInterfaceImplRetriever",
             "classmerging.pkg.SimpleInterfaceImplRetriever$SimpleInterfaceImpl");
-    runTest(main, programFiles, preservedClassNames);
+    runTest(main, programFiles, preservedClassNames::contains);
   }
 
   @Ignore("b/73958515")
@@ -282,7 +309,7 @@
     runTest(
         main,
         programFiles,
-        preservedClassNames,
+        preservedClassNames::contains,
         getProguardConfig(
             EXAMPLE_KEEP,
             "-allowaccessmodification",
@@ -310,7 +337,7 @@
     runTest(
         main,
         programFiles,
-        preservedClassNames,
+        preservedClassNames::contains,
         getProguardConfig(
             EXAMPLE_KEEP, "-keep class classmerging.RewritePinnedMethodTest$A { *; }"));
   }
@@ -327,40 +354,42 @@
     Set<String> preservedClassNames =
         ImmutableSet.of(
             "classmerging.TemplateMethodTest", "classmerging.TemplateMethodTest$AbstractClassImpl");
-    runTest(main, programFiles, preservedClassNames);
+    runTest(main, programFiles, preservedClassNames::contains);
   }
 
-  private DexInspector runTest(String main, Path[] programFiles, Set<String> preservedClassNames)
-      throws Exception {
+  private DexInspector runTest(
+      String main, Path[] programFiles, Predicate<String> preservedClassNames) throws Exception {
     return runTest(main, programFiles, preservedClassNames, getProguardConfig(EXAMPLE_KEEP));
   }
 
   private DexInspector runTest(
-      String main, Path[] programFiles, Set<String> preservedClassNames, String proguardConfig)
+      String main,
+      Path[] programFiles,
+      Predicate<String> preservedClassNames,
+      String proguardConfig)
       throws Exception {
     return runTestOnInput(
         main, readProgramFiles(programFiles), preservedClassNames, proguardConfig);
   }
 
   private DexInspector runTestOnInput(
-      String main, AndroidApp input, Set<String> preservedClassNames, String proguardConfig)
+      String main, AndroidApp input, Predicate<String> preservedClassNames, String proguardConfig)
       throws Exception {
     AndroidApp output = compileWithR8(input, proguardConfig, this::configure);
-    DexInspector inspector = new DexInspector(output);
+    DexInspector inputInspector = new DexInspector(input);
+    DexInspector outputInspector = new DexInspector(output);
     // Check that all classes in [preservedClassNames] are in fact preserved.
-    for (String className : preservedClassNames) {
-      assertTrue(
-          "Class " + className + " should be present", inspector.clazz(className).isPresent());
-    }
-    // Check that all other classes have been removed.
-    for (FoundClassSubject classSubject : inspector.allClasses()) {
-      String className = classSubject.getDexClass().toSourceString();
-      assertTrue(
-          "Class " + className + " should be absent", preservedClassNames.contains(className));
+    for (FoundClassSubject classSubject : inputInspector.allClasses()) {
+      String className = classSubject.getOriginalName();
+      boolean shouldBePresent = preservedClassNames.test(className);
+      assertEquals(
+          "Class " + className + " should be " + (shouldBePresent ? "present" : "absent"),
+          shouldBePresent,
+          outputInspector.clazz(className).isPresent());
     }
     // Check that the R8-generated code produces the same result as D8-generated code.
     assertEquals(runOnArt(compileWithD8(input), main), runOnArt(output, main));
-    return inspector;
+    return outputInspector;
   }
 
   private String getProguardConfig(Path path, String... additionalRules) throws IOException {
diff --git a/src/test/java/com/android/tools/r8/debug/DebugTestBase.java b/src/test/java/com/android/tools/r8/debug/DebugTestBase.java
index d41ee84..5707812 100644
--- a/src/test/java/com/android/tools/r8/debug/DebugTestBase.java
+++ b/src/test/java/com/android/tools/r8/debug/DebugTestBase.java
@@ -1943,6 +1943,7 @@
             .addAll(super.getExcludedClasses())
             .add("libcore.*")
             .add("dalvik.*")
+            .add("com.android.dex.*") // Android 6.0.1 - 7.0.0 use this for reflection.
             .build();
       }
     }