diff --git a/src/main/java/com/android/tools/r8/GenerateMainDexList.java b/src/main/java/com/android/tools/r8/GenerateMainDexList.java
index 14dd1ae..aafe941 100644
--- a/src/main/java/com/android/tools/r8/GenerateMainDexList.java
+++ b/src/main/java/com/android/tools/r8/GenerateMainDexList.java
@@ -8,7 +8,7 @@
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexApplication;
-import com.android.tools.r8.graph.DexDefinition;
+import com.android.tools.r8.graph.DexReference;
 import com.android.tools.r8.graph.GraphLense;
 import com.android.tools.r8.shaking.DiscardedChecker;
 import com.android.tools.r8.shaking.Enqueuer;
@@ -80,9 +80,9 @@
       }
       // Print -whyareyoukeeping results if any.
       if (whyAreYouKeepingConsumer != null) {
-        for (DexDefinition definition : mainDexRootSet.reasonAsked) {
+        for (DexReference reference : mainDexRootSet.reasonAsked) {
           whyAreYouKeepingConsumer.printWhyAreYouKeeping(
-              enqueuer.getGraphNode(definition), System.out);
+              enqueuer.getGraphNode(reference), System.out);
         }
       }
 
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 8ef9af6..4da9b6e 100644
--- a/src/main/java/com/android/tools/r8/R8.java
+++ b/src/main/java/com/android/tools/r8/R8.java
@@ -13,11 +13,12 @@
 import com.android.tools.r8.experimental.graphinfo.GraphConsumer;
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.AppliedGraphLens;
 import com.android.tools.r8.graph.DexApplication;
 import com.android.tools.r8.graph.DexCallSite;
 import com.android.tools.r8.graph.DexClass;
-import com.android.tools.r8.graph.DexDefinition;
 import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.graph.DexReference;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.GraphLense;
 import com.android.tools.r8.ir.conversion.IRConverter;
@@ -370,7 +371,7 @@
           // We can now remove visibility bridges. Note that we do not need to update the
           // invoke-targets here, as the existing invokes will simply dispatch to the now
           // visible super-method. MemberRebinding, if run, will then dispatch it correctly.
-          application = new VisibilityBridgeRemover(appView.appInfo(), application).run();
+          new VisibilityBridgeRemover(appView.withLiveness()).run();
         }
       }
 
@@ -401,8 +402,10 @@
               SeedMapper.seedMapperFromFile(
                   options.getProguardConfiguration().getApplyMappingFile());
           timing.begin("apply-mapping");
-          appView.setGraphLense(
-              new ProguardMapApplier(appView.withLiveness(), seedMapper).run(timing));
+          GraphLense applyMappingLense =
+              new ProguardMapApplier(appView.withLiveness(), seedMapper).run(timing);
+          rootSet = rootSet.rewrittenWithLense(applyMappingLense);
+          appView.setGraphLense(applyMappingLense);
           application = application.asDirect().rewrittenWithLense(appView.graphLense());
           appView.setAppInfo(
               appView
@@ -473,18 +476,28 @@
             new EnumOrdinalMapCollector(appViewWithLiveness, options).run());
       }
 
+      assert appView.appInfo().hasLiveness();
+
       timing.begin("Create IR");
       Set<DexCallSite> desugaredCallSites;
       CfgPrinter printer = options.printCfg ? new CfgPrinter() : null;
       try {
         IRConverter converter =
-            new IRConverter(appView, options, timing, printer, mainDexClasses, rootSet);
+            new IRConverter(
+                appView.withLiveness(), options, timing, printer, mainDexClasses, rootSet);
         application = converter.optimize(application, executorService);
         desugaredCallSites = converter.getDesugaredCallSites();
       } finally {
         timing.end();
       }
 
+      // At this point all code has been mapped according to the graph lens. We cannot remove the
+      // graph lens entirely, though, since it is needed for mapping all field and method signatures
+      // back to the original program.
+      timing.begin("AppliedGraphLens construction");
+      appView.setGraphLense(new AppliedGraphLens(appView, application.classes()));
+      timing.end();
+
       if (options.printCfg) {
         if (options.printCfgFile == null || options.printCfgFile.isEmpty()) {
           System.out.print(printer.toString());
@@ -527,9 +540,9 @@
               .run();
         }
         if (whyAreYouKeepingConsumer != null) {
-          for (DexDefinition dexDefinition : mainDexRootSet.reasonAsked) {
+          for (DexReference reference : mainDexRootSet.reasonAsked) {
             whyAreYouKeepingConsumer.printWhyAreYouKeeping(
-                enqueuer.getGraphNode(dexDefinition), System.out);
+                enqueuer.getGraphNode(reference), System.out);
           }
         }
       }
@@ -569,9 +582,9 @@
 
             // Print reasons on the application after pruning, so that we reflect the actual result.
             if (whyAreYouKeepingConsumer != null) {
-              for (DexDefinition dexDefinition : rootSet.reasonAsked) {
+              for (DexReference reference : rootSet.reasonAsked) {
                 whyAreYouKeepingConsumer.printWhyAreYouKeeping(
-                    enqueuer.getGraphNode(dexDefinition), System.out);
+                    enqueuer.getGraphNode(reference), System.out);
               }
             }
             // Remove annotations that refer to types that no longer exist.
@@ -632,7 +645,14 @@
 
       // Validity checks.
       assert application.classes().stream().allMatch(DexClass::isValid);
-      assert rootSet.verifyKeptItemsAreKept(application, appView.appInfo(), options);
+      assert rootSet.verifyKeptItemsAreKept(application, appView.appInfo());
+      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/Version.java b/src/main/java/com/android/tools/r8/Version.java
index 20093ab..ee26dd8 100644
--- a/src/main/java/com/android/tools/r8/Version.java
+++ b/src/main/java/com/android/tools/r8/Version.java
@@ -11,7 +11,7 @@
 
   // This field is accessed from release scripts using simple pattern matching.
   // Therefore, changing this field could break our release scripts.
-  public static final String LABEL = "1.4.33";
+  public static final String LABEL = "1.4.34";
 
   private Version() {
   }
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/AppInfo.java b/src/main/java/com/android/tools/r8/graph/AppInfo.java
index c9edb88..028f5a2 100644
--- a/src/main/java/com/android/tools/r8/graph/AppInfo.java
+++ b/src/main/java/com/android/tools/r8/graph/AppInfo.java
@@ -66,6 +66,17 @@
     return app.classesWithDeterministicOrder();
   }
 
+  public DexDefinition definitionFor(DexReference reference) {
+    if (reference.isDexType()) {
+      return definitionFor(reference.asDexType());
+    }
+    if (reference.isDexMethod()) {
+      return definitionFor(reference.asDexMethod());
+    }
+    assert reference.isDexField();
+    return definitionFor(reference.asDexField());
+  }
+
   public DexClass definitionFor(DexType type) {
     return app.definitionFor(type);
   }
diff --git a/src/main/java/com/android/tools/r8/graph/AppView.java b/src/main/java/com/android/tools/r8/graph/AppView.java
index f9a9dde..e232cb9 100644
--- a/src/main/java/com/android/tools/r8/graph/AppView.java
+++ b/src/main/java/com/android/tools/r8/graph/AppView.java
@@ -106,6 +106,11 @@
     }
 
     @Override
+    public VerticallyMergedClasses verticallyMergedClasses() {
+      return AppView.this.verticallyMergedClasses();
+    }
+
+    @Override
     public AppView<AppInfoWithLiveness> withLiveness() {
       return this;
     }
diff --git a/src/main/java/com/android/tools/r8/graph/AppliedGraphLens.java b/src/main/java/com/android/tools/r8/graph/AppliedGraphLens.java
new file mode 100644
index 0000000..d2387f4
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/graph/AppliedGraphLens.java
@@ -0,0 +1,138 @@
+// Copyright (c) 2019, 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.ir.code.Invoke;
+import com.google.common.collect.BiMap;
+import com.google.common.collect.HashBiMap;
+import java.util.IdentityHashMap;
+import java.util.List;
+import java.util.Map;
+
+/**
+ * A graph lens that will not lead to any code rewritings in the {@link
+ * com.android.tools.r8.ir.conversion.LensCodeRewriter}, or parameter removals in the {@link
+ * com.android.tools.r8.ir.conversion.IRBuilder}.
+ *
+ * <p>The mappings from the original program to the generated program are kept, though.
+ */
+public class AppliedGraphLens extends GraphLense {
+
+  private final AppView<? extends AppInfo> appView;
+
+  private final BiMap<DexType, DexType> originalTypeNames = HashBiMap.create();
+  private final BiMap<DexField, DexField> originalFieldSignatures = HashBiMap.create();
+  private final BiMap<DexMethod, DexMethod> originalMethodSignatures = HashBiMap.create();
+  private final Map<DexMethod, DexMethod> originalMethodSignaturesForBridges =
+      new IdentityHashMap<>();
+
+  public AppliedGraphLens(
+      AppView<? extends AppInfoWithSubtyping> appView, List<DexProgramClass> classes) {
+    this.appView = appView;
+
+    for (DexProgramClass clazz : classes) {
+      // Record original type names.
+      {
+        DexType type = clazz.type;
+        if (appView.verticallyMergedClasses() != null
+            && !appView.verticallyMergedClasses().hasBeenMergedIntoSubtype(type)) {
+          DexType original = appView.graphLense().getOriginalType(type);
+          if (original != type) {
+            DexType existing = originalTypeNames.forcePut(type, original);
+            assert existing == null;
+          }
+        }
+      }
+
+      // Record original field signatures.
+      for (DexEncodedField encodedField : clazz.fields()) {
+        DexField field = encodedField.field;
+        DexField original = appView.graphLense().getOriginalFieldSignature(field);
+        if (original != field) {
+          DexField existing = originalFieldSignatures.forcePut(field, original);
+          assert existing == null;
+        }
+      }
+
+      // Record original method signatures.
+      for (DexEncodedMethod encodedMethod : clazz.methods()) {
+        DexMethod method = encodedMethod.method;
+        DexMethod original = appView.graphLense().getOriginalMethodSignature(method);
+        if (original != method) {
+          DexMethod existing = originalMethodSignatures.inverse().get(original);
+          if (existing == null) {
+            originalMethodSignatures.put(method, original);
+          } else {
+            DexMethod renamed = getRenamedMethodSignature(original);
+            if (renamed == existing) {
+              originalMethodSignaturesForBridges.put(method, original);
+            } else {
+              originalMethodSignatures.forcePut(method, original);
+              originalMethodSignaturesForBridges.put(existing, original);
+            }
+          }
+        }
+      }
+    }
+  }
+
+  @Override
+  public DexType getOriginalType(DexType type) {
+    return originalTypeNames.getOrDefault(type, type);
+  }
+
+  @Override
+  public DexField getOriginalFieldSignature(DexField field) {
+    return originalFieldSignatures.getOrDefault(field, field);
+  }
+
+  @Override
+  public DexMethod getOriginalMethodSignature(DexMethod method) {
+    if (originalMethodSignaturesForBridges.containsKey(method)) {
+      return originalMethodSignaturesForBridges.get(method);
+    }
+    return originalMethodSignatures.getOrDefault(method, method);
+  }
+
+  @Override
+  public DexField getRenamedFieldSignature(DexField originalField) {
+    return originalFieldSignatures.inverse().getOrDefault(originalField, originalField);
+  }
+
+  @Override
+  public DexMethod getRenamedMethodSignature(DexMethod originalMethod) {
+    return originalMethodSignatures.inverse().getOrDefault(originalMethod, originalMethod);
+  }
+
+  @Override
+  public DexType lookupType(DexType type) {
+    if (appView.verticallyMergedClasses() != null
+        && appView.verticallyMergedClasses().hasBeenMergedIntoSubtype(type)) {
+      return lookupType(appView.verticallyMergedClasses().getTargetFor(type));
+    }
+    return originalTypeNames.inverse().getOrDefault(type, type);
+  }
+
+  @Override
+  public GraphLenseLookupResult lookupMethod(
+      DexMethod method, DexMethod context, Invoke.Type type) {
+    return new GraphLenseLookupResult(method, type);
+  }
+
+  @Override
+  public RewrittenPrototypeDescription lookupPrototypeChanges(DexMethod method) {
+    return RewrittenPrototypeDescription.none();
+  }
+
+  @Override
+  public DexField lookupField(DexField field) {
+    return field;
+  }
+
+  @Override
+  public boolean isContextFreeForMethods() {
+    return true;
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/graph/DexCode.java b/src/main/java/com/android/tools/r8/graph/DexCode.java
index b754c9a..fab4a83 100644
--- a/src/main/java/com/android/tools/r8/graph/DexCode.java
+++ b/src/main/java/com/android/tools/r8/graph/DexCode.java
@@ -193,7 +193,15 @@
             graphLense.getOriginalMethodSignature(encodedMethod.method),
             null,
             appInfo);
-    IRBuilder builder = new IRBuilder(encodedMethod, appInfo, source, options, origin);
+    IRBuilder builder =
+        new IRBuilder(
+            encodedMethod,
+            appInfo,
+            source,
+            options,
+            origin,
+            new ValueNumberGenerator(),
+            graphLense);
     return builder.build(encodedMethod);
   }
 
diff --git a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
index acf3e05..7a33ba4 100644
--- a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
+++ b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
@@ -260,6 +260,10 @@
   public final DexProto twrCloseResourceMethodProto =
       createProto(voidType, throwableType, autoCloseableType);
 
+  public final DexString deserializeLambdaMethodName = createString("$deserializeLambda$");
+  public final DexProto deserializeLambdaMethodProto =
+      createProto(objectType, createType("Ljava/lang/invoke/SerializedLambda;"));
+
   // Dex system annotations.
   // See https://source.android.com/devices/tech/dalvik/dex-format.html#system-annotation
   public final DexType annotationDefault = createType("Ldalvik/annotation/AnnotationDefault;");
diff --git a/src/main/java/com/android/tools/r8/graph/DexMethod.java b/src/main/java/com/android/tools/r8/graph/DexMethod.java
index 3aba90c..bd86c12 100644
--- a/src/main/java/com/android/tools/r8/graph/DexMethod.java
+++ b/src/main/java/com/android/tools/r8/graph/DexMethod.java
@@ -185,6 +185,11 @@
     return builder.toString();
   }
 
+  public boolean isLambdaDeserializeMethod(DexItemFactory dexItemFactory) {
+    return name == dexItemFactory.deserializeLambdaMethodName
+        && proto == dexItemFactory.deserializeLambdaMethodProto;
+  }
+
   synchronized public void setSingleVirtualMethodCache(
       DexType receiverType, DexEncodedMethod method) {
     if (singleTargetCache == null) {
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 d5e2fed..0c48ea9 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;
@@ -442,6 +448,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 c6a527f..884df4f 100644
--- a/src/main/java/com/android/tools/r8/graph/GraphLense.java
+++ b/src/main/java/com/android/tools/r8/graph/GraphLense.java
@@ -10,11 +10,16 @@
 import com.android.tools.r8.utils.IteratorUtils;
 import com.google.common.collect.BiMap;
 import com.google.common.collect.HashBiMap;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
 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;
@@ -22,6 +27,9 @@
 import java.util.ListIterator;
 import java.util.Map;
 import java.util.Set;
+import java.util.SortedSet;
+import java.util.TreeSet;
+import java.util.function.Function;
 
 /**
  * A GraphLense implements a virtual view on top of the graph, used to delay global rewrites until
@@ -478,6 +486,23 @@
     return true;
   }
 
+  public ImmutableList<DexReference> rewriteReferencesConservatively(List<DexReference> original) {
+    ImmutableList.Builder<DexReference> builder = ImmutableList.builder();
+    for (DexReference item : original) {
+      if (item.isDexMethod()) {
+        DexMethod method = item.asDexMethod();
+        if (isContextFreeForMethod(method)) {
+          builder.add(lookupMethod(method));
+        } else {
+          builder.addAll(lookupMethodInAllContexts(method));
+        }
+      } else {
+        builder.add(lookupReference(item));
+      }
+    }
+    return builder.build();
+  }
+
   public ImmutableSet<DexReference> rewriteReferencesConservatively(Set<DexReference> original) {
     ImmutableSet.Builder<DexReference> builder = ImmutableSet.builder();
     for (DexReference item : original) {
@@ -495,6 +520,23 @@
     return builder.build();
   }
 
+  public Set<DexReference> rewriteMutableReferencesConservatively(Set<DexReference> original) {
+    Set<DexReference> result = Sets.newIdentityHashSet();
+    for (DexReference item : original) {
+      if (item.isDexMethod()) {
+        DexMethod method = item.asDexMethod();
+        if (isContextFreeForMethod(method)) {
+          result.add(lookupMethod(method));
+        } else {
+          result.addAll(lookupMethodInAllContexts(method));
+        }
+      } else {
+        result.add(lookupReference(item));
+      }
+    }
+    return result;
+  }
+
   public Object2BooleanMap<DexReference> rewriteReferencesConservatively(
       Object2BooleanMap<DexReference> original) {
     Object2BooleanMap<DexReference> result = new Object2BooleanArrayMap<>();
@@ -516,6 +558,22 @@
     return result;
   }
 
+  public ImmutableSet<DexType> rewriteTypesConservatively(Set<DexType> original) {
+    ImmutableSet.Builder<DexType> builder = ImmutableSet.builder();
+    for (DexType item : original) {
+      builder.add(lookupType(item));
+    }
+    return builder.build();
+  }
+
+  public Set<DexType> rewriteMutableTypesConservatively(Set<DexType> original) {
+    Set<DexType> result = Sets.newIdentityHashSet();
+    for (DexType item : original) {
+      result.add(lookupType(item));
+    }
+    return result;
+  }
+
   public ImmutableSortedSet<DexMethod> rewriteMethodsWithRenamedSignature(Set<DexMethod> methods) {
     ImmutableSortedSet.Builder<DexMethod> builder =
         new ImmutableSortedSet.Builder<>(PresortedComparable::slowCompare);
@@ -547,6 +605,121 @@
     return builder.build();
   }
 
+  public SortedSet<DexMethod> rewriteMutableMethodsConservatively(Set<DexMethod> original) {
+    SortedSet<DexMethod> result = new TreeSet<>(PresortedComparable::slowCompare);
+    if (isContextFreeForMethods()) {
+      for (DexMethod item : original) {
+        result.add(lookupMethod(item));
+      }
+    } else {
+      for (DexMethod item : original) {
+        // Avoid using lookupMethodInAllContexts when possible.
+        if (isContextFreeForMethod(item)) {
+          result.add(lookupMethod(item));
+        } else {
+          // The lense is context sensitive, but we do not have the context here. Therefore, we
+          // conservatively look up the method in all contexts.
+          result.addAll(lookupMethodInAllContexts(item));
+        }
+      }
+    }
+    return result;
+  }
+
+  public static <T extends DexReference, S> ImmutableMap<T, S> rewriteReferenceKeys(
+      Map<T, S> original, Function<T, T> rewrite) {
+    ImmutableMap.Builder<T, S> builder = new ImmutableMap.Builder<>();
+    for (T item : original.keySet()) {
+      builder.put(rewrite.apply(item), original.get(item));
+    }
+    return builder.build();
+  }
+
+  public static <T extends DexReference, S> Map<T, S> rewriteMutableReferenceKeys(
+      Map<T, S> original, Function<T, T> rewrite) {
+    Map<T, S> result = new IdentityHashMap<>();
+    for (T item : original.keySet()) {
+      result.put(rewrite.apply(item), original.get(item));
+    }
+    return result;
+  }
+
+  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/code/InvokeStatic.java b/src/main/java/com/android/tools/r8/ir/code/InvokeStatic.java
index a852d28..d5f86fa 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeStatic.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeStatic.java
@@ -105,8 +105,8 @@
   }
 
   @Override
-  public InlineAction computeInlining(InliningOracle decider, DexType inocationContext) {
-    return decider.computeForInvokeStatic(this, inocationContext);
+  public InlineAction computeInlining(InliningOracle decider, DexType invocationContext) {
+    return decider.computeForInvokeStatic(this, invocationContext);
   }
 
   @Override
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 9cb4d46..0343e8a 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
@@ -160,7 +160,7 @@
       InternalOptions options,
       Timing timing,
       CfgPrinter printer,
-      AppView<? extends AppInfoWithSubtyping> appView,
+      AppView<? extends AppInfoWithLiveness> appView,
       MainDexClasses mainDexClasses,
       RootSet rootSet) {
     assert appInfo != null;
@@ -180,8 +180,9 @@
     this.stringConcatRewriter = new StringConcatRewriter(appInfo);
     this.lambdaRewriter = options.enableDesugaring ? new LambdaRewriter(this) : null;
     this.interfaceMethodRewriter =
-        (options.enableDesugaring && enableInterfaceMethodDesugaring())
-            ? new InterfaceMethodRewriter(this, options) : null;
+        options.isInterfaceMethodDesugaringEnabled()
+            ? new InterfaceMethodRewriter(appView, this, options)
+            : null;
     this.twrCloseResourceRewriter =
         (options.enableDesugaring && enableTwrCloseResourceDesugaring())
             ? new TwrCloseResourceRewriter(this) : null;
@@ -276,7 +277,7 @@
    * Create an IR converter for processing methods with full program optimization enabled.
    */
   public IRConverter(
-      AppView<AppInfoWithSubtyping> appView,
+      AppView<? extends AppInfoWithLiveness> appView,
       InternalOptions options,
       Timing timing,
       CfgPrinter printer,
@@ -285,16 +286,6 @@
     this(appView.appInfo(), options, timing, printer, appView, mainDexClasses, rootSet);
   }
 
-  private boolean enableInterfaceMethodDesugaring() {
-    switch (options.interfaceMethodDesugaring) {
-      case Off:
-        return false;
-      case Auto:
-        return !options.canUseDefaultAndStaticInterfaceMethods();
-    }
-    throw new Unreachable();
-  }
-
   private boolean enableTwrCloseResourceDesugaring() {
     return enableTryWithResourcesDesugaring() && !options.canUseTwrCloseResourceMethod();
   }
@@ -327,10 +318,11 @@
     );
   }
 
-  private void removeLambdaDeserializationMethods() {
+  private boolean removeLambdaDeserializationMethods() {
     if (lambdaRewriter != null) {
-      lambdaRewriter.removeLambdaDeserializationMethods(appInfo.classes());
+      return lambdaRewriter.removeLambdaDeserializationMethods(appInfo.classes());
     }
+    return false;
   }
 
   private void synthesizeLambdaClasses(Builder<?> builder, ExecutorService executorService)
@@ -538,8 +530,13 @@
 
   public DexApplication optimize(DexApplication application, ExecutorService executorService)
       throws ExecutionException {
+    if (options.enableTreeShaking) {
+      assert !removeLambdaDeserializationMethods();
+    } else {
+      removeLambdaDeserializationMethods();
+    }
+
     computeReachabilitySensitivity(application);
-    removeLambdaDeserializationMethods();
     collectLambdaMergingCandidates(application);
     collectStaticizerCandidates(application);
 
@@ -1190,8 +1187,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/InterfaceMethodRewriter.java b/src/main/java/com/android/tools/r8/ir/desugar/InterfaceMethodRewriter.java
index a9a571f..e79017d 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
@@ -32,6 +32,7 @@
 import com.android.tools.r8.ir.conversion.IRConverter;
 import com.android.tools.r8.ir.desugar.DefaultMethodsHelper.Collection;
 import com.android.tools.r8.origin.Origin;
+import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.StringDiagnostic;
 import com.google.common.collect.Sets;
@@ -78,6 +79,7 @@
   public static final String DEFAULT_METHOD_PREFIX = "$default$";
   public static final String PRIVATE_METHOD_PREFIX = "$private$";
 
+  private final AppView<? extends AppInfoWithLiveness> appView;
   private final IRConverter converter;
   private final InternalOptions options;
   final DexItemFactory factory;
@@ -112,8 +114,12 @@
     ExcludeDexResources
   }
 
-  public InterfaceMethodRewriter(IRConverter converter, InternalOptions options) {
+  public InterfaceMethodRewriter(
+      AppView<? extends AppInfoWithLiveness> appView,
+      IRConverter converter,
+      InternalOptions options) {
     assert converter != null;
+    this.appView = appView;
     this.converter = converter;
     this.options = options;
     this.factory = options.itemFactory;
@@ -429,7 +435,7 @@
 
   private Map<DexType, DexProgramClass> processInterfaces(Builder<?> builder, Flavor flavour) {
     NestedGraphLense.Builder graphLensBuilder = GraphLense.builder();
-    InterfaceProcessor processor = new InterfaceProcessor(this);
+    InterfaceProcessor processor = new InterfaceProcessor(appView, this);
     for (DexProgramClass clazz : builder.getProgramClasses()) {
       if (shouldProcess(clazz, flavour, true)) {
         processor.process(clazz.asProgramClass(), graphLensBuilder);
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 f39e1df..afe0c8e 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
@@ -11,6 +11,7 @@
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.errors.CompilationError;
 import com.android.tools.r8.errors.Unimplemented;
+import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.ClassAccessFlags;
 import com.android.tools.r8.graph.Code;
 import com.android.tools.r8.graph.DexAnnotationSet;
@@ -30,6 +31,7 @@
 import com.android.tools.r8.ir.synthetic.ForwardMethodSourceCode;
 import com.android.tools.r8.ir.synthetic.SynthesizedCode;
 import com.android.tools.r8.origin.SynthesizedOrigin;
+import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
 import java.util.ArrayDeque;
 import java.util.ArrayList;
 import java.util.Collections;
@@ -47,11 +49,16 @@
 //
 // Also moves static interface methods into a companion class.
 final class InterfaceProcessor {
+
+  private final AppView<? extends AppInfoWithLiveness> appView;
   private final InterfaceMethodRewriter rewriter;
+
   // All created companion and dispatch classes indexed by interface type.
   final Map<DexType, DexProgramClass> syntheticClasses = new IdentityHashMap<>();
 
-  InterfaceProcessor(InterfaceMethodRewriter rewriter) {
+  InterfaceProcessor(
+      AppView<? extends AppInfoWithLiveness> appView, InterfaceMethodRewriter rewriter) {
+    this.appView = appView;
     this.rewriter = rewriter;
   }
 
@@ -106,7 +113,7 @@
       }
     }
 
-    // If at least one bridge methods was removed update the table.
+    // If at least one bridge method was removed then update the table.
     if (remainingMethods.size() < iface.virtualMethods().length) {
       iface.setVirtualMethods(remainingMethods.toArray(
           new DexEncodedMethod[remainingMethods.size()]));
@@ -304,6 +311,9 @@
   // methods. Bridge methods that does not override an implementation in a super-interface must
   // also be kept (such a situation can happen if the vertical class merger merges two interfaces).
   private boolean interfaceMethodRemovalChangesApi(DexEncodedMethod method, DexClass iface) {
+    if (appView != null && appView.appInfo().isPinned(method.method)) {
+      return true;
+    }
     if (method.accessFlags.isBridge()) {
       Deque<DexType> worklist = new ArrayDeque<>();
       Set<DexType> seenBefore = new HashSet<>();
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/LambdaClass.java b/src/main/java/com/android/tools/r8/ir/desugar/LambdaClass.java
index bf36c20..b78f6df 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/LambdaClass.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/LambdaClass.java
@@ -517,11 +517,6 @@
       for (int i = 0; i < directMethods.length; i++) {
         DexEncodedMethod encodedMethod = directMethods[i];
         if (implMethod.match(encodedMethod)) {
-          // Check that this method is synthetic, since this implies that the method cannot be kept
-          // by an explicit -keep rule. This is necessary because we could otherwise be changing
-          // the signature of a kept method here, which is not allowed (see b/120971047).
-          assert encodedMethod.accessFlags.isSynthetic();
-
           // We need to create a new static method with the same code to be able to safely
           // relax its accessibility without making it virtual.
           MethodAccessFlags newAccessFlags = encodedMethod.accessFlags.copy();
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/LambdaDescriptor.java b/src/main/java/com/android/tools/r8/ir/desugar/LambdaDescriptor.java
index 6836ad3..235c96d 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/LambdaDescriptor.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/LambdaDescriptor.java
@@ -152,7 +152,7 @@
   }
 
   /** If the lambda delegates to lambda$ method. */
-  boolean delegatesToLambdaImplMethod() {
+  public boolean delegatesToLambdaImplMethod() {
     DexString methodName = implHandle.asMethod().name;
     return methodName.toString().startsWith(LambdaRewriter.EXPECTED_LAMBDA_METHOD_PREFIX);
   }
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 5814486..eba995f 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
@@ -45,12 +45,10 @@
  * lambda class generation, and instruction patching.
  */
 public class LambdaRewriter {
-  private static final String SERIALIZED_LAMBDA_TYPE_DESCR = "Ljava/lang/invoke/SerializedLambda;";
-
-  private static final String DESERIALIZE_LAMBDA_METHOD_NAME = "$deserializeLambda$";
 
   // 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";
 
@@ -64,9 +62,6 @@
   final DexString classConstructorName;
   final DexString instanceFieldName;
 
-  final DexString deserializeLambdaMethodName;
-  final DexProto deserializeLambdaMethodProto;
-
   final BiMap<DexMethod, DexMethod> methodMapping = HashBiMap.create();
 
   // Maps call sites seen so far to inferred lambda descriptor. It is intended
@@ -96,10 +91,6 @@
     this.objectInitMethod = factory.createMethod(factory.objectType, initProto, constructorName);
     this.classConstructorName = factory.createString(Constants.CLASS_INITIALIZER_NAME);
     this.instanceFieldName = factory.createString(LAMBDA_INSTANCE_FIELD_NAME);
-
-    this.deserializeLambdaMethodName = factory.createString(DESERIALIZE_LAMBDA_METHOD_NAME);
-    this.deserializeLambdaMethodProto = factory.createProto(
-        factory.objectType, factory.createType(SERIALIZED_LAMBDA_TYPE_DESCR));
   }
 
   /**
@@ -136,7 +127,8 @@
   }
 
   /** Remove lambda deserialization methods. */
-  public void removeLambdaDeserializationMethods(Iterable<DexProgramClass> classes) {
+  public boolean removeLambdaDeserializationMethods(Iterable<DexProgramClass> classes) {
+    boolean anyRemoved = false;
     for (DexProgramClass clazz : classes) {
       // Search for a lambda deserialization method and remove it if found.
       DexEncodedMethod[] directMethods = clazz.directMethods();
@@ -145,8 +137,7 @@
         for (int i = 0; i < methodCount; i++) {
           DexEncodedMethod encoded = directMethods[i];
           DexMethod method = encoded.method;
-          if (method.name == deserializeLambdaMethodName &&
-              method.proto == deserializeLambdaMethodProto) {
+          if (method.isLambdaDeserializeMethod(appInfo.dexItemFactory)) {
             assert encoded.accessFlags.isStatic();
             assert encoded.accessFlags.isSynthetic();
 
@@ -155,12 +146,15 @@
             System.arraycopy(directMethods, i + 1, newMethods, i, methodCount - i - 1);
             clazz.setDirectMethods(newMethods);
 
+            anyRemoved = true;
+
             // We assume there is only one such method in the class.
             break;
           }
         }
       }
     }
+    return anyRemoved;
   }
 
   /**
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java b/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
index e3257d5..a07410c 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
@@ -1889,7 +1889,7 @@
             String name = null;
             if (invokedMethod == appInfo.dexItemFactory.classMethods.getName) {
               if (code.options.enableMinification
-                  && !converter.rootSet.noObfuscation.contains(holder)) {
+                  && !converter.rootSet.noObfuscation.contains(holderType)) {
                 deferred = new DexItemBasedValueString(
                     holderType, new ClassNameComputationInfo(NAME));
               } else {
@@ -1899,7 +1899,7 @@
               // TODO(b/119426668): desugar Type#getTypeName
             } else if (invokedMethod == appInfo.dexItemFactory.classMethods.getCanonicalName) {
               if (code.options.enableMinification
-                  && !converter.rootSet.noObfuscation.contains(holder)) {
+                  && !converter.rootSet.noObfuscation.contains(holderType)) {
                 deferred = new DexItemBasedValueString(
                     holderType, new ClassNameComputationInfo(CANONICAL_NAME));
               } else {
@@ -1907,7 +1907,7 @@
               }
             } else if (invokedMethod == appInfo.dexItemFactory.classMethods.getSimpleName) {
               if (code.options.enableMinification
-                  && !converter.rootSet.noObfuscation.contains(holder)) {
+                  && !converter.rootSet.noObfuscation.contains(holderType)) {
                 deferred = new DexItemBasedValueString(
                     holderType, new ClassNameComputationInfo(SIMPLE_NAME));
               } else {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/MemberValuePropagation.java b/src/main/java/com/android/tools/r8/ir/optimize/MemberValuePropagation.java
index 41faa04..434bb04 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/MemberValuePropagation.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/MemberValuePropagation.java
@@ -6,13 +6,14 @@
 import com.android.tools.r8.errors.CompilationError;
 import com.android.tools.r8.graph.DebugLocalInfo;
 import com.android.tools.r8.graph.DexClass;
+import com.android.tools.r8.graph.DexDefinition;
 import com.android.tools.r8.graph.DexEncodedField;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexEncodedMethod.TrivialInitializer;
 import com.android.tools.r8.graph.DexEncodedMethod.TrivialInitializer.TrivialClassInitializer;
 import com.android.tools.r8.graph.DexField;
-import com.android.tools.r8.graph.DexItem;
 import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexReference;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.ir.analysis.type.TypeAnalysis;
 import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
@@ -56,12 +57,16 @@
     this.appInfo = appInfo;
   }
 
-  private ProguardMemberRuleLookup lookupMemberRule(DexItem item) {
-    ProguardMemberRule rule = appInfo.noSideEffects.get(item);
+  private ProguardMemberRuleLookup lookupMemberRule(DexDefinition definition) {
+    if (definition == null) {
+      return null;
+    }
+    DexReference reference = definition.toReference();
+    ProguardMemberRule rule = appInfo.noSideEffects.get(reference);
     if (rule != null) {
       return new ProguardMemberRuleLookup(RuleType.ASSUME_NO_SIDE_EFFECTS, rule);
     }
-    rule = appInfo.assumedValues.get(item);
+    rule = appInfo.assumedValues.get(reference);
     if (rule != null) {
       return new ProguardMemberRuleLookup(RuleType.ASSUME_VALUES, rule);
     }
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/ClassNameMinifier.java b/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java
index b02801c..e53f959 100644
--- a/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java
@@ -87,12 +87,10 @@
     this.classDictionary = options.getProguardConfiguration().getClassObfuscationDictionary();
     this.keepInnerClassStructure = options.getProguardConfiguration().getKeepAttributes().signature;
     this.noObfuscationTypes =
-        DexReference.filterDexType(
-            DexDefinition.mapToReference(rootSet.noObfuscation.stream()))
+        DexReference.filterDexType(rootSet.noObfuscation.stream())
             .collect(Collectors.toSet());
     this.keepPackageName =
-        DexReference.filterDexType(
-            DexDefinition.mapToReference(rootSet.keepPackageName.stream()))
+        DexReference.filterDexType(rootSet.keepPackageName.stream())
             .collect(Collectors.toSet());
 
     // Initialize top-level naming state.
diff --git a/src/main/java/com/android/tools/r8/naming/FieldNameMinifier.java b/src/main/java/com/android/tools/r8/naming/FieldNameMinifier.java
index b589aa4..bbb3391 100644
--- a/src/main/java/com/android/tools/r8/naming/FieldNameMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/FieldNameMinifier.java
@@ -72,8 +72,8 @@
       DexEncodedField encodedField,
       NamingState<DexType, ?> state,
       boolean isLibrary) {
-    if (isLibrary || rootSet.noObfuscation.contains(encodedField)) {
-      DexField field = encodedField.field;
+    DexField field = encodedField.field;
+    if (isLibrary || rootSet.noObfuscation.contains(field)) {
       state.reserveName(field.name, field.type);
     }
   }
diff --git a/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java b/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java
index df11ba9..5f990ac 100644
--- a/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java
@@ -479,11 +479,12 @@
     return state;
   }
 
-  private void reserveNamesForMethod(DexEncodedMethod method,
-      boolean keepAll, NamingState<DexProto, ?> state) {
+  private void reserveNamesForMethod(
+      DexEncodedMethod encodedMethod, boolean keepAll, NamingState<DexProto, ?> state) {
+    DexMethod method = encodedMethod.method;
     if (keepAll || rootSet.noObfuscation.contains(method)) {
-      state.reserveName(method.method.name, method.method.proto);
-      globalState.reserveName(method.method.name, method.method.proto);
+      state.reserveName(method.name, method.proto);
+      globalState.reserveName(method.name, method.proto);
     }
   }
 
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/optimize/VisibilityBridgeRemover.java b/src/main/java/com/android/tools/r8/optimize/VisibilityBridgeRemover.java
index debba04..59caf25 100644
--- a/src/main/java/com/android/tools/r8/optimize/VisibilityBridgeRemover.java
+++ b/src/main/java/com/android/tools/r8/optimize/VisibilityBridgeRemover.java
@@ -3,87 +3,89 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.optimize;
 
-import com.android.tools.r8.graph.AppInfoWithSubtyping;
-import com.android.tools.r8.graph.DexApplication;
-import com.android.tools.r8.graph.DexClass;
+import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexMethod;
-import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.MethodAccessFlags;
 import com.android.tools.r8.logging.Log;
 import com.android.tools.r8.optimize.InvokeSingleTargetExtractor.InvokeKind;
+import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
 import com.google.common.collect.Sets;
 import java.util.Arrays;
-import java.util.List;
 import java.util.Set;
-import java.util.stream.Collectors;
 
 public class VisibilityBridgeRemover {
-  private final AppInfoWithSubtyping appInfo;
-  private final DexApplication application;
-  private final Set<DexEncodedMethod> unneededVisibilityBridges = Sets.newIdentityHashSet();
 
-  public VisibilityBridgeRemover(AppInfoWithSubtyping appInfo, DexApplication application) {
-    this.appInfo = appInfo;
-    this.application = application;
+  private final AppView<? extends AppInfoWithLiveness> appView;
+
+  public VisibilityBridgeRemover(AppView<? extends AppInfoWithLiveness> appView) {
+    this.appView = appView;
   }
 
-  private void identifyBridgeMethod(DexEncodedMethod method) {
+  private void removeUnneededVisibilityBridgesFromClass(DexProgramClass clazz) {
+    clazz.setDirectMethods(removeUnneededVisibilityBridges(clazz.directMethods()));
+    clazz.setVirtualMethods(removeUnneededVisibilityBridges(clazz.virtualMethods()));
+  }
+
+  private DexEncodedMethod[] removeUnneededVisibilityBridges(DexEncodedMethod[] methods) {
+    Set<DexEncodedMethod> methodsToBeRemoved = null;
+    for (DexEncodedMethod method : methods) {
+      if (isUnneededVisibilityBridge(method)) {
+        if (methodsToBeRemoved == null) {
+          methodsToBeRemoved = Sets.newIdentityHashSet();
+        }
+        methodsToBeRemoved.add(method);
+      }
+    }
+    if (methodsToBeRemoved != null) {
+      Set<DexEncodedMethod> finalMethodsToBeRemoved = methodsToBeRemoved;
+      return Arrays.stream(methods)
+          .filter(method -> !finalMethodsToBeRemoved.contains(method))
+          .toArray(DexEncodedMethod[]::new);
+    }
+    return methods;
+  }
+
+  private boolean isUnneededVisibilityBridge(DexEncodedMethod method) {
+    if (appView.appInfo().isPinned(method.method)) {
+      return false;
+    }
     MethodAccessFlags accessFlags = method.accessFlags;
-    if (accessFlags.isBridge() && !accessFlags.isAbstract()) {
-      InvokeSingleTargetExtractor targetExtractor =
-          new InvokeSingleTargetExtractor(appInfo.dexItemFactory);
-      method.getCode().registerCodeReferences(targetExtractor);
-      DexMethod target = targetExtractor.getTarget();
-      InvokeKind kind = targetExtractor.getKind();
-      // javac-generated visibility forward bridge method has same descriptor (name, signature and
-      // return type).
-      if (target != null && target.hasSameProtoAndName(method.method)) {
-        assert !accessFlags.isPrivate() && !accessFlags.isConstructor();
-        if (kind == InvokeKind.SUPER) {
-          // This is a visibility forward, so check for the direct target.
-          DexEncodedMethod targetMethod =
-              appInfo.resolveMethod(target.getHolder(), target).asSingleTarget();
-          if (targetMethod != null && targetMethod.accessFlags.isPublic()) {
-            if (Log.ENABLED) {
-              Log.info(getClass(), "Removing visibility forwarding %s -> %s", method.method,
-                  targetMethod.method);
-            }
-            unneededVisibilityBridges.add(method);
+    if (!accessFlags.isBridge() || accessFlags.isAbstract()) {
+      return false;
+    }
+    InvokeSingleTargetExtractor targetExtractor =
+        new InvokeSingleTargetExtractor(appView.dexItemFactory());
+    method.getCode().registerCodeReferences(targetExtractor);
+    DexMethod target = targetExtractor.getTarget();
+    InvokeKind kind = targetExtractor.getKind();
+    // javac-generated visibility forward bridge method has same descriptor (name, signature and
+    // return type).
+    if (target != null && target.hasSameProtoAndName(method.method)) {
+      assert !accessFlags.isPrivate() && !accessFlags.isConstructor();
+      if (kind == InvokeKind.SUPER) {
+        // This is a visibility forward, so check for the direct target.
+        DexEncodedMethod targetMethod =
+            appView.appInfo().resolveMethod(target.getHolder(), target).asSingleTarget();
+        if (targetMethod != null && targetMethod.accessFlags.isPublic()) {
+          if (Log.ENABLED) {
+            Log.info(
+                getClass(),
+                "Removing visibility forwarding %s -> %s",
+                method.method,
+                targetMethod.method);
           }
+          return true;
         }
       }
     }
+    return false;
   }
 
-  private void removeUnneededVisibilityBridges() {
-    Set<DexType> classes = unneededVisibilityBridges.stream()
-        .map(method -> method.method.getHolder())
-        .collect(Collectors.toSet());
-    for (DexType type : classes) {
-      DexClass clazz = appInfo.definitionFor(type);
-      clazz.setVirtualMethods(removeMethods(clazz.virtualMethods(), unneededVisibilityBridges));
+  public void run() {
+    for (DexProgramClass clazz : appView.appInfo().classes()) {
+      removeUnneededVisibilityBridgesFromClass(clazz);
     }
   }
-
-  private DexEncodedMethod[] removeMethods(DexEncodedMethod[] methods,
-      Set<DexEncodedMethod> removals) {
-    assert methods != null;
-    List<DexEncodedMethod> newMethods = Arrays.stream(methods)
-        .filter(method -> !removals.contains(method))
-        .collect(Collectors.toList());
-    assert newMethods.size() < methods.length;
-    return newMethods.toArray(new DexEncodedMethod[newMethods.size()]);
-  }
-
-  public DexApplication run() {
-    for (DexClass clazz : appInfo.classes()) {
-      clazz.forEachMethod(this::identifyBridgeMethod);
-    }
-    if (!unneededVisibilityBridges.isEmpty()) {
-      removeUnneededVisibilityBridges();
-    }
-    return application;
-  }
-
 }
diff --git a/src/main/java/com/android/tools/r8/shaking/DiscardedChecker.java b/src/main/java/com/android/tools/r8/shaking/DiscardedChecker.java
index b28a1a7..07a62a8 100644
--- a/src/main/java/com/android/tools/r8/shaking/DiscardedChecker.java
+++ b/src/main/java/com/android/tools/r8/shaking/DiscardedChecker.java
@@ -9,6 +9,7 @@
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexDefinition;
 import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.graph.DexReference;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.shaking.RootSetBuilder.RootSet;
 import com.android.tools.r8.utils.InternalOptions;
@@ -19,7 +20,7 @@
 
 public class DiscardedChecker {
 
-  private final Set<DexDefinition> checkDiscarded;
+  private final Set<DexReference> checkDiscarded;
   private final List<DexProgramClass> classes;
   private boolean fail = false;
   private final InternalOptions options;
@@ -55,7 +56,7 @@
   }
 
   private void checkItem(DexDefinition item) {
-    if (checkDiscarded.contains(item)) {
+    if (checkDiscarded.contains(item.toReference())) {
       options.reporter.info(
           new StringDiagnostic("Item " + item.toSourceString() + " was not discarded."));
       fail = true;
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 0761a71..55ceee8 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -3,6 +3,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.shaking;
 
+import static com.android.tools.r8.graph.GraphLense.rewriteReferenceKeys;
 import static com.android.tools.r8.naming.IdentifierNameStringUtils.identifyIdentifier;
 import static com.android.tools.r8.naming.IdentifierNameStringUtils.isReflectionMethod;
 import static com.android.tools.r8.shaking.AnnotationRemover.shouldKeepAnnotation;
@@ -63,7 +64,6 @@
 import com.android.tools.r8.utils.Timing;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableList.Builder;
-import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.ImmutableSortedSet;
 import com.google.common.collect.Iterables;
@@ -193,6 +193,10 @@
    */
   private final Set<DexMethod> methodsTargetedByInvokeDynamic = Sets.newIdentityHashSet();
   /**
+   * Set of direct lambda methods that are the immediate target of an invoke-dynamic.
+   */
+  private final Set<DexMethod> lambdaMethodsTargetedByInvokeDynamic = Sets.newIdentityHashSet();
+  /**
    * Set of virtual methods that are the immediate target of an invoke-direct.
    * */
   private final Set<DexMethod> virtualMethodsTargetedByInvokeDirect = Sets.newIdentityHashSet();
@@ -237,15 +241,15 @@
   private final Set<DexMethod> virtualTargetsMarkedAsReachable = Sets.newIdentityHashSet();
 
   /**
-   * A set of dexitems we have reported missing to dedupe warnings.
+   * A set of references we have reported missing to dedupe warnings.
    */
   private final Set<DexReference> reportedMissing = Sets.newIdentityHashSet();
 
   /**
-   * A set of items that we are keeping due to keep rules. This may differ from the rootSet due to
-   * dependent keep rules.
+   * A set of references that we are keeping due to keep rules. This may differ from the root set
+   * due to dependent keep rules.
    */
-  private final Set<DexDefinition> pinnedItems = Sets.newIdentityHashSet();
+  private final Set<DexReference> pinnedItems = Sets.newIdentityHashSet();
 
   /**
    * A map from classes to annotations that need to be processed should the classes ever become
@@ -297,22 +301,24 @@
     this.options = options;
   }
 
-  private void enqueueRootItems(Map<DexDefinition, Set<ProguardKeepRule>> items) {
+  private void enqueueRootItems(Map<DexReference, Set<ProguardKeepRule>> items) {
     items.entrySet().forEach(this::enqueueRootItem);
   }
 
-  private void enqueueRootItem(Entry<DexDefinition, Set<ProguardKeepRule>> root) {
-    enqueueRootItem(root.getKey(), root.getValue());
-  }
-
-  private void enqueueRootItem(DexDefinition item, ProguardKeepRule rule) {
-    enqueueRootItem(item, KeepReason.dueToKeepRule(rule));
+  private void enqueueRootItem(Entry<DexReference, Set<ProguardKeepRule>> root) {
+    DexDefinition item = appInfo.definitionFor(root.getKey());
+    if (item != null) {
+      enqueueRootItem(item, root.getValue());
+    } else {
+      // TODO(b/123923324): Verify that root items are present.
+      // assert false : "Expected root item `" + root.getKey().toSourceString() + "` to be present";
+    }
   }
 
   private void enqueueRootItem(DexDefinition item, Set<ProguardKeepRule> rules) {
     assert !rules.isEmpty();
     if (keptGraphConsumer != null) {
-      GraphNode node = getGraphNode(item);
+      GraphNode node = getGraphNode(item.toReference());
       for (ProguardKeepRule rule : rules) {
         registerEdge(node, KeepReason.dueToKeepRule(rule));
       }
@@ -322,7 +328,7 @@
 
   private void enqueueRootItem(DexDefinition item, KeepReason reason) {
     if (keptGraphConsumer != null) {
-      registerEdge(getGraphNode(item), reason);
+      registerEdge(getGraphNode(item.toReference()), reason);
     }
     internalEnqueueRootItem(item, reason);
   }
@@ -352,7 +358,7 @@
     } else {
       throw new IllegalArgumentException(item.toString());
     }
-    pinnedItems.add(item);
+    pinnedItems.add(item.toReference());
   }
 
   private void enqueueFirstNonSerializableClassInitializer(DexClass clazz, KeepReason reason) {
@@ -368,16 +374,17 @@
   }
 
   private void enqueueHolderIfDependentNonStaticMember(
-      DexClass holder, Map<DexDefinition, Set<ProguardKeepRule>> dependentItems) {
+      DexClass holder, Map<DexReference, Set<ProguardKeepRule>> dependentItems) {
     // Check if any dependent members are not static, and in that case enqueue the class as well.
     // Having a dependent rule like -keepclassmembers with non static items indicates that class
     // instances will be present even if tracing do not find any instantiation. See b/115867670.
-    for (Entry<DexDefinition, Set<ProguardKeepRule>> entry : dependentItems.entrySet()) {
-      DexDefinition dependentItem = entry.getKey();
-      if (dependentItem.isDexClass()) {
+    for (Entry<DexReference, Set<ProguardKeepRule>> entry : dependentItems.entrySet()) {
+      DexReference dependentItem = entry.getKey();
+      if (dependentItem.isDexType()) {
         continue;
       }
-      if (!dependentItem.isStaticMember()) {
+      DexDefinition dependentDefinition = appInfo.definitionFor(dependentItem);
+      if (!dependentDefinition.isStaticMember()) {
         enqueueRootItem(holder, entry.getValue());
         // Enough to enqueue the known holder once.
         break;
@@ -648,6 +655,10 @@
       assert implHandle != null;
 
       DexMethod method = implHandle.asMethod();
+      if (descriptor.delegatesToLambdaImplMethod()) {
+        lambdaMethodsTargetedByInvokeDynamic.add(method);
+      }
+
       if (!methodsTargetedByInvokeDynamic.add(method)) {
         return;
       }
@@ -810,7 +821,7 @@
         annotations.forEach(this::handleAnnotationOfLiveType);
       }
 
-      Map<DexDefinition, Set<ProguardKeepRule>> dependentItems = rootSet.getDependentItems(holder);
+      Map<DexReference, Set<ProguardKeepRule>> dependentItems = rootSet.getDependentItems(holder);
       enqueueHolderIfDependentNonStaticMember(holder, dependentItems);
       // Add all dependent members to the workqueue.
       enqueueRootItems(dependentItems);
@@ -1325,7 +1336,7 @@
       // TODO(sgjesse): Does this have to be enqueued as a root item? Right now it is done as the
       // marking of not renaming is in the root set.
       enqueueRootItem(valuesMethod, reason);
-      rootSet.noObfuscation.add(valuesMethod);
+      rootSet.noObfuscation.add(valuesMethod.toReference());
     }
   }
 
@@ -1465,17 +1476,14 @@
                   targetedMethods.getItems(),
                   executorService);
           ConsequentRootSet consequentRootSet = ifRuleEvaluator.run(liveTypes);
+          rootSet.addConsequentRootSet(consequentRootSet);
           enqueueRootItems(consequentRootSet.noShrinking);
-          rootSet.neverInline.addAll(consequentRootSet.neverInline);
-          rootSet.neverClassInline.addAll(consequentRootSet.neverClassInline);
-          rootSet.noOptimization.addAll(consequentRootSet.noOptimization);
-          rootSet.noObfuscation.addAll(consequentRootSet.noObfuscation);
-          rootSet.addDependentItems(consequentRootSet.dependentNoShrinking);
           // Check if any newly dependent members are not static, and in that case find the holder
           // and enqueue it as well. This is -if version of workaround for b/115867670.
           consequentRootSet.dependentNoShrinking.forEach((precondition, dependentItems) -> {
-            if (precondition.isDexClass()) {
-              enqueueHolderIfDependentNonStaticMember(precondition.asDexClass(), dependentItems);
+            if (precondition.isDexType()) {
+              DexClass preconditionHolder = appInfo.definitionFor(precondition.asDexType());
+              enqueueHolderIfDependentNonStaticMember(preconditionHolder, dependentItems);
             }
             // Add all dependent members to the workqueue.
             enqueueRootItems(dependentItems);
@@ -1520,9 +1528,18 @@
     } finally {
       timing.end();
     }
+    unpinLambdaMethods();
     return new AppInfoWithLiveness(appInfo, this);
   }
 
+  private void unpinLambdaMethods() {
+    for (DexMethod method : lambdaMethodsTargetedByInvokeDynamic) {
+      pinnedItems.remove(method);
+      rootSet.prune(method);
+    }
+    lambdaMethodsTargetedByInvokeDynamic.clear();
+  }
+
   private void markMethodAsKept(DexEncodedMethod target, KeepReason reason) {
     DexClass holder = appInfo.definitionFor(target.method.holder);
     // If this method no longer has a corresponding class then we have shaken it away before.
@@ -1948,11 +1965,11 @@
     /**
      * All items with assumenosideeffects rule.
      */
-    public final Map<DexDefinition, ProguardMemberRule> noSideEffects;
+    public final Map<DexReference, ProguardMemberRule> noSideEffects;
     /**
      * All items with assumevalues rule.
      */
-    public final Map<DexDefinition, ProguardMemberRule> assumedValues;
+    public final Map<DexReference, ProguardMemberRule> assumedValues;
     /**
      * All methods that should be inlined if possible due to a configuration directive.
      */
@@ -1965,9 +1982,13 @@
      * All methods that *must* never be inlined due to a configuration directive (testing only).
      */
     public final Set<DexMethod> neverInline;
-    /** All methods that may not have any parameters with a constant value removed. */
+    /**
+     * All methods that may not have any parameters with a constant value removed.
+     */
     public final Set<DexMethod> keepConstantArguments;
-    /** All methods that may not have any unused arguments removed. */
+    /**
+     * All methods that may not have any unused arguments removed.
+     */
     public final Set<DexMethod> keepUnusedArguments;
     /**
      * All types that *must* never be inlined due to a configuration directive (testing only).
@@ -2028,8 +2049,7 @@
           instanceFieldReads.keySet(), staticFieldReads.keySet());
       this.fieldsWritten = enqueuer.mergeFieldAccesses(
           instanceFieldWrites.keySet(), staticFieldWrites.keySet());
-      this.pinnedItems =
-          DexDefinition.mapToReference(enqueuer.pinnedItems.stream()).collect(Collectors.toSet());
+      this.pinnedItems = enqueuer.pinnedItems;
       this.virtualInvokes = joinInvokedMethods(enqueuer.virtualInvokes);
       this.interfaceInvokes = joinInvokedMethods(enqueuer.interfaceInvokes);
       this.superInvokes = joinInvokedMethods(enqueuer.superInvokes, TargetWithContext::getTarget);
@@ -2143,16 +2163,14 @@
       this.callSites = previous.callSites;
       this.brokenSuperInvokes = lense.rewriteMethodsConservatively(previous.brokenSuperInvokes);
       this.prunedTypes = rewriteItems(previous.prunedTypes, lense::lookupType);
-      assert lense.assertDefinitionsNotModified(previous.noSideEffects.keySet());
-      this.noSideEffects = previous.noSideEffects;
-      assert lense.assertDefinitionsNotModified(previous.assumedValues.keySet());
-      this.assumedValues = previous.assumedValues;
+      this.noSideEffects = rewriteReferenceKeys(previous.noSideEffects, lense::lookupReference);
+      this.assumedValues = rewriteReferenceKeys(previous.assumedValues, lense::lookupReference);
       assert lense.assertDefinitionsNotModified(
           previous.alwaysInline.stream()
               .map(this::definitionFor)
               .filter(Objects::nonNull)
               .collect(Collectors.toList()));
-      this.alwaysInline = previous.alwaysInline;
+      this.alwaysInline = lense.rewriteMethodsWithRenamedSignature(previous.alwaysInline);
       this.forceInline = lense.rewriteMethodsWithRenamedSignature(previous.forceInline);
       this.neverInline = lense.rewriteMethodsWithRenamedSignature(previous.neverInline);
       this.keepConstantArguments =
@@ -2165,7 +2183,7 @@
               .filter(Objects::nonNull)
               .collect(Collectors.toList()));
       this.neverClassInline = rewriteItems(previous.neverClassInline, lense::lookupType);
-      this.neverMerge = previous.neverMerge;
+      this.neverMerge = rewriteItems(previous.neverMerge, lense::lookupType);
       this.identifierNameStrings =
           lense.rewriteReferencesConservatively(previous.identifierNameStrings);
       // Switchmap classes should never be affected by renaming.
@@ -2174,8 +2192,8 @@
               .map(this::definitionFor)
               .filter(Objects::nonNull)
               .collect(Collectors.toList()));
-      this.switchMaps = previous.switchMaps;
-      this.ordinalsMaps = rewriteKeys(previous.ordinalsMaps, lense::lookupType);
+      this.switchMaps = rewriteReferenceKeys(previous.switchMaps, lense::lookupField);
+      this.ordinalsMaps = rewriteReferenceKeys(previous.ordinalsMaps, lense::lookupType);
       // Sanity check sets after rewriting.
       assert Sets.intersection(instanceFieldReads.keySet(), staticFieldReads.keySet()).isEmpty();
       assert Sets.intersection(instanceFieldWrites.keySet(), staticFieldWrites.keySet()).isEmpty();
@@ -2318,14 +2336,6 @@
       return builder.build();
     }
 
-    private static <T extends PresortedComparable<T>, S> ImmutableMap<T, S> rewriteKeys(
-        Map<T, S> original, Function<T, T> rewrite) {
-      ImmutableMap.Builder<T, S> builder = new ImmutableMap.Builder<>();
-      for (T item : original.keySet()) {
-        builder.put(rewrite.apply(item), original.get(item));
-      }
-      return builder.build();
-    }
 
     private static <T extends PresortedComparable<T>, S>
         Map<T, Set<S>> rewriteKeysWhileMergingValues(
@@ -2820,15 +2830,15 @@
     return reason.getSourceNode(this);
   }
 
-  public GraphNode getGraphNode(DexDefinition item) {
-    if (item instanceof DexClass) {
-      return getClassGraphNode(((DexClass) item).type);
+  public GraphNode getGraphNode(DexReference reference) {
+    if (reference.isDexType()) {
+      return getClassGraphNode(reference.asDexType());
     }
-    if (item instanceof DexEncodedMethod) {
-      return getMethodGraphNode(((DexEncodedMethod) item).method);
+    if (reference.isDexMethod()) {
+      return getMethodGraphNode(reference.asDexMethod());
     }
-    if (item instanceof DexEncodedField) {
-      return getFieldGraphNode(((DexEncodedField) item).field);
+    if (reference.isDexField()) {
+      return getFieldGraphNode(reference.asDexField());
     }
     throw new Unreachable();
   }
diff --git a/src/main/java/com/android/tools/r8/shaking/ProguardMemberRule.java b/src/main/java/com/android/tools/r8/shaking/ProguardMemberRule.java
index 86b29a8..f3ac326 100644
--- a/src/main/java/com/android/tools/r8/shaking/ProguardMemberRule.java
+++ b/src/main/java/com/android/tools/r8/shaking/ProguardMemberRule.java
@@ -273,6 +273,19 @@
     return false;
   }
 
+  public boolean isSpecific() {
+    switch (getRuleType()) {
+      case ALL:
+        // fall through
+      case ALL_FIELDS:
+        // fall through
+      case ALL_METHODS:
+        return false;
+      default:
+        return Iterables.size(getWildcards()) == 0;
+    }
+  }
+
   Iterable<ProguardWildcard> getWildcards() {
     return Iterables.concat(
         ProguardTypeMatcher.getWildcardsOrEmpty(annotation),
diff --git a/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java b/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java
index 2a8ce8f..f94954b 100644
--- a/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java
+++ b/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java
@@ -3,6 +3,9 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.shaking;
 
+import static com.android.tools.r8.graph.GraphLense.rewriteMutableReferenceKeys;
+import static com.android.tools.r8.graph.GraphLense.rewriteReferenceKeys;
+
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.AppInfo;
@@ -22,11 +25,11 @@
 import com.android.tools.r8.graph.DexReference;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.DirectMappedDexApplication;
+import com.android.tools.r8.graph.GraphLense;
 import com.android.tools.r8.logging.Log;
 import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.MethodSignatureEquivalence;
-import com.android.tools.r8.utils.OffOrAuto;
 import com.android.tools.r8.utils.StringDiagnostic;
 import com.android.tools.r8.utils.ThreadUtils;
 import com.google.common.base.Equivalence.Wrapper;
@@ -53,6 +56,7 @@
 import java.util.concurrent.ExecutionException;
 import java.util.concurrent.ExecutorService;
 import java.util.concurrent.Future;
+import java.util.function.Function;
 import java.util.function.Predicate;
 import java.util.stream.Collectors;
 
@@ -61,14 +65,14 @@
   private final AppView<? extends AppInfo> appView;
   private final DirectMappedDexApplication application;
   private final Iterable<? extends ProguardConfigurationRule> rules;
-  private final Map<DexDefinition, Set<ProguardKeepRule>> noShrinking = new IdentityHashMap<>();
-  private final Set<DexDefinition> noOptimization = Sets.newIdentityHashSet();
-  private final Set<DexDefinition> noObfuscation = Sets.newIdentityHashSet();
-  private final LinkedHashMap<DexDefinition, DexDefinition> reasonAsked = new LinkedHashMap<>();
-  private final Set<DexDefinition> keepPackageName = Sets.newIdentityHashSet();
+  private final Map<DexReference, Set<ProguardKeepRule>> noShrinking = new IdentityHashMap<>();
+  private final Set<DexReference> noOptimization = Sets.newIdentityHashSet();
+  private final Set<DexReference> noObfuscation = Sets.newIdentityHashSet();
+  private final LinkedHashMap<DexReference, DexReference> reasonAsked = new LinkedHashMap<>();
+  private final Set<DexReference> keepPackageName = Sets.newIdentityHashSet();
   private final Set<ProguardConfigurationRule> rulesThatUseExtendsOrImplementsWrong =
       Sets.newIdentityHashSet();
-  private final Set<DexDefinition> checkDiscarded = Sets.newIdentityHashSet();
+  private final Set<DexReference> checkDiscarded = Sets.newIdentityHashSet();
   private final Set<DexMethod> alwaysInline = Sets.newIdentityHashSet();
   private final Set<DexMethod> forceInline = Sets.newIdentityHashSet();
   private final Set<DexMethod> neverInline = Sets.newIdentityHashSet();
@@ -76,10 +80,10 @@
   private final Set<DexMethod> keepUnusedArguments = Sets.newIdentityHashSet();
   private final Set<DexType> neverClassInline = Sets.newIdentityHashSet();
   private final Set<DexType> neverMerge = Sets.newIdentityHashSet();
-  private final Map<DexDefinition, Map<DexDefinition, Set<ProguardKeepRule>>> dependentNoShrinking =
+  private final Map<DexReference, Map<DexReference, Set<ProguardKeepRule>>> dependentNoShrinking =
       new IdentityHashMap<>();
-  private final Map<DexDefinition, ProguardMemberRule> noSideEffects = new IdentityHashMap<>();
-  private final Map<DexDefinition, ProguardMemberRule> assumedValues = new IdentityHashMap<>();
+  private final Map<DexReference, ProguardMemberRule> noSideEffects = new IdentityHashMap<>();
+  private final Map<DexReference, ProguardMemberRule> assumedValues = new IdentityHashMap<>();
   private final Set<DexReference> identifierNameStrings = Sets.newIdentityHashSet();
   private final InternalOptions options;
 
@@ -863,11 +867,11 @@
     }
     // Keep the type if the item is also kept.
     dependentNoShrinking
-        .computeIfAbsent(item, x -> new IdentityHashMap<>())
-        .computeIfAbsent(definition, k -> new HashSet<>())
+        .computeIfAbsent(item.toReference(), x -> new IdentityHashMap<>())
+        .computeIfAbsent(type, k -> new HashSet<>())
         .add(context);
     // Unconditionally add to no-obfuscation, as that is only checked for surviving items.
-    noObfuscation.add(definition);
+    noObfuscation.add(type);
   }
 
   private void includeDescriptorClasses(DexDefinition item, ProguardKeepRule context) {
@@ -891,9 +895,28 @@
       ProguardMemberRule rule,
       DexDefinition precondition) {
     if (context instanceof ProguardKeepRule) {
-      if (item.isDexEncodedMethod() && item.asDexEncodedMethod().accessFlags.isSynthetic()) {
-        // Don't keep synthetic methods (see b/120971047 for additional details).
-        return;
+      if (item.isDexEncodedMethod()) {
+        DexEncodedMethod encodedMethod = item.asDexEncodedMethod();
+        if (encodedMethod.method.isLambdaDeserializeMethod(appView.dexItemFactory())) {
+          // Don't keep lambda deserialization methods.
+          return;
+        }
+        // If desugaring is enabled, private and static interface methods will be moved to a
+        // companion class. So we don't need to add them to the root set in the beginning.
+        if (options.isInterfaceMethodDesugaringEnabled()
+            && encodedMethod.hasCode()
+            && (encodedMethod.isPrivateMethod() || encodedMethod.isStaticMember())) {
+          DexClass holder = appView.appInfo().definitionFor(encodedMethod.method.getHolder());
+          if (holder != null && holder.isInterface()) {
+            if (rule.isSpecific()) {
+              options.reporter.warning(
+                  new StringDiagnostic(
+                      "The rule `" + rule + "` is ignored because the targeting interface method `"
+                          + encodedMethod.method.toSourceString() + "` will be desugared."));
+            }
+            return;
+          }
+        }
       }
 
       ProguardKeepRule keepRule = (ProguardKeepRule) context;
@@ -901,32 +924,32 @@
       if (!modifiers.allowsShrinking) {
         if (precondition != null) {
           dependentNoShrinking
-              .computeIfAbsent(precondition, x -> new IdentityHashMap<>())
-              .computeIfAbsent(item, i -> new HashSet<>())
+              .computeIfAbsent(precondition.toReference(), x -> new IdentityHashMap<>())
+              .computeIfAbsent(item.toReference(), i -> new HashSet<>())
               .add(keepRule);
         } else {
-          noShrinking.computeIfAbsent(item, i -> new HashSet<>()).add(keepRule);
+          noShrinking.computeIfAbsent(item.toReference(), i -> new HashSet<>()).add(keepRule);
         }
       }
       if (!modifiers.allowsOptimization) {
-        noOptimization.add(item);
+        noOptimization.add(item.toReference());
       }
       if (!modifiers.allowsObfuscation) {
-        noObfuscation.add(item);
+        noObfuscation.add(item.toReference());
       }
       if (modifiers.includeDescriptorClasses) {
         includeDescriptorClasses(item, keepRule);
       }
     } else if (context instanceof ProguardAssumeNoSideEffectRule) {
-      noSideEffects.put(item, rule);
+      noSideEffects.put(item.toReference(), rule);
     } else if (context instanceof ProguardWhyAreYouKeepingRule) {
-      reasonAsked.computeIfAbsent(item, i -> i);
+      reasonAsked.computeIfAbsent(item.toReference(), i -> i);
     } else if (context instanceof ProguardKeepPackageNamesRule) {
-      keepPackageName.add(item);
+      keepPackageName.add(item.toReference());
     } else if (context instanceof ProguardAssumeValuesRule) {
-      assumedValues.put(item, rule);
+      assumedValues.put(item.toReference(), rule);
     } else if (context instanceof ProguardCheckDiscardRule) {
-      checkDiscarded.add(item);
+      checkDiscarded.add(item.toReference());
     } else if (context instanceof InlineRule) {
       if (item.isDexEncodedMethod()) {
         switch (((InlineRule) context).getType()) {
@@ -982,12 +1005,12 @@
 
   public static class RootSet {
 
-    public final Map<DexDefinition, Set<ProguardKeepRule>> noShrinking;
-    public final Set<DexDefinition> noOptimization;
-    public final Set<DexDefinition> noObfuscation;
-    public final ImmutableList<DexDefinition> reasonAsked;
-    public final Set<DexDefinition> keepPackageName;
-    public final Set<DexDefinition> checkDiscarded;
+    public final Map<DexReference, Set<ProguardKeepRule>> noShrinking;
+    public final Set<DexReference> noOptimization;
+    public final Set<DexReference> noObfuscation;
+    public final ImmutableList<DexReference> reasonAsked;
+    public final Set<DexReference> keepPackageName;
+    public final Set<DexReference> checkDiscarded;
     public final Set<DexMethod> alwaysInline;
     public final Set<DexMethod> forceInline;
     public final Set<DexMethod> neverInline;
@@ -995,20 +1018,20 @@
     public final Set<DexMethod> keepUnusedArguments;
     public final Set<DexType> neverClassInline;
     public final Set<DexType> neverMerge;
-    public final Map<DexDefinition, ProguardMemberRule> noSideEffects;
-    public final Map<DexDefinition, ProguardMemberRule> assumedValues;
-    private final Map<DexDefinition, Map<DexDefinition, Set<ProguardKeepRule>>>
+    public final Map<DexReference, ProguardMemberRule> noSideEffects;
+    public final Map<DexReference, ProguardMemberRule> assumedValues;
+    private final Map<DexReference, Map<DexReference, Set<ProguardKeepRule>>>
         dependentNoShrinking;
     public final Set<DexReference> identifierNameStrings;
     public final Set<ProguardIfRule> ifRules;
 
     private RootSet(
-        Map<DexDefinition, Set<ProguardKeepRule>> noShrinking,
-        Set<DexDefinition> noOptimization,
-        Set<DexDefinition> noObfuscation,
-        ImmutableList<DexDefinition> reasonAsked,
-        Set<DexDefinition> keepPackageName,
-        Set<DexDefinition> checkDiscarded,
+        Map<DexReference, Set<ProguardKeepRule>> noShrinking,
+        Set<DexReference> noOptimization,
+        Set<DexReference> noObfuscation,
+        ImmutableList<DexReference> reasonAsked,
+        Set<DexReference> keepPackageName,
+        Set<DexReference> checkDiscarded,
         Set<DexMethod> alwaysInline,
         Set<DexMethod> forceInline,
         Set<DexMethod> neverInline,
@@ -1016,12 +1039,12 @@
         Set<DexMethod> keepUnusedArguments,
         Set<DexType> neverClassInline,
         Set<DexType> neverMerge,
-        Map<DexDefinition, ProguardMemberRule> noSideEffects,
-        Map<DexDefinition, ProguardMemberRule> assumedValues,
-        Map<DexDefinition, Map<DexDefinition, Set<ProguardKeepRule>>> dependentNoShrinking,
+        Map<DexReference, ProguardMemberRule> noSideEffects,
+        Map<DexReference, ProguardMemberRule> assumedValues,
+        Map<DexReference, Map<DexReference, Set<ProguardKeepRule>>> dependentNoShrinking,
         Set<DexReference> identifierNameStrings,
         Set<ProguardIfRule> ifRules) {
-      this.noShrinking = Collections.unmodifiableMap(noShrinking);
+      this.noShrinking = noShrinking;
       this.noOptimization = noOptimization;
       this.noObfuscation = noObfuscation;
       this.reasonAsked = reasonAsked;
@@ -1034,40 +1057,121 @@
       this.keepUnusedArguments = keepUnusedArguments;
       this.neverClassInline = neverClassInline;
       this.neverMerge = Collections.unmodifiableSet(neverMerge);
-      this.noSideEffects = Collections.unmodifiableMap(noSideEffects);
-      this.assumedValues = Collections.unmodifiableMap(assumedValues);
+      this.noSideEffects = noSideEffects;
+      this.assumedValues = assumedValues;
       this.dependentNoShrinking = dependentNoShrinking;
       this.identifierNameStrings = Collections.unmodifiableSet(identifierNameStrings);
       this.ifRules = Collections.unmodifiableSet(ifRules);
     }
 
+    private RootSet(RootSet previous, GraphLense lense) {
+      this.noShrinking = rewriteMutableReferenceKeys(previous.noShrinking, lense::lookupReference);
+      this.noOptimization = lense.rewriteMutableReferencesConservatively(previous.noOptimization);
+      this.noObfuscation = lense.rewriteMutableReferencesConservatively(previous.noObfuscation);
+      this.reasonAsked = lense.rewriteReferencesConservatively(previous.reasonAsked);
+      this.keepPackageName = lense.rewriteReferencesConservatively(previous.keepPackageName);
+      this.checkDiscarded = lense.rewriteReferencesConservatively(previous.checkDiscarded);
+      this.alwaysInline = lense.rewriteMethodsConservatively(previous.alwaysInline);
+      this.forceInline = lense.rewriteMethodsConservatively(previous.forceInline);
+      this.neverInline = lense.rewriteMutableMethodsConservatively(previous.neverInline);
+      this.keepConstantArguments =
+          lense.rewriteMutableMethodsConservatively(previous.keepConstantArguments);
+      this.keepUnusedArguments =
+          lense.rewriteMutableMethodsConservatively(previous.keepUnusedArguments);
+      this.neverClassInline = lense.rewriteMutableTypesConservatively(previous.neverClassInline);
+      this.neverMerge = lense.rewriteTypesConservatively(previous.neverMerge);
+      this.noSideEffects =
+          rewriteMutableReferenceKeys(previous.noSideEffects, lense::lookupReference);
+      this.assumedValues =
+          rewriteMutableReferenceKeys(previous.assumedValues, lense::lookupReference);
+      this.dependentNoShrinking =
+          rewriteDependentReferenceKeys(previous.dependentNoShrinking, lense::lookupReference);
+      this.identifierNameStrings =
+          lense.rewriteReferencesConservatively(previous.identifierNameStrings);
+      this.ifRules = Collections.unmodifiableSet(previous.ifRules);
+    }
+
+    public RootSet rewrittenWithLense(GraphLense lense) {
+      return new RootSet(this, lense);
+    }
+
+    private static <T extends DexReference, S> Map<T, Map<T, S>> rewriteDependentReferenceKeys(
+        Map<T, Map<T, S>> original, Function<T, T> rewrite) {
+      Map<T, Map<T, S>> result = new IdentityHashMap<>();
+      for (T item : original.keySet()) {
+        result.put(rewrite.apply(item), rewriteReferenceKeys(original.get(item), rewrite));
+      }
+      return result;
+    }
+
+    void addConsequentRootSet(ConsequentRootSet consequentRootSet) {
+      neverInline.addAll(consequentRootSet.neverInline);
+      neverClassInline.addAll(consequentRootSet.neverClassInline);
+      noOptimization.addAll(consequentRootSet.noOptimization);
+      noObfuscation.addAll(consequentRootSet.noObfuscation);
+      addDependentItems(consequentRootSet.dependentNoShrinking);
+    }
+
     // Add dependent items that depend on -if rules.
-    void addDependentItems(
-        Map<DexDefinition, Map<DexDefinition, Set<ProguardKeepRule>>> dependentItems) {
+    private void addDependentItems(
+        Map<DexReference, Map<DexReference, Set<ProguardKeepRule>>> dependentItems) {
       dependentItems.forEach(
-          (def, dependence) ->
+          (reference, dependence) ->
               dependentNoShrinking
-                  .computeIfAbsent(def, x -> new IdentityHashMap<>())
+                  .computeIfAbsent(reference, x -> new IdentityHashMap<>())
                   .putAll(dependence));
     }
 
-    Map<DexDefinition, Set<ProguardKeepRule>> getDependentItems(DexDefinition item) {
-      return Collections
-          .unmodifiableMap(dependentNoShrinking.getOrDefault(item, Collections.emptyMap()));
+    Map<DexReference, Set<ProguardKeepRule>> getDependentItems(DexDefinition item) {
+      return Collections.unmodifiableMap(
+          dependentNoShrinking.getOrDefault(item.toReference(), Collections.emptyMap()));
+    }
+
+    public void copy(DexReference original, DexReference rewritten) {
+      if (noShrinking.containsKey(original)) {
+        noShrinking.put(rewritten, noShrinking.get(original));
+      }
+      if (noOptimization.contains(original)) {
+        noOptimization.add(rewritten);
+      }
+      if (noObfuscation.contains(original)) {
+        noObfuscation.add(rewritten);
+      }
+      if (noSideEffects.containsKey(original)) {
+        noSideEffects.put(rewritten, noSideEffects.get(original));
+      }
+      if (assumedValues.containsKey(original)) {
+        assumedValues.put(rewritten, assumedValues.get(original));
+      }
+    }
+
+    public void prune(DexReference reference) {
+      noShrinking.remove(reference);
+      noOptimization.remove(reference);
+      noObfuscation.remove(reference);
+      noSideEffects.remove(reference);
+      assumedValues.remove(reference);
+    }
+
+    public void move(DexReference original, DexReference rewritten) {
+      copy(original, rewritten);
+      prune(original);
     }
 
     public boolean verifyKeptFieldsAreAccessedAndLive(AppInfoWithLiveness appInfo) {
-      for (DexDefinition definition : noShrinking.keySet()) {
-        if (definition.isDexEncodedField()) {
-          DexEncodedField field = definition.asDexEncodedField();
-          if (field.isStatic() || isKeptDirectlyOrIndirectly(field.field.clazz, appInfo)) {
+      for (DexReference reference : noShrinking.keySet()) {
+        if (reference.isDexField()) {
+          DexField field = reference.asDexField();
+          DexEncodedField encodedField = appInfo.definitionFor(field);
+          if (encodedField != null
+              && (encodedField.isStatic() || isKeptDirectlyOrIndirectly(field.clazz, appInfo))) {
             // TODO(b/121354886): Enable asserts for reads and writes.
-            /*assert appInfo.fieldsRead.contains(field.field)
-                : "Expected kept field `" + field.field.toSourceString() + "` to be read";
-            assert appInfo.fieldsWritten.contains(field.field)
-                : "Expected kept field `" + field.field.toSourceString() + "` to be written";*/
-            assert appInfo.liveFields.contains(field.field)
-                : "Expected kept field `" + field.field.toSourceString() + "` to be live";
+            /*assert appInfo.fieldsRead.contains(field)
+                : "Expected kept field `" + field.toSourceString() + "` to be read";
+            assert appInfo.fieldsWritten.contains(field)
+                : "Expected kept field `" + field.toSourceString() + "` to be written";*/
+            assert appInfo.liveFields.contains(field)
+                : "Expected kept field `" + field.toSourceString() + "` to be live";
           }
         }
       }
@@ -1075,17 +1179,17 @@
     }
 
     public boolean verifyKeptMethodsAreTargetedAndLive(AppInfoWithLiveness appInfo) {
-      for (DexDefinition definition : noShrinking.keySet()) {
-        if (definition.isDexEncodedMethod()) {
-          DexEncodedMethod method = definition.asDexEncodedMethod();
-          assert appInfo.targetedMethods.contains(method.method)
-              : "Expected kept method `" + method.method.toSourceString() + "` to be targeted";
-
-          if (!method.accessFlags.isAbstract()
-              && isKeptDirectlyOrIndirectly(method.method.holder, appInfo)) {
-            assert appInfo.liveMethods.contains(method.method)
+      for (DexReference reference : noShrinking.keySet()) {
+        if (reference.isDexMethod()) {
+          DexMethod method = reference.asDexMethod();
+          assert appInfo.targetedMethods.contains(method)
+              : "Expected kept method `" + method.toSourceString() + "` to be targeted";
+          DexEncodedMethod encodedMethod = appInfo.definitionFor(method);
+          if (!encodedMethod.accessFlags.isAbstract()
+              && isKeptDirectlyOrIndirectly(method.holder, appInfo)) {
+            assert appInfo.liveMethods.contains(method)
                 : "Expected non-abstract kept method `"
-                    + method.method.toSourceString()
+                    + method.toSourceString()
                     + "` to be live";
           }
         }
@@ -1094,73 +1198,63 @@
     }
 
     public boolean verifyKeptTypesAreLive(AppInfoWithLiveness appInfo) {
-      for (DexDefinition definition : noShrinking.keySet()) {
-        if (definition.isDexClass()) {
-          DexClass clazz = definition.asDexClass();
-          assert appInfo.liveTypes.contains(clazz.type)
-              : "Expected kept type `" + clazz.type.toSourceString() + "` to be live";
+      for (DexReference reference : noShrinking.keySet()) {
+        if (reference.isDexType()) {
+          DexType type = reference.asDexType();
+          assert appInfo.liveTypes.contains(type)
+              : "Expected kept type `" + type.toSourceString() + "` to be live";
         }
       }
       return true;
     }
 
     private boolean isKeptDirectlyOrIndirectly(DexType type, AppInfoWithLiveness appInfo) {
+      if (noShrinking.containsKey(type)) {
+        return true;
+      }
       DexClass clazz = appInfo.definitionFor(type);
       if (clazz == null) {
         return false;
       }
-      if (noShrinking.containsKey(clazz)) {
-        return true;
-      }
       if (clazz.superType != null) {
         return isKeptDirectlyOrIndirectly(clazz.superType, appInfo);
       }
       return false;
     }
 
-    public boolean verifyKeptItemsAreKept(
-        DexApplication application, AppInfo appInfo, InternalOptions options) {
-      if (options.getProguardConfiguration().hasApplyMappingFile()) {
-        // TODO(b/121295633): Root set is obsolete after mapping has been applied.
-        return true;
-      }
-
-      boolean isInterfaceMethodDesugaringEnabled =
-          options.enableDesugaring
-              && options.interfaceMethodDesugaring == OffOrAuto.Auto
-              && !options.canUseDefaultAndStaticInterfaceMethods();
-
+    public boolean verifyKeptItemsAreKept(DexApplication application, AppInfo appInfo) {
       Set<DexReference> pinnedItems =
           appInfo.hasLiveness() ? appInfo.withLiveness().pinnedItems : null;
 
       // Create a mapping from each required type to the set of required members on that type.
-      Map<DexType, Set<DexDefinition>> requiredDefinitionsPerType = new IdentityHashMap<>();
-      for (DexDefinition definition : noShrinking.keySet()) {
+      Map<DexType, Set<DexReference>> requiredReferencesPerType = new IdentityHashMap<>();
+      for (DexReference reference : noShrinking.keySet()) {
         // Check that `pinnedItems` is a super set of the root set.
-        assert pinnedItems == null || pinnedItems.contains(definition.toReference());
-        if (definition.isDexClass()) {
-          DexType type = definition.toReference().asDexType();
-          requiredDefinitionsPerType.putIfAbsent(type, Sets.newIdentityHashSet());
+        assert pinnedItems == null || pinnedItems.contains(reference)
+            : "Expected reference `" + reference.toSourceString() + "` to be pinned";
+        if (reference.isDexType()) {
+          DexType type = reference.asDexType();
+          requiredReferencesPerType.putIfAbsent(type, Sets.newIdentityHashSet());
         } else {
-          assert definition.isDexEncodedField() || definition.isDexEncodedMethod();
-          Descriptor<?, ?> descriptor = definition.toReference().asDescriptor();
-          requiredDefinitionsPerType
+          assert reference.isDexField() || reference.isDexMethod();
+          Descriptor<?, ?> descriptor = reference.asDescriptor();
+          requiredReferencesPerType
               .computeIfAbsent(descriptor.getHolder(), key -> Sets.newIdentityHashSet())
-              .add(definition);
+              .add(reference);
         }
       }
 
       // Run through each class in the program and check that it has members it must have.
       for (DexProgramClass clazz : application.classes()) {
-        Set<DexDefinition> requiredDefinitions =
-            requiredDefinitionsPerType.getOrDefault(clazz.type, ImmutableSet.of());
+        Set<DexReference> requiredReferences =
+            requiredReferencesPerType.getOrDefault(clazz.type, ImmutableSet.of());
 
         Set<DexField> fields = null;
         Set<DexMethod> methods = null;
 
-        for (DexDefinition requiredDefinition : requiredDefinitions) {
-          if (requiredDefinition.isDexEncodedField()) {
-            DexEncodedField requiredField = requiredDefinition.asDexEncodedField();
+        for (DexReference requiredReference : requiredReferences) {
+          if (requiredReference.isDexField()) {
+            DexField requiredField = requiredReference.asDexField();
             if (fields == null) {
               // Create a Set of the fields to avoid quadratic behavior.
               fields =
@@ -1168,16 +1262,12 @@
                       .map(DexEncodedField::getKey)
                       .collect(Collectors.toSet());
             }
-            assert fields.contains(requiredField.field);
-          } else if (requiredDefinition.isDexEncodedMethod()) {
-            DexEncodedMethod requiredMethod = requiredDefinition.asDexEncodedMethod();
-            if (isInterfaceMethodDesugaringEnabled) {
-              if (clazz.isInterface() && requiredMethod.hasCode()) {
-                // TODO(b/121240523): Ideally, these default interface methods should not be in the
-                // root set.
-                continue;
-              }
-            }
+            assert fields.contains(requiredField)
+                : "Expected field `"
+                    + requiredField.toSourceString()
+                    + "` from the root set to be present";
+          } else if (requiredReference.isDexMethod()) {
+            DexMethod requiredMethod = requiredReference.asDexMethod();
             if (methods == null) {
               // Create a Set of the methods to avoid quadratic behavior.
               methods =
@@ -1185,21 +1275,24 @@
                       .map(DexEncodedMethod::getKey)
                       .collect(Collectors.toSet());
             }
-            assert methods.contains(requiredMethod.method);
+            assert methods.contains(requiredMethod)
+                : "Expected method `"
+                    + requiredMethod.toSourceString()
+                    + "` from the root set to be present";
           } else {
             assert false;
           }
         }
-        requiredDefinitionsPerType.remove(clazz.type);
+        requiredReferencesPerType.remove(clazz.type);
       }
 
       // If the map is non-empty, then a type in the root set was not in the application.
-      if (!requiredDefinitionsPerType.isEmpty()) {
-        DexType type = requiredDefinitionsPerType.keySet().iterator().next();
+      if (!requiredReferencesPerType.isEmpty()) {
+        DexType type = requiredReferencesPerType.keySet().iterator().next();
         DexClass clazz = application.definitionFor(type);
         assert clazz == null || clazz.isProgramClass()
             : "Unexpected library type in root set: `" + type + "`";
-        assert requiredDefinitionsPerType.isEmpty()
+        assert requiredReferencesPerType.isEmpty()
             : "Expected type `" + type.toSourceString() + "` to be present";
       }
 
@@ -1225,7 +1318,7 @@
 
       builder.append("\n\nNo Shrinking:");
       noShrinking.keySet().stream()
-          .sorted(Comparator.comparing(DexDefinition::toSourceString))
+          .sorted(Comparator.comparing(DexReference::toSourceString))
           .forEach(a -> builder
               .append("\n").append(a.toSourceString()).append(" ").append(noShrinking.get(a)));
       builder.append("\n");
@@ -1237,18 +1330,18 @@
   static class ConsequentRootSet {
     final Set<DexMethod> neverInline;
     final Set<DexType> neverClassInline;
-    final Map<DexDefinition, Set<ProguardKeepRule>> noShrinking;
-    final Set<DexDefinition> noOptimization;
-    final Set<DexDefinition> noObfuscation;
-    final Map<DexDefinition, Map<DexDefinition, Set<ProguardKeepRule>>> dependentNoShrinking;
+    final Map<DexReference, Set<ProguardKeepRule>> noShrinking;
+    final Set<DexReference> noOptimization;
+    final Set<DexReference> noObfuscation;
+    final Map<DexReference, Map<DexReference, Set<ProguardKeepRule>>> dependentNoShrinking;
 
     private ConsequentRootSet(
         Set<DexMethod> neverInline,
         Set<DexType> neverClassInline,
-        Map<DexDefinition, Set<ProguardKeepRule>> noShrinking,
-        Set<DexDefinition> noOptimization,
-        Set<DexDefinition> noObfuscation,
-        Map<DexDefinition, Map<DexDefinition, Set<ProguardKeepRule>>> dependentNoShrinking) {
+        Map<DexReference, Set<ProguardKeepRule>> noShrinking,
+        Set<DexReference> noOptimization,
+        Set<DexReference> noObfuscation,
+        Map<DexReference, Map<DexReference, Set<ProguardKeepRule>>> dependentNoShrinking) {
       this.neverInline = Collections.unmodifiableSet(neverInline);
       this.neverClassInline = Collections.unmodifiableSet(neverClassInline);
       this.noShrinking = Collections.unmodifiableMap(noShrinking);
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 7edd536..145f24b 100644
--- a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
+++ b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
@@ -14,7 +14,6 @@
 import com.android.tools.r8.graph.DexAnnotationSet;
 import com.android.tools.r8.graph.DexApplication;
 import com.android.tools.r8.graph.DexClass;
-import com.android.tools.r8.graph.DexDefinition;
 import com.android.tools.r8.graph.DexEncodedField;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexField;
@@ -272,9 +271,7 @@
     // TODO(christofferqa): Remove the invariant that the graph lense should not modify any
     // methods from the sets alwaysInline and noSideEffects (see use of assertNotModified).
     extractPinnedItems(appInfo.alwaysInline, AbortReason.ALWAYS_INLINE);
-    extractPinnedItems(
-        DexDefinition.mapToReference(appInfo.noSideEffects.keySet().stream())::iterator,
-        AbortReason.NO_SIDE_EFFECTS);
+    extractPinnedItems(appInfo.noSideEffects.keySet(), AbortReason.NO_SIDE_EFFECTS);
 
     for (DexProgramClass clazz : classes) {
       for (DexEncodedMethod method : clazz.methods()) {
@@ -620,7 +617,7 @@
   }
 
   private boolean verifyGraphLense(GraphLense graphLense) {
-    assert graphLense.assertDefinitionsNotModified(appInfo.noSideEffects.keySet());
+    assert graphLense.assertReferencesNotModified(appInfo.noSideEffects.keySet());
 
     // Note that the method assertReferencesNotModified() relies on getRenamedFieldSignature() and
     // getRenamedMethodSignature() instead of lookupField() and lookupMethod(). This is important
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/main/java/com/android/tools/r8/utils/InternalOptions.java b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
index 045aa39..cad6397 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -579,6 +579,16 @@
     return isGeneratingClassFiles() || hasMinApi(AndroidApiLevel.N);
   }
 
+  public boolean isInterfaceMethodDesugaringEnabled() {
+    // This condition is to filter out tests that never set program consumer.
+    if (!hasConsumer()) {
+      return false;
+    }
+    return enableDesugaring
+        && interfaceMethodDesugaring == OffOrAuto.Auto
+        && !canUseDefaultAndStaticInterfaceMethods();
+  }
+
   public boolean canUseMultidex() {
     assert isGeneratingDex();
     return intermediate || hasMinApi(AndroidApiLevel.L);
diff --git a/src/test/java/com/android/tools/r8/R8TestCompileResult.java b/src/test/java/com/android/tools/r8/R8TestCompileResult.java
index a9c02ff..ecb0a92 100644
--- a/src/test/java/com/android/tools/r8/R8TestCompileResult.java
+++ b/src/test/java/com/android/tools/r8/R8TestCompileResult.java
@@ -55,6 +55,11 @@
     return state.getDiagnosticsMessages();
   }
 
+  public R8TestCompileResult inspectDiagnosticMessages(Consumer<TestDiagnosticMessages> consumer) {
+    consumer.accept(state.getDiagnosticsMessages());
+    return self();
+  }
+
   @Override
   public CodeInspector inspector() throws IOException, ExecutionException {
     return new CodeInspector(app, proguardMap);
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());
     }
diff --git a/src/test/java/com/android/tools/r8/kotlin/ProcessKotlinReflectionLibTest.java b/src/test/java/com/android/tools/r8/kotlin/ProcessKotlinReflectionLibTest.java
new file mode 100644
index 0000000..700e2d4
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/kotlin/ProcessKotlinReflectionLibTest.java
@@ -0,0 +1,66 @@
+// Copyright (c) 2019, 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.kotlin;
+
+import com.android.tools.r8.KotlinTestBase;
+import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.ToolHelper.KotlinTargetVersion;
+import java.util.Collection;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class ProcessKotlinReflectionLibTest extends KotlinTestBase {
+  private final Backend backend;
+
+  public ProcessKotlinReflectionLibTest(Backend backend, KotlinTargetVersion targetVersion) {
+    super(targetVersion);
+    this.backend = backend;
+  }
+
+  @Parameterized.Parameters(name = "Backend: {0} target: {1}")
+  public static Collection<Object[]> data() {
+    return buildParameters(Backend.values(), KotlinTargetVersion.values());
+  }
+
+  private void test(String... rules) throws Exception {
+    testForR8(backend)
+        .addLibraryFiles(ToolHelper.getDefaultAndroidJar(), ToolHelper.getKotlinStdlibJar())
+        .addProgramFiles(ToolHelper.getKotlinReflectJar())
+        .addKeepRules(rules)
+        .compile();
+  }
+
+  @Test
+  public void testAsIs() throws Exception {
+    test("-dontshrink", "-dontoptimize", "-dontobfuscate");
+  }
+
+  @Test
+  public void testDontShrinkAndDontOptimize() throws Exception {
+    test("-dontshrink", "-dontoptimize");
+  }
+
+  @Test
+  public void testDontShrinkAndDontObfuscate() throws Exception {
+    test("-dontshrink", "-dontobfuscate");
+  }
+
+  @Test
+  public void testDontShrink() throws Exception {
+    test("-dontshrink");
+  }
+
+  @Test
+  public void testDontOptimize() throws Exception {
+    test("-dontoptimize");
+  }
+
+  @Test
+  public void testDontObfuscate() throws Exception {
+    test("-dontobfuscate");
+  }
+
+}
diff --git a/src/test/java/com/android/tools/r8/kotlin/ProcessKotlinStdlibTest.java b/src/test/java/com/android/tools/r8/kotlin/ProcessKotlinStdlibTest.java
new file mode 100644
index 0000000..f796046
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/kotlin/ProcessKotlinStdlibTest.java
@@ -0,0 +1,64 @@
+// Copyright (c) 2019, 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.kotlin;
+
+import com.android.tools.r8.KotlinTestBase;
+import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.ToolHelper.KotlinTargetVersion;
+import java.util.Collection;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class ProcessKotlinStdlibTest extends KotlinTestBase {
+  private final Backend backend;
+
+  public ProcessKotlinStdlibTest(Backend backend, KotlinTargetVersion targetVersion) {
+    super(targetVersion);
+    this.backend = backend;
+  }
+
+  @Parameterized.Parameters(name = "Backend: {0} target: {1}")
+  public static Collection<Object[]> data() {
+    return buildParameters(Backend.values(), KotlinTargetVersion.values());
+  }
+
+  private void test(String... rules) throws Exception {
+    testForR8(backend)
+        .addProgramFiles(ToolHelper.getKotlinStdlibJar())
+        .addKeepRules(rules)
+        .compile();
+  }
+
+  @Test
+  public void testAsIs() throws Exception {
+    test("-dontshrink", "-dontoptimize", "-dontobfuscate");
+  }
+
+  @Test
+  public void testDontShrinkAndDontOptimize() throws Exception {
+    test("-dontshrink", "-dontoptimize");
+  }
+
+  @Test
+  public void testDontShrinkAndDontObfuscate() throws Exception {
+    test("-dontshrink", "-dontobfuscate");
+  }
+
+  @Test
+  public void testDontShrink() throws Exception {
+    test("-dontshrink");
+  }
+
+  @Test
+  public void testDontOptimize() throws Exception {
+    test("-dontoptimize");
+  }
+
+  @Test
+  public void testDontObfuscate() throws Exception {
+    test("-dontobfuscate");
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/shaking/desugar/KeepRuleWarningTest.java b/src/test/java/com/android/tools/r8/shaking/desugar/KeepRuleWarningTest.java
new file mode 100644
index 0000000..ab37cb0
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/desugar/KeepRuleWarningTest.java
@@ -0,0 +1,102 @@
+// Copyright (c) 2019, 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.shaking.desugar;
+
+import static org.hamcrest.CoreMatchers.containsString;
+
+import com.android.tools.r8.NeverMerge;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestDiagnosticMessages;
+import com.android.tools.r8.utils.AndroidApiLevel;
+import com.android.tools.r8.utils.StringUtils;
+import org.junit.Test;
+
+@NeverMerge
+interface I {
+  static void foo() {
+    System.out.println("static::foo");
+  }
+
+  default void bar() {
+    foo();
+    System.out.println("default::bar");
+  }
+}
+
+class C implements I {
+}
+
+class KeepRuleWarningTestRunner {
+  public static void main(String[] args) {
+    C obj = new C();
+    obj.bar();
+  }
+}
+
+public class KeepRuleWarningTest extends TestBase {
+  private static final Class<?> MAIN = KeepRuleWarningTestRunner.class;
+  private static final String EXPECTED_OUTPUT = StringUtils.lines("static::foo", "default::bar");
+
+  @Test
+  public void test_allMethods() throws Exception {
+    testForR8(Backend.DEX)
+        .addProgramClasses(I.class, C.class, MAIN)
+        .setMinApi(AndroidApiLevel.L)
+        .enableMergeAnnotations()
+        .addKeepMainRule(MAIN)
+        .addKeepRules("-keep interface **.I { <methods>; }")
+        .compile()
+        .inspectDiagnosticMessages(TestDiagnosticMessages::assertNoMessages)
+        .run(MAIN)
+        .assertSuccessWithOutput(EXPECTED_OUTPUT);
+  }
+
+  @Test
+  public void test_asterisk() throws Exception {
+    testForR8(Backend.DEX)
+        .addProgramClasses(I.class, C.class, MAIN)
+        .setMinApi(AndroidApiLevel.L)
+        .enableMergeAnnotations()
+        .addKeepMainRule(MAIN)
+        .addKeepRules("-keep interface **.I { *(); }")
+        .compile()
+        .inspectDiagnosticMessages(TestDiagnosticMessages::assertNoMessages)
+        .run(MAIN)
+        .assertSuccessWithOutput(EXPECTED_OUTPUT);
+  }
+
+  @Test
+  public void test_stillNotSpecific() throws Exception {
+    testForR8(Backend.DEX)
+        .addProgramClasses(I.class, C.class, MAIN)
+        .setMinApi(AndroidApiLevel.L)
+        .enableMergeAnnotations()
+        .addKeepMainRule(MAIN)
+        .addKeepRules("-keep interface **.I { *** f*(); }")
+        .compile()
+        .inspectDiagnosticMessages(TestDiagnosticMessages::assertNoMessages)
+        .run(MAIN)
+        .assertSuccessWithOutput(EXPECTED_OUTPUT);
+  }
+
+  @Test
+  public void test_specific() throws Exception {
+    testForR8(Backend.DEX)
+        .addProgramClasses(I.class, C.class, MAIN)
+        .setMinApi(AndroidApiLevel.L)
+        .enableMergeAnnotations()
+        .addKeepMainRule(MAIN)
+        .addKeepRules("-keep interface **.I { static void foo(); }")
+        .compile()
+        .inspectDiagnosticMessages(m -> {
+          m.assertWarningsCount(1)
+              .assertWarningMessageThatMatches(containsString("static void foo()"))
+              .assertWarningMessageThatMatches(containsString("is ignored"))
+              .assertWarningMessageThatMatches(containsString("will be desugared"));
+        })
+        .run(MAIN)
+        .assertSuccessWithOutput(EXPECTED_OUTPUT);
+  }
+
+}
\ No newline at end of file
diff --git a/src/test/java/com/android/tools/r8/shaking/desugar/interfacemethods/BridgeInliningTest.java b/src/test/java/com/android/tools/r8/shaking/desugar/interfacemethods/BridgeInliningTest.java
new file mode 100644
index 0000000..5038729
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/desugar/interfacemethods/BridgeInliningTest.java
@@ -0,0 +1,73 @@
+// Copyright (c) 2019, 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.shaking.desugar.interfacemethods;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertThat;
+import static org.junit.Assert.assertTrue;
+
+import com.android.tools.r8.NeverMerge;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.utils.AndroidApiLevel;
+import com.android.tools.r8.utils.StringUtils;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import com.android.tools.r8.utils.codeinspector.MethodSubject;
+import java.lang.reflect.Method;
+import org.junit.Test;
+
+@NeverMerge
+interface I {
+  default void m() {
+    System.out.println("I::m");
+  }
+}
+
+class C implements I {
+}
+
+class BridgeInliningTestRunner {
+  public static void main(String[] args) throws Exception {
+    C obj = new C();
+    for (Method m : obj.getClass().getDeclaredMethods()) {
+      m.invoke(obj, null);
+    }
+  }
+}
+
+public class BridgeInliningTest extends TestBase {
+  private static final Class<?> MAIN = BridgeInliningTestRunner.class;
+  private static final String EXPECTED_OUTPUT = StringUtils.lines("I::m");
+
+  @Test
+  public void test() throws Exception {
+    testForR8(Backend.DEX)
+        .addProgramClasses(I.class, C.class, MAIN)
+        .setMinApi(AndroidApiLevel.L)
+        .enableMergeAnnotations()
+        .addKeepMainRule(MAIN)
+        .addKeepRules("-keep interface **.I { m(); }")
+        .run(MAIN)
+        .assertSuccessWithOutput(EXPECTED_OUTPUT)
+        .inspect(this::inspect);
+  }
+
+  private void inspect(CodeInspector codeInspector) {
+    ClassSubject c = codeInspector.clazz(C.class);
+    assertThat(c, isPresent());
+    MethodSubject m = c.uniqueMethodWithName("m");
+    assertThat(m, isPresent());
+    assertTrue(m.getMethod().hasCode());
+    // TODO(b/123778921): why are I and C not merged without merge annotations?
+    //assertTrue(
+    //    m.iterateInstructions(i -> i.isConstString("I::m", JumboStringMode.ALLOW)).hasNext());
+
+    // TODO(b/123778921): No companion class is in the output.
+    //codeInspector.forAllClasses(classSubject -> {
+    //  assertFalse(classSubject.getOriginalDescriptor().contains("$-CC"));
+    //});
+  }
+
+}
diff --git a/src/test/java/com/android/tools/r8/shaking/synthetic/KotlinCollectionDump.java b/src/test/java/com/android/tools/r8/shaking/synthetic/KotlinCollectionDump.java
new file mode 100644
index 0000000..d104272
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/synthetic/KotlinCollectionDump.java
@@ -0,0 +1,113 @@
+// Copyright (c) 2019, 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.shaking.synthetic;
+
+import org.objectweb.asm.ClassWriter;
+import org.objectweb.asm.Label;
+import org.objectweb.asm.MethodVisitor;
+import org.objectweb.asm.Opcodes;
+
+// Generated by running tools/asmifier.py on the following code snippet:
+//
+//  class Base {
+//    public static void foo() {
+//      System.out.println("Base::foo");
+//    }
+//    static void bar() {
+//      Sub.foo();
+//    }
+//  }
+//
+// then make bar _synthetic_ as `kotlinc` does.
+class Base implements Opcodes {
+
+  public static byte[] dump () throws Exception {
+
+    ClassWriter classWriter = new ClassWriter(0);
+    MethodVisitor methodVisitor;
+
+    classWriter.visit(V1_8, ACC_SUPER, "Base", null, "java/lang/Object", null);
+
+    classWriter.visitSource("Arrays.kt", null);
+
+    {
+      methodVisitor = classWriter.visitMethod(0, "<init>", "()V", null, null);
+      methodVisitor.visitCode();
+      Label label0 = new Label();
+      methodVisitor.visitLabel(label0);
+      methodVisitor.visitLineNumber(3, label0);
+      methodVisitor.visitVarInsn(ALOAD, 0);
+      methodVisitor.visitMethodInsn(INVOKESPECIAL, "java/lang/Object", "<init>", "()V", false);
+      methodVisitor.visitInsn(RETURN);
+      methodVisitor.visitMaxs(1, 1);
+      methodVisitor.visitEnd();
+    }
+    {
+      methodVisitor = classWriter.visitMethod(ACC_PUBLIC | ACC_STATIC, "foo", "()V", null, null);
+      methodVisitor.visitCode();
+      Label label0 = new Label();
+      methodVisitor.visitLabel(label0);
+      methodVisitor.visitLineNumber(5, label0);
+      methodVisitor.visitFieldInsn(GETSTATIC, "java/lang/System", "out", "Ljava/io/PrintStream;");
+      methodVisitor.visitLdcInsn("Base::foo");
+      methodVisitor.visitMethodInsn(
+          INVOKEVIRTUAL, "java/io/PrintStream", "println", "(Ljava/lang/String;)V", false);
+      Label label1 = new Label();
+      methodVisitor.visitLabel(label1);
+      methodVisitor.visitLineNumber(6, label1);
+      methodVisitor.visitInsn(RETURN);
+      methodVisitor.visitMaxs(2, 0);
+      methodVisitor.visitEnd();
+    }
+    {
+      methodVisitor = classWriter.visitMethod(ACC_STATIC | ACC_SYNTHETIC, "bar", "()V", null, null);
+      methodVisitor.visitCode();
+      Label label0 = new Label();
+      methodVisitor.visitLabel(label0);
+      methodVisitor.visitLineNumber(9, label0);
+      methodVisitor.visitMethodInsn(INVOKESTATIC, "Sub", "foo", "()V", false);
+      Label label1 = new Label();
+      methodVisitor.visitLabel(label1);
+      methodVisitor.visitLineNumber(10, label1);
+      methodVisitor.visitInsn(RETURN);
+      methodVisitor.visitMaxs(0, 0);
+      methodVisitor.visitEnd();
+    }
+    classWriter.visitEnd();
+
+    return classWriter.toByteArray();
+  }
+}
+
+// Generated by running tools/asmifier.py on the following code snippet:
+//  class Sub extends Base {}
+class Sub implements Opcodes {
+
+  public static byte[] dump () throws Exception {
+
+    ClassWriter classWriter = new ClassWriter(0);
+    MethodVisitor methodVisitor;
+
+    classWriter.visit(V1_8, ACC_SUPER, "Sub", null, "Base", null);
+
+    classWriter.visitSource("Arrays.kt", null);
+
+    {
+      methodVisitor = classWriter.visitMethod(0, "<init>", "()V", null, null);
+      methodVisitor.visitCode();
+      Label label0 = new Label();
+      methodVisitor.visitLabel(label0);
+      methodVisitor.visitLineNumber(13, label0);
+      methodVisitor.visitVarInsn(ALOAD, 0);
+      methodVisitor.visitMethodInsn(INVOKESPECIAL, "Base", "<init>", "()V", false);
+      methodVisitor.visitInsn(RETURN);
+      methodVisitor.visitMaxs(1, 1);
+      methodVisitor.visitEnd();
+    }
+    classWriter.visitEnd();
+
+    return classWriter.toByteArray();
+  }
+}
+
diff --git a/src/test/java/com/android/tools/r8/shaking/synthetic/StaticCallInSyntheticMethodAsmTest.java b/src/test/java/com/android/tools/r8/shaking/synthetic/StaticCallInSyntheticMethodAsmTest.java
new file mode 100644
index 0000000..b08be31
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/synthetic/StaticCallInSyntheticMethodAsmTest.java
@@ -0,0 +1,37 @@
+// Copyright (c) 2019, 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.shaking.synthetic;
+
+import com.android.tools.r8.AsmTestBase;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class StaticCallInSyntheticMethodAsmTest extends AsmTestBase {
+  private final Backend backend;
+
+  @Parameterized.Parameters(name = "backend: {0}")
+  public static Backend[] data() {
+    return Backend.values();
+  }
+
+  public StaticCallInSyntheticMethodAsmTest(Backend backend) {
+    this.backend = backend;
+  }
+
+  // class Base {
+  //   static void foo() { ... }
+  //   static synthetic void bar() { Sub.foo(); }
+  // }
+  // class Sub extends Base {}
+  @Test
+  public void test() throws Exception {
+    testForR8(backend)
+        .addProgramClassFileData(Base.dump(), Sub.dump())
+        .addKeepRules("-dontshrink")
+        .compile();
+  }
+
+}