diff --git a/build.gradle b/build.gradle
index 7f41caa..7761e37 100644
--- a/build.gradle
+++ b/build.gradle
@@ -501,6 +501,9 @@
     task.relocate('org.apache.commons', 'com.android.tools.r8.org.apache.commons')
     task.relocate('org.objectweb.asm', 'com.android.tools.r8.org.objectweb.asm')
     task.relocate('it.unimi.dsi.fastutil', 'com.android.tools.r8.it.unimi.dsi.fastutil')
+    task.relocate('kotlin', 'com.android.tools.r8.jetbrains.kotlin')
+    task.relocate('kotlinx', 'com.android.tools.r8.jetbrains.kotlinx')
+    task.relocate('org.jetbrains', 'com.android.tools.r8.org.jetbrains')
 }
 
 task repackageDeps(type: ShadowJar) {
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 c737055..b11e33d 100644
--- a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
+++ b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
@@ -4,6 +4,7 @@
 package com.android.tools.r8.shaking;
 
 import com.android.tools.r8.errors.CompilationError;
+import com.android.tools.r8.graph.AppInfo.ResolutionResult;
 import com.android.tools.r8.graph.DefaultUseRegistry;
 import com.android.tools.r8.graph.DexAnnotationSet;
 import com.android.tools.r8.graph.DexApplication;
@@ -95,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);
 
@@ -138,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)
@@ -202,9 +207,13 @@
     return true;
   }
 
-  private boolean mergeMayLeadToIllegalAccesses(DexClass clazz, DexClass singleSubclass) {
-    if (clazz.type.isSamePackage(singleSubclass.type)) {
-      return false;
+  private boolean mergeMayLeadToIllegalAccesses(DexClass source, DexClass target) {
+    if (source.type.isSamePackage(target.type)) {
+      int accessLevel =
+          source.accessFlags.isPrivate() ? 0 : (source.accessFlags.isPublic() ? 2 : 1);
+      int otherAccessLevel =
+          target.accessFlags.isPrivate() ? 0 : (target.accessFlags.isPublic() ? 2 : 1);
+      return accessLevel > otherAccessLevel;
     }
     // TODO(christofferqa): To merge [clazz] into a class from another package we need to ensure:
     // (A) All accesses to [clazz] and its members from inside the current package of [clazz] will
@@ -268,6 +277,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;
   }
 
@@ -345,6 +358,9 @@
         }
         continue;
       }
+      if (methodResolutionMayChange(clazz, targetClass)) {
+        continue;
+      }
       // Field resolution first considers the direct interfaces of [targetClass] before it proceeds
       // to the super class.
       if (fieldResolutionMayChange(clazz, targetClass)) {
@@ -395,6 +411,49 @@
     return renamedMembersLense.build(graphLense);
   }
 
+  private boolean methodResolutionMayChange(DexClass source, DexClass target) {
+    // When merging an interface into a class, all instructions on the form "invoke-interface
+    // [source].m" are changed into "invoke-virtual [target].m". We need to abort the merge if this
+    // transformation could hide IncompatibleClassChangeErrors.
+    if (source.isInterface() && !target.isInterface()) {
+      List<DexEncodedMethod> defaultMethods = new ArrayList<>();
+      for (DexEncodedMethod virtualMethod : source.virtualMethods()) {
+        if (!virtualMethod.accessFlags.isAbstract()) {
+          defaultMethods.add(virtualMethod);
+        }
+      }
+
+      // For each of the default methods, the subclass [target] could inherit another default method
+      // with the same signature from another interface (i.e., there is a conflict). In such cases,
+      // instructions on the form "invoke-interface [source].foo()" will fail with an Incompatible-
+      // ClassChangeError.
+      //
+      // Example:
+      //   interface I1 { default void m() {} }
+      //   interface I2 { default void m() {} }
+      //   class C implements I1, I2 {
+      //     ... invoke-interface I1.m ... <- IncompatibleClassChangeError
+      //   }
+      for (DexEncodedMethod method : defaultMethods) {
+        // Conservatively find all possible targets for this method.
+        Set<DexEncodedMethod> interfaceTargets = appInfo.lookupInterfaceTargets(method.method);
+
+        // If [method] is not even an interface-target, then we can safely merge it. Otherwise we
+        // need to check for a conflict.
+        if (interfaceTargets.remove(method)) {
+          for (DexEncodedMethod interfaceTarget : interfaceTargets) {
+            DexClass enclosingClass = appInfo.definitionFor(interfaceTarget.method.holder);
+            if (enclosingClass != null && enclosingClass.isInterface()) {
+              // Found another default method that is different from the one in [source], aborting.
+              return true;
+            }
+          }
+        }
+      }
+    }
+    return false;
+  }
+
   private boolean fieldResolutionMayChange(DexClass source, DexClass target) {
     if (source.type == target.superType) {
       // If there is a "iget Target.f" or "iput Target.f" instruction in target, and the class
@@ -652,17 +711,19 @@
           ParameterAnnotationsList.empty(),
           new SynthesizedCode(
               new ForwardMethodSourceCode(holder, proto, holder, invocationTarget, Type.DIRECT),
-              registry -> registry.registerInvokeDirect(invocationTarget)));
+              registry -> registry.registerInvokeDirect(invocationTarget)),
+          signature.hasClassFileVersion() ? signature.getClassFileVersion() : -1);
     }
 
     // Returns the method that shadows the given method, or null if method is not shadowed.
     private DexEncodedMethod findMethodInTarget(DexEncodedMethod method) {
-      DexEncodedMethod actual = appInfo.resolveMethod(target.type, method.method).asSingleTarget();
-      if (actual == null) {
-        // May happen in case of missing classes.
+      ResolutionResult resolutionResult = appInfo.resolveMethod(target.type, method.method);
+      if (!resolutionResult.hasSingleTarget()) {
+        // May happen in case of missing classes, or if multiple implementations were found.
         abortMerge = true;
         return null;
       }
+      DexEncodedMethod actual = resolutionResult.asSingleTarget();
       if (actual != method) {
         return actual;
       }
diff --git a/src/test/examples/classmerging/SimpleInterface.java b/src/test/examples/classmerging/SimpleInterface.java
deleted file mode 100644
index e8ebcab..0000000
--- a/src/test/examples/classmerging/SimpleInterface.java
+++ /dev/null
@@ -1,9 +0,0 @@
-// 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 interface SimpleInterface {
-  void foo();
-}
diff --git a/src/test/examples/classmerging/SimpleInterfaceAccessTest.java b/src/test/examples/classmerging/SimpleInterfaceAccessTest.java
index 04b5386..ce7bf14 100644
--- a/src/test/examples/classmerging/SimpleInterfaceAccessTest.java
+++ b/src/test/examples/classmerging/SimpleInterfaceAccessTest.java
@@ -8,9 +8,35 @@
 
 public class SimpleInterfaceAccessTest {
   public static void main(String[] args) {
-    // It is not possible to merge the interface SimpleInterface into SimpleInterfaceImpl, since
-    // this would lead to an illegal class access here.
-    SimpleInterface obj = SimpleInterfaceImplRetriever.getSimpleInterfaceImpl();
-    obj.foo();
+    // Without access modifications, it is not possible to merge the interface SimpleInterface into
+    // SimpleInterfaceImpl, since this would lead to an illegal class access here.
+    SimpleInterface x = SimpleInterfaceImplRetriever.getSimpleInterfaceImpl();
+    x.foo();
+
+    // Without access modifications, it is not possible to merge the interface OtherSimpleInterface
+    // into OtherSimpleInterfaceImpl, since this could lead to an illegal class access if another
+    // package references OtherSimpleInterface.
+    OtherSimpleInterface y = new OtherSimpleInterfaceImpl();
+    y.bar();
+  }
+
+  // Should only be merged into OtherSimpleInterfaceImpl if access modifications are allowed.
+  public interface SimpleInterface {
+
+    void foo();
+  }
+
+  // Should only be merged into OtherSimpleInterfaceImpl if access modifications are allowed.
+  public interface OtherSimpleInterface {
+
+    void bar();
+  }
+
+  private static class OtherSimpleInterfaceImpl implements OtherSimpleInterface {
+
+    @Override
+    public void bar() {
+      System.out.println("In bar on OtherSimpleInterfaceImpl");
+    }
   }
 }
diff --git a/src/test/examples/classmerging/pkg/SimpleInterfaceImplRetriever.java b/src/test/examples/classmerging/pkg/SimpleInterfaceImplRetriever.java
index 5cfa11e..22391e9 100644
--- a/src/test/examples/classmerging/pkg/SimpleInterfaceImplRetriever.java
+++ b/src/test/examples/classmerging/pkg/SimpleInterfaceImplRetriever.java
@@ -4,7 +4,7 @@
 
 package classmerging.pkg;
 
-import classmerging.SimpleInterface;
+import classmerging.SimpleInterfaceAccessTest.SimpleInterface;
 
 public class SimpleInterfaceImplRetriever {
 
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..f141d36 100644
--- a/src/test/java/com/android/tools/r8/classmerging/ClassMergingTest.java
+++ b/src/test/java/com/android/tools/r8/classmerging/ClassMergingTest.java
@@ -35,7 +35,7 @@
 import java.util.Set;
 import java.util.concurrent.ExecutionException;
 import java.util.function.Consumer;
-import org.junit.Ignore;
+import java.util.function.Predicate;
 import org.junit.Test;
 
 // TODO(christofferqa): Add tests to check that statically typed invocations on method handles
@@ -44,11 +44,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 +113,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 +147,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 +203,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 +223,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 +244,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());
@@ -243,8 +269,10 @@
     String main = "classmerging.SimpleInterfaceAccessTest";
     Path[] programFiles =
         new Path[] {
-          CF_DIR.resolve("SimpleInterface.class"),
           CF_DIR.resolve("SimpleInterfaceAccessTest.class"),
+          CF_DIR.resolve("SimpleInterfaceAccessTest$SimpleInterface.class"),
+          CF_DIR.resolve("SimpleInterfaceAccessTest$OtherSimpleInterface.class"),
+          CF_DIR.resolve("SimpleInterfaceAccessTest$OtherSimpleInterfaceImpl.class"),
           CF_DIR.resolve("pkg/SimpleInterfaceImplRetriever.class"),
           CF_DIR.resolve("pkg/SimpleInterfaceImplRetriever$SimpleInterfaceImpl.class")
         };
@@ -252,14 +280,15 @@
     // is in a different package and is not public.
     ImmutableSet<String> preservedClassNames =
         ImmutableSet.of(
-            "classmerging.SimpleInterface",
             "classmerging.SimpleInterfaceAccessTest",
+            "classmerging.SimpleInterfaceAccessTest$SimpleInterface",
+            "classmerging.SimpleInterfaceAccessTest$OtherSimpleInterface",
+            "classmerging.SimpleInterfaceAccessTest$OtherSimpleInterfaceImpl",
             "classmerging.pkg.SimpleInterfaceImplRetriever",
             "classmerging.pkg.SimpleInterfaceImplRetriever$SimpleInterfaceImpl");
-    runTest(main, programFiles, preservedClassNames);
+    runTest(main, programFiles, preservedClassNames::contains);
   }
 
-  @Ignore("b/73958515")
   @Test
   public void testNoIllegalClassAccessWithAccessModifications() throws Exception {
     // If access modifications are allowed then SimpleInterface should be merged into
@@ -267,14 +296,20 @@
     String main = "classmerging.SimpleInterfaceAccessTest";
     Path[] programFiles =
         new Path[] {
-          CF_DIR.resolve("SimpleInterface.class"),
           CF_DIR.resolve("SimpleInterfaceAccessTest.class"),
+          CF_DIR.resolve("SimpleInterfaceAccessTest$SimpleInterface.class"),
+          CF_DIR.resolve("SimpleInterfaceAccessTest$OtherSimpleInterface.class"),
+          CF_DIR.resolve("SimpleInterfaceAccessTest$OtherSimpleInterfaceImpl.class"),
           CF_DIR.resolve("pkg/SimpleInterfaceImplRetriever.class"),
           CF_DIR.resolve("pkg/SimpleInterfaceImplRetriever$SimpleInterfaceImpl.class")
         };
     ImmutableSet<String> preservedClassNames =
         ImmutableSet.of(
             "classmerging.SimpleInterfaceAccessTest",
+            // TODO(christofferqa): Should be able to merge SimpleInterface into SimpleInterfaceImpl
+            // when access modifications are allowed.
+            "classmerging.SimpleInterfaceAccessTest$SimpleInterface",
+            "classmerging.SimpleInterfaceAccessTest$OtherSimpleInterfaceImpl",
             "classmerging.pkg.SimpleInterfaceImplRetriever",
             "classmerging.pkg.SimpleInterfaceImplRetriever$SimpleInterfaceImpl");
     // Allow access modifications (and prevent SimpleInterfaceImplRetriever from being removed as
@@ -282,7 +317,7 @@
     runTest(
         main,
         programFiles,
-        preservedClassNames,
+        preservedClassNames::contains,
         getProguardConfig(
             EXAMPLE_KEEP,
             "-allowaccessmodification",
@@ -310,7 +345,7 @@
     runTest(
         main,
         programFiles,
-        preservedClassNames,
+        preservedClassNames::contains,
         getProguardConfig(
             EXAMPLE_KEEP, "-keep class classmerging.RewritePinnedMethodTest$A { *; }"));
   }
@@ -327,40 +362,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/DebugStreamComparator.java b/src/test/java/com/android/tools/r8/debug/DebugStreamComparator.java
index 22e8537..eb85a7c 100644
--- a/src/test/java/com/android/tools/r8/debug/DebugStreamComparator.java
+++ b/src/test/java/com/android/tools/r8/debug/DebugStreamComparator.java
@@ -13,7 +13,9 @@
 import com.android.tools.r8.utils.Pair;
 import com.android.tools.r8.utils.StringUtils;
 import com.android.tools.r8.utils.StringUtils.BraceType;
+import java.util.ArrayDeque;
 import java.util.ArrayList;
+import java.util.Deque;
 import java.util.HashMap;
 import java.util.Iterator;
 import java.util.List;
@@ -44,6 +46,60 @@
     }
   }
 
+  private static class StreamState {
+    static final int ENTRY_LINE = -1;
+    static final int PLACEHOLDER_LINE = -2;
+
+    final Iterator<DebuggeeState> iterator;
+    final Deque<Integer> frameEntryLines = new ArrayDeque<>();
+    int currentLine = ENTRY_LINE;
+
+    StreamState(Stream<DebuggeeState> stream) {
+      iterator = stream.iterator();
+    }
+
+    DebuggeeState next() {
+      while (true) {
+        DebuggeeState state = iterator.next();
+        if (state == null) {
+          return null;
+        }
+        int nextDepth = state.getFrameDepth();
+        int nextLine = state.getLineNumber();
+        if (nextDepth == frameEntryLines.size()) {
+          currentLine = nextLine;
+          return state;
+        }
+        if (nextDepth > frameEntryLines.size()) {
+          frameEntryLines.push(currentLine);
+          while (nextDepth > frameEntryLines.size()) {
+            // If the depth grows by more than one we have entered into filtered out frames, eg,
+            // java/android internals. In this case push placeholder lines on the stack.
+            frameEntryLines.push(PLACEHOLDER_LINE);
+          }
+          currentLine = nextLine;
+          assert nextDepth == frameEntryLines.size();
+          return state;
+        }
+        currentLine = nextLine;
+        while (frameEntryLines.size() > nextDepth + 1) {
+          // If the depth decreases by more than one we have popped the filtered frames.
+          // Verify they are placeholder lines.
+          int placeholder = frameEntryLines.pop();
+          assert placeholder == PLACEHOLDER_LINE;
+        }
+        int lineOnEntry = frameEntryLines.pop();
+        assert nextDepth == frameEntryLines.size();
+        if (lineOnEntry != nextLine) {
+          return state;
+        }
+        // A frame was popped and the current line is the same as when the frame was entered.
+        // In this case we advance again to avoid comparing that a function call returns to the
+        // same line (which may not be the case if no stores are needed after the call).
+      }
+    }
+  }
+
   private boolean verifyLines = true;
   private boolean verifyFiles = true;
   private boolean verifyMethods = true;
@@ -140,13 +196,16 @@
   }
 
   private void internal() {
-    List<Iterator<DebuggeeState>> iterators =
-        streams.stream().map(Stream::iterator).collect(Collectors.toList());
+    List<StreamState> streamStates =
+        streams.stream().map(StreamState::new).collect(Collectors.toList());
     while (true) {
-      List<DebuggeeState> states = new ArrayList<>(iterators.size());
+      List<DebuggeeState> states = new ArrayList<>(streamStates.size());
       boolean done = false;
-      for (Iterator<DebuggeeState> iterator : iterators) {
-        DebuggeeState state = iterator.next();
+      for (StreamState streamState : streamStates) {
+        DebuggeeState state;
+        do {
+          state = streamState.next();
+        } while (state != null && !filter.test(state));
         states.add(state);
         if (state == null) {
           done = true;
@@ -159,11 +218,9 @@
               states.stream().allMatch(Objects::isNull));
           return;
         } else {
-          if (filter.test(states.get(0))) {
-            verifyStatesEqual(states);
-            if (printOptions.printStates) {
-              System.out.println(prettyPrintState(states.get(0), printOptions));
-            }
+          verifyStatesEqual(states);
+          if (printOptions.printStates) {
+            System.out.println(prettyPrintState(states.get(0), printOptions));
           }
         }
       } catch (AssertionError e) {
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();
       }
     }
diff --git a/src/test/java/com/android/tools/r8/debug/ExamplesDebugTest.java b/src/test/java/com/android/tools/r8/debug/ExamplesDebugTest.java
index 02e995f..6de20c6 100644
--- a/src/test/java/com/android/tools/r8/debug/ExamplesDebugTest.java
+++ b/src/test/java/com/android/tools/r8/debug/ExamplesDebugTest.java
@@ -75,7 +75,7 @@
 
   @Test
   public void testBridgeMethod() throws Exception {
-    // TODO(b/79671093): D8 has different line number info during stepping.
+    // TODO(b/79671093): D8 has local variables with empty names.
     testDebuggingJvmOnly("bridge", "BridgeMethod");
   }
 
@@ -122,8 +122,7 @@
 
   @Test
   public void testInstanceVariable() throws Exception {
-    // TODO(b/79671093): D8 has different line number info during stepping.
-    testDebuggingJvmOnly("instancevariable", "InstanceVariable");
+    testDebugging("instancevariable", "InstanceVariable");
   }
 
   @Test
@@ -133,8 +132,7 @@
 
   @Test
   public void testInvoke() throws Exception {
-    // TODO(b/79671093): D8 has different line number info during stepping.
-    testDebuggingJvmOnly("invoke", "Invoke");
+    testDebugging("invoke", "Invoke");
   }
 
   @Test
@@ -155,8 +153,7 @@
 
   @Test
   public void testNewArray() throws Exception {
-    // TODO(b/79671093): D8 has different line number info during stepping.
-    testDebuggingJvmOnly("newarray", "NewArray");
+    testDebugging("newarray", "NewArray");
   }
 
   @Test
@@ -166,8 +163,7 @@
 
   @Test
   public void testReturns() throws Exception {
-    // TODO(b/79671093): D8 has different line number info during stepping.
-    testDebuggingJvmOnly("returns", "Returns");
+    testDebugging("returns", "Returns");
   }
 
   @Test
@@ -222,8 +218,7 @@
 
   @Test
   public void testInvokeEmpty() throws Exception {
-    // TODO(b/79671093): D8 has different line number info during stepping.
-    testDebuggingJvmOnly("invokeempty", "InvokeEmpty");
+    testDebugging("invokeempty", "InvokeEmpty");
   }
 
   @Test
@@ -233,21 +228,17 @@
 
   @Test
   public void testRegress2() throws Exception {
-    // TODO(b/79671093): D8 has different line number info during stepping.
-    testDebuggingJvmOnly("regress2", "Regress2");
+    testDebugging("regress2", "Regress2");
   }
 
-  @Ignore("TODO(mathiasr): Different behavior CfSourceCode vs JarSourceCode")
   @Test
   public void testRegress37726195() throws Exception {
-    // TODO(b/79671093): We don't match JVM's behavior on this example.
-    testDebuggingJvmOutputOnly("regress_37726195", "Regress");
+    testDebugging("regress_37726195", "Regress");
   }
 
   @Test
   public void testRegress37658666() throws Exception {
-    // TODO(b/79671093): D8 has different line number info during stepping.
-    testDebuggingJvmOnly("regress_37658666", "Regress");
+    testDebugging("regress_37658666", "Regress");
   }
 
   @Test
@@ -257,8 +248,7 @@
 
   @Test
   public void testRegress37955340() throws Exception {
-    // TODO(b/79671093): D8 has different line number info during stepping.
-    testDebuggingJvmOnly("regress_37955340", "Regress");
+    testDebugging("regress_37955340", "Regress");
   }
 
   @Test
@@ -304,8 +294,7 @@
 
   @Test
   public void testMemberrebinding2() throws Exception {
-    // TODO(b/79671093): D8 has different line number info during stepping.
-    testDebuggingJvmOnly("memberrebinding2", "Memberrebinding");
+    testDebugging("memberrebinding2", "Memberrebinding");
   }
 
   @Test
@@ -315,14 +304,12 @@
 
   @Test
   public void testMinification() throws Exception {
-    // TODO(b/79671093): D8 has different line number info during stepping.
-    testDebuggingJvmOnly("minification", "Minification");
+    testDebugging("minification", "Minification");
   }
 
   @Test
   public void testEnclosingmethod() throws Exception {
-    // TODO(b/79671093): D8 has different line number info during stepping.
-    testDebuggingJvmOnly("enclosingmethod", "Main");
+    testDebugging("enclosingmethod", "Main");
   }
 
   @Test
diff --git a/src/test/java/com/android/tools/r8/resolution/singletarget/one/AbstractTopClass.java b/src/test/java/com/android/tools/r8/resolution/singletarget/one/AbstractTopClass.java
index d9ff675..c745dfa 100644
--- a/src/test/java/com/android/tools/r8/resolution/singletarget/one/AbstractTopClass.java
+++ b/src/test/java/com/android/tools/r8/resolution/singletarget/one/AbstractTopClass.java
@@ -5,33 +5,36 @@
 
 public abstract class AbstractTopClass implements InterfaceWithDefault {
 
+  // Avoid AbstractTopClass.class.getCanonicalName() as it may change during shrinking.
+  private static final String TAG = "AbstractTopClass";
+
   public void singleTargetAtTop() {
-    System.out.println(AbstractTopClass.class.getCanonicalName());
+    System.out.println(TAG);
   }
 
   public void singleShadowingOverride() {
-    System.out.println(AbstractTopClass.class.getCanonicalName());
+    System.out.println(TAG);
   }
 
   public abstract void abstractTargetAtTop();
 
   public void overridenInAbstractClassOnly() {
-    System.out.println(AbstractTopClass.class.getCanonicalName());
+    System.out.println(TAG);
   }
 
   public void overriddenInTwoSubTypes() {
-    System.out.println(AbstractTopClass.class.getCanonicalName());
+    System.out.println(TAG);
   }
 
   public void definedInTwoSubTypes() {
-    System.out.println(AbstractTopClass.class.getCanonicalName());
+    System.out.println(TAG);
   }
 
   public static void staticMethod() {
-    System.out.println(AbstractTopClass.class.getCanonicalName());
+    System.out.println(TAG);
   }
 
   public void overriddenByIrrelevantInterface() {
-    System.out.println(AbstractTopClass.class.getCanonicalName());
+    System.out.println(TAG);
   }
 }
diff --git a/src/test/java/com/android/tools/r8/resolution/singletarget/one/InterfaceWithDefault.java b/src/test/java/com/android/tools/r8/resolution/singletarget/one/InterfaceWithDefault.java
index 1a0c434..f0faedd 100644
--- a/src/test/java/com/android/tools/r8/resolution/singletarget/one/InterfaceWithDefault.java
+++ b/src/test/java/com/android/tools/r8/resolution/singletarget/one/InterfaceWithDefault.java
@@ -5,15 +5,18 @@
 
 public interface InterfaceWithDefault {
 
+  // Avoid InterfaceWithDefault.class.getCanonicalName() as it may change during shrinking.
+  String TAG = "InterfaceWithDefault";
+
   default void defaultMethod() {
-    System.out.println(InterfaceWithDefault.class.getCanonicalName());
+    System.out.println(TAG);
   }
 
   default void overriddenDefault() {
-    System.out.println(InterfaceWithDefault.class.getCanonicalName());
+    System.out.println(TAG);
   }
 
   default void overriddenInOtherInterface() {
-    System.out.println(InterfaceWithDefault.class.getCanonicalName());
+    System.out.println(TAG);
   }
 }
diff --git a/src/test/java/com/android/tools/r8/resolution/singletarget/one/SubSubClassOne.java b/src/test/java/com/android/tools/r8/resolution/singletarget/one/SubSubClassOne.java
index 22be6a4..ff585af 100644
--- a/src/test/java/com/android/tools/r8/resolution/singletarget/one/SubSubClassOne.java
+++ b/src/test/java/com/android/tools/r8/resolution/singletarget/one/SubSubClassOne.java
@@ -5,18 +5,21 @@
 
 public class SubSubClassOne extends AbstractSubClass implements IrrelevantInterfaceWithDefault {
 
+  // Avoid SubSubClassOne.class.getCanonicalName() as it may change during shrinking.
+  private static final String TAG = "SubSubClassOne";
+
   @Override
   public void abstractTargetAtTop() {
-    System.out.println(SubSubClassOne.class.getCanonicalName());
+    System.out.println(TAG);
   }
 
   @Override
   public void overriddenInTwoSubTypes() {
-    System.out.println(SubSubClassOne.class.getCanonicalName());
+    System.out.println(TAG);
   }
 
   @Override
   public void definedInTwoSubTypes() {
-    System.out.println(SubSubClassOne.class.getCanonicalName());
+    System.out.println(TAG);
   }
 }