diff --git a/.gitignore b/.gitignore
index c5f7f13..6e4c0e3 100644
--- a/.gitignore
+++ b/.gitignore
@@ -132,6 +132,16 @@
 third_party/opensource-apps/antennapod.tar.gz
 third_party/opensource-apps/applymapping
 third_party/opensource-apps/applymapping.tar.gz
+third_party/opensource-apps/chanu
+third_party/opensource-apps/chanu.tar.gz
+third_party/opensource-apps/friendlyeats
+third_party/opensource-apps/friendlyeats.tar.gz
+third_party/opensource-apps/iosched
+third_party/opensource-apps/iosched.tar.gz
+third_party/opensource-apps/sunflower
+third_party/opensource-apps/sunflower.tar.gz
+third_party/opensource-apps/wikipedia
+third_party/opensource-apps/wikipedia.tar.gz
 third_party/opensource_apps
 third_party/opensource_apps.tar.gz
 third_party/proguard/*
diff --git a/src/main/java/com/android/tools/r8/R8.java b/src/main/java/com/android/tools/r8/R8.java
index a38b29e..b97eb7f 100644
--- a/src/main/java/com/android/tools/r8/R8.java
+++ b/src/main/java/com/android/tools/r8/R8.java
@@ -422,7 +422,7 @@
                   appViewWithLiveness, appViewWithLiveness.appInfo().computeSubtypingInfo())
               .run();
 
-          if (appView.options().protoShrinking().isProtoShrinkingEnabled()) {
+          if (appView.options().protoShrinking().isProtoEnumShrinkingEnabled()) {
             appView.protoShrinker().enumProtoShrinker.clearDeadEnumLiteMaps();
           }
 
@@ -571,12 +571,11 @@
         }
         if (options.enableHorizontalClassMerging && options.enableInlining) {
           timing.begin("HorizontalClassMerger");
-          HorizontalClassMerger merger =
-              new HorizontalClassMerger(
-                  appViewWithLiveness, mainDexTracingResult, runtimeTypeCheckInfo);
+          HorizontalClassMerger merger = new HorizontalClassMerger(appViewWithLiveness);
           DirectMappedDexApplication.Builder appBuilder =
               appView.appInfo().app().asDirect().builder();
-          HorizontalClassMergerGraphLens lens = merger.run(appBuilder);
+          HorizontalClassMergerGraphLens lens =
+              merger.run(appBuilder, mainDexTracingResult, runtimeTypeCheckInfo);
           if (lens != null) {
             DirectMappedDexApplication app = appBuilder.build();
             appView.removePrunedClasses(app, appView.horizontallyMergedClasses().getSources());
@@ -783,7 +782,9 @@
         }
 
         if (appView.options().protoShrinking().isProtoShrinkingEnabled()) {
-          appView.protoShrinker().enumProtoShrinker.verifyDeadEnumLiteMapsAreDead();
+          if (appView.options().protoShrinking().isProtoEnumShrinkingEnabled()) {
+            appView.protoShrinker().enumProtoShrinker.verifyDeadEnumLiteMapsAreDead();
+          }
 
           IRConverter converter = new IRConverter(appView, timing, null, mainDexTracingResult);
 
diff --git a/src/main/java/com/android/tools/r8/dex/DexParser.java b/src/main/java/com/android/tools/r8/dex/DexParser.java
index 4941d0b..24d3a36 100644
--- a/src/main/java/com/android/tools/r8/dex/DexParser.java
+++ b/src/main/java/com/android/tools/r8/dex/DexParser.java
@@ -674,6 +674,7 @@
         code = codes.get(codeOff);
       }
       DexMethod method = indexedItems.getMethod(methodIndex);
+      accessFlags.setConstructor(method, dexItemFactory);
       DexAnnotationSet methodAnnotations = annotationIterator.getNextFor(method);
       String methodSignature = DexAnnotation.getSignature(methodAnnotations, dexItemFactory);
       if (methodSignature != null) {
diff --git a/src/main/java/com/android/tools/r8/graph/AccessFlags.java b/src/main/java/com/android/tools/r8/graph/AccessFlags.java
index c169b25..de254fc 100644
--- a/src/main/java/com/android/tools/r8/graph/AccessFlags.java
+++ b/src/main/java/com/android/tools/r8/graph/AccessFlags.java
@@ -291,4 +291,34 @@
     }
     return builder.toString();
   }
+
+  abstract static class BuilderBase<B extends BuilderBase<B, F>, F extends AccessFlags<F>> {
+
+    protected F flags;
+
+    BuilderBase(F flags) {
+      this.flags = flags;
+    }
+
+    public B setPackagePrivate() {
+      assert flags.isPackagePrivate();
+      return self();
+    }
+
+    public B setStatic() {
+      flags.setStatic();
+      return self();
+    }
+
+    public B setSynthetic() {
+      flags.setSynthetic();
+      return self();
+    }
+
+    public F build() {
+      return flags;
+    }
+
+    public abstract B self();
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/graph/AppInfoWithClassHierarchy.java b/src/main/java/com/android/tools/r8/graph/AppInfoWithClassHierarchy.java
index ace1d56..144b1de 100644
--- a/src/main/java/com/android/tools/r8/graph/AppInfoWithClassHierarchy.java
+++ b/src/main/java/com/android/tools/r8/graph/AppInfoWithClassHierarchy.java
@@ -669,19 +669,19 @@
       List<DexType> interfaces,
       MaximallySpecificMethodsBuilder builder) {
     for (DexType iface : interfaces) {
-      DexClass definiton = definitionFor(iface);
-      if (definiton == null) {
+      DexClass definition = definitionFor(iface);
+      if (definition == null) {
         // Ignore missing interface definitions.
         continue;
       }
-      assert definiton.isInterface();
-      DexEncodedMethod result = definiton.lookupMethod(method);
+      assert definition.isInterface();
+      DexEncodedMethod result = definition.lookupMethod(method);
       if (isMaximallySpecificCandidate(result)) {
         // The candidate is added and doing so will prohibit shadowed methods from being in the set.
-        builder.addCandidate(definiton, result, this);
+        builder.addCandidate(definition, result, this);
       } else {
         // Look at the super-interfaces of this class and keep searching.
-        resolveMethodStep3Helper(method, definiton, builder);
+        resolveMethodStep3Helper(method, definition, builder);
       }
     }
     // Now look at indirect super interfaces.
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 37f45c6..ef9b742 100644
--- a/src/main/java/com/android/tools/r8/graph/AppView.java
+++ b/src/main/java/com/android/tools/r8/graph/AppView.java
@@ -13,6 +13,7 @@
 import com.android.tools.r8.graph.classmerging.MergedClassesCollection;
 import com.android.tools.r8.graph.classmerging.VerticallyMergedClasses;
 import com.android.tools.r8.horizontalclassmerging.HorizontallyMergedClasses;
+import com.android.tools.r8.ir.analysis.proto.EnumLiteProtoShrinker;
 import com.android.tools.r8.ir.analysis.proto.GeneratedExtensionRegistryShrinker;
 import com.android.tools.r8.ir.analysis.proto.GeneratedMessageLiteBuilderShrinker;
 import com.android.tools.r8.ir.analysis.proto.GeneratedMessageLiteShrinker;
@@ -315,6 +316,13 @@
     return defaultValue;
   }
 
+  public <U> U withProtoEnumShrinker(Function<EnumLiteProtoShrinker, U> fn, U defaultValue) {
+    if (protoShrinker != null && options().protoShrinking().isProtoEnumShrinkingEnabled()) {
+      return fn.apply(protoShrinker.enumProtoShrinker);
+    }
+    return defaultValue;
+  }
+
   public <E extends Throwable> void withGeneratedExtensionRegistryShrinker(
       ThrowingConsumer<GeneratedExtensionRegistryShrinker, E> consumer) throws E {
     if (protoShrinker != null && protoShrinker.generatedExtensionRegistryShrinker != null) {
diff --git a/src/main/java/com/android/tools/r8/graph/DexClass.java b/src/main/java/com/android/tools/r8/graph/DexClass.java
index c49b888..45130dc 100644
--- a/src/main/java/com/android/tools/r8/graph/DexClass.java
+++ b/src/main/java/com/android/tools/r8/graph/DexClass.java
@@ -11,6 +11,7 @@
 import com.android.tools.r8.origin.Origin;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.InternalOptions;
+import com.android.tools.r8.utils.IterableUtils;
 import com.android.tools.r8.utils.OptionalBool;
 import com.android.tools.r8.utils.TraversalContinuation;
 import com.google.common.base.MoreObjects;
@@ -179,6 +180,10 @@
     return methodCollection.removeMethod(method);
   }
 
+  public void setDirectMethods(List<DexEncodedMethod> methods) {
+    setDirectMethods(methods.toArray(DexEncodedMethod.EMPTY_ARRAY));
+  }
+
   public void setDirectMethods(DexEncodedMethod[] methods) {
     methodCollection.setDirectMethods(methods);
   }
@@ -195,6 +200,10 @@
     methodCollection.addVirtualMethods(methods);
   }
 
+  public void setVirtualMethods(List<DexEncodedMethod> methods) {
+    setVirtualMethods(methods.toArray(DexEncodedMethod.EMPTY_ARRAY));
+  }
+
   public void setVirtualMethods(DexEncodedMethod[] methods) {
     methodCollection.setVirtualMethods(methods);
   }
@@ -263,6 +272,10 @@
     return Arrays.asList(staticFields);
   }
 
+  public Iterable<DexEncodedField> staticFields(Predicate<DexEncodedField> predicate) {
+    return IterableUtils.filter(staticFields(), predicate);
+  }
+
   public void appendStaticField(DexEncodedField field) {
     DexEncodedField[] newFields = new DexEncodedField[staticFields.length + 1];
     System.arraycopy(staticFields, 0, newFields, 0, staticFields.length);
@@ -498,6 +511,10 @@
     return null;
   }
 
+  public boolean canBeInstantiatedByNewInstance() {
+    return !isAbstract() && !isAnnotation() && !isInterface();
+  }
+
   public boolean isAbstract() {
     return accessFlags.isAbstract();
   }
diff --git a/src/main/java/com/android/tools/r8/graph/DexEncodedField.java b/src/main/java/com/android/tools/r8/graph/DexEncodedField.java
index c10a345..159c27b 100644
--- a/src/main/java/com/android/tools/r8/graph/DexEncodedField.java
+++ b/src/main/java/com/android/tools/r8/graph/DexEncodedField.java
@@ -95,6 +95,7 @@
     optimizationInfo = info;
   }
 
+  @Override
   public KotlinFieldLevelInfo getKotlinMemberInfo() {
     return kotlinMemberInfo;
   }
diff --git a/src/main/java/com/android/tools/r8/graph/DexEncodedMember.java b/src/main/java/com/android/tools/r8/graph/DexEncodedMember.java
index 079afc1..dd69340 100644
--- a/src/main/java/com/android/tools/r8/graph/DexEncodedMember.java
+++ b/src/main/java/com/android/tools/r8/graph/DexEncodedMember.java
@@ -3,6 +3,8 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.graph;
 
+import com.android.tools.r8.kotlin.KotlinMemberLevelInfo;
+
 public abstract class DexEncodedMember<D extends DexEncodedMember<D, R>, R extends DexMember<D, R>>
     extends DexDefinition {
 
@@ -14,6 +16,8 @@
     return getReference().holder;
   }
 
+  public abstract KotlinMemberLevelInfo getKotlinMemberInfo();
+
   @Override
   public abstract R getReference();
 
diff --git a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
index c92307e..c353e8a 100644
--- a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
+++ b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
@@ -381,6 +381,10 @@
     return method;
   }
 
+  public DexMethodSignature getSignature() {
+    return new DexMethodSignature(method);
+  }
+
   public DexTypeList parameters() {
     return method.proto.parameters;
   }
@@ -595,6 +599,15 @@
     return accessFlags.isSynthetic();
   }
 
+  public boolean belongsToDirectPool() {
+    return accessFlags.isStatic() || accessFlags.isPrivate() || accessFlags.isConstructor();
+  }
+
+  public boolean belongsToVirtualPool() {
+    return !belongsToDirectPool();
+  }
+
+  @Override
   public KotlinMethodLevelInfo getKotlinMemberInfo() {
     return kotlinMemberInfo;
   }
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 98128c4..6edd1e1 100644
--- a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
+++ b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
@@ -1780,7 +1780,7 @@
    *
    * @param tryString callback to check if the method name is in use.
    */
-  public <T extends DexMember<?, ?>> T createFreshMember(
+  public <T> T createFreshMember(
       Function<DexString, Optional<T>> tryString, String baseName, DexType holder) {
     int index = 0;
     while (true) {
@@ -1841,20 +1841,19 @@
       DexProto proto,
       DexType target,
       Predicate<DexMethod> isFresh) {
-    DexMethod method =
-        createFreshMember(
-            name -> {
-              DexMethod tryMethod = createMethod(target, proto, name);
-              if (isFresh.test(tryMethod)) {
-                return Optional.of(tryMethod);
-              } else {
-                return Optional.empty();
-              }
-            },
-            baseName,
-            holder);
-    return method;
+    return createFreshMember(
+        name -> {
+          DexMethod tryMethod = createMethod(target, proto, name);
+          if (isFresh.test(tryMethod)) {
+            return Optional.of(tryMethod);
+          } else {
+            return Optional.empty();
+          }
+        },
+        baseName,
+        holder);
   }
+
   /**
    * Tries to find a method name for insertion into the class {@code target} of the form
    * baseName$holder$n, where {@code baseName} and {@code holder} are supplied by the user, and
@@ -1863,14 +1862,49 @@
    *
    * @param holder indicates where the method originates from.
    */
-  public DexField createFreshFieldName(
+  public DexMethodSignature createFreshMethodSignatureName(
+      String baseName, DexType holder, DexProto proto, Predicate<DexMethodSignature> isFresh) {
+    return createFreshMember(
+        name -> {
+          DexMethodSignature trySignature = new DexMethodSignature(proto, name);
+          if (isFresh.test(trySignature)) {
+            return Optional.of(trySignature);
+          } else {
+            return Optional.empty();
+          }
+        },
+        baseName,
+        holder);
+  }
+
+  /**
+   * Tries to find a method name for insertion into the class {@code target} of the form baseName$n,
+   * where {@code baseName} is supplied by the user, and {@code n} is picked to be the first number
+   * so that {@code isFresh.apply(method)} returns {@code true}.
+   */
+  public DexField createFreshFieldName(DexField template, Predicate<DexField> isFresh) {
+    return internalCreateFreshFieldName(template, null, isFresh);
+  }
+
+  /**
+   * Tries to find a method name for insertion into the class {@code target} of the form
+   * baseName$holder$n, where {@code baseName} and {@code holder} are supplied by the user, and
+   * {@code n} is picked to be the first number so that {@code isFresh.apply(method)} returns {@code
+   * true}.
+   *
+   * @param holder indicates where the method originates from.
+   */
+  public DexField createFreshFieldNameWithHolderSuffix(
       DexField template, DexType holder, Predicate<DexField> isFresh) {
-    DexField field =
-        createFreshMember(
-            name -> Optional.of(template.withName(name, this)).filter(isFresh),
-            template.name.toSourceString(),
-            holder);
-    return field;
+    return internalCreateFreshFieldName(template, holder, isFresh);
+  }
+
+  private DexField internalCreateFreshFieldName(
+      DexField template, DexType holder, Predicate<DexField> isFresh) {
+    return createFreshMember(
+        name -> Optional.of(template.withName(name, this)).filter(isFresh),
+        template.name.toSourceString(),
+        holder);
   }
 
   public DexMethod createInstanceInitializerWithFreshProto(
@@ -2146,6 +2180,10 @@
     return createMethod(clazz, proto, name);
   }
 
+  public DexMethod createClinitMethod(DexType holder) {
+    return createMethod(holder, createProto(voidType), classConstructorMethodName);
+  }
+
   public AdvanceLine createAdvanceLine(int delta) {
     synchronized (advanceLines) {
       return advanceLines.computeIfAbsent(delta, AdvanceLine::new);
diff --git a/src/main/java/com/android/tools/r8/graph/DexMember.java b/src/main/java/com/android/tools/r8/graph/DexMember.java
index 5c34e83..3041e01 100644
--- a/src/main/java/com/android/tools/r8/graph/DexMember.java
+++ b/src/main/java/com/android/tools/r8/graph/DexMember.java
@@ -27,6 +27,11 @@
   public abstract boolean match(D entry);
 
   @Override
+  public DexType getContextType() {
+    return holder;
+  }
+
+  @Override
   public boolean isDexMember() {
     return true;
   }
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 74b0fff..6c288c7 100644
--- a/src/main/java/com/android/tools/r8/graph/DexMethod.java
+++ b/src/main/java/com/android/tools/r8/graph/DexMethod.java
@@ -110,6 +110,10 @@
     return proto.parameters.size();
   }
 
+  public DexMethodSignature getSignature() {
+    return new DexMethodSignature(this);
+  }
+
   @Override
   public void collectIndexedItems(IndexedItemCollection indexedItems) {
     if (collectIndexedItemsExceptName(indexedItems)) {
diff --git a/src/main/java/com/android/tools/r8/graph/DexMethodSignature.java b/src/main/java/com/android/tools/r8/graph/DexMethodSignature.java
new file mode 100644
index 0000000..8b2fcc4
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/graph/DexMethodSignature.java
@@ -0,0 +1,92 @@
+// Copyright (c) 2020, 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 java.util.Objects;
+
+public class DexMethodSignature {
+  private final DexProto proto;
+  private final DexString name;
+
+  public DexMethodSignature(DexMethod method) {
+    this(method.proto, method.name);
+  }
+
+  public DexMethodSignature(DexProto proto, DexString name) {
+    assert proto != null;
+    assert name != null;
+    this.proto = proto;
+    this.name = name;
+  }
+
+  public DexProto getProto() {
+    return proto;
+  }
+
+  public DexString getName() {
+    return name;
+  }
+
+  public DexMethodSignature withName(DexString name) {
+    return new DexMethodSignature(proto, name);
+  }
+
+  public DexMethodSignature withProto(DexProto proto) {
+    return new DexMethodSignature(proto, name);
+  }
+
+  public DexMethod withHolder(ProgramDefinition definition, DexItemFactory dexItemFactory) {
+    return withHolder(definition.getContextType(), dexItemFactory);
+  }
+
+  public DexMethod withHolder(DexReference reference, DexItemFactory dexItemFactory) {
+    return dexItemFactory.createMethod(reference.getContextType(), proto, name);
+  }
+
+  @Override
+  public boolean equals(Object o) {
+    if (this == o) return true;
+    if (o == null || getClass() != o.getClass()) return false;
+    DexMethodSignature that = (DexMethodSignature) o;
+    return proto == that.proto && name == that.name;
+  }
+
+  @Override
+  public int hashCode() {
+    return Objects.hash(proto, name);
+  }
+
+  public DexType getReturnType() {
+    return proto.returnType;
+  }
+
+  public int getArity() {
+    return proto.getArity();
+  }
+
+  @Override
+  public String toString() {
+    return "Method Signature " + name + " " + proto.toString();
+  }
+
+  private String toSourceString() {
+    return toSourceString(false);
+  }
+
+  private String toSourceString(boolean includeReturnType) {
+    StringBuilder builder = new StringBuilder();
+    if (includeReturnType) {
+      builder.append(getReturnType().toSourceString()).append(" ");
+    }
+    builder.append(name).append("(");
+    for (int i = 0; i < getArity(); i++) {
+      if (i != 0) {
+        builder.append(", ");
+      }
+      builder.append(proto.parameters.values[i].toSourceString());
+    }
+    return builder.append(")").toString();
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/graph/DexProto.java b/src/main/java/com/android/tools/r8/graph/DexProto.java
index 1eefc66..333be20 100644
--- a/src/main/java/com/android/tools/r8/graph/DexProto.java
+++ b/src/main/java/com/android/tools/r8/graph/DexProto.java
@@ -45,6 +45,10 @@
     return parameters.values[index];
   }
 
+  public int getArity() {
+    return parameters.size();
+  }
+
   @Override
   public int computeHashCode() {
     return shorty.hashCode()
diff --git a/src/main/java/com/android/tools/r8/graph/DexReference.java b/src/main/java/com/android/tools/r8/graph/DexReference.java
index c60efe5..3263b6d 100644
--- a/src/main/java/com/android/tools/r8/graph/DexReference.java
+++ b/src/main/java/com/android/tools/r8/graph/DexReference.java
@@ -29,6 +29,8 @@
 
   public abstract void collectIndexedItems(IndexedItemCollection indexedItems);
 
+  public abstract DexType getContextType();
+
   public boolean isDexType() {
     return false;
   }
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 b1892bf..72e632d 100644
--- a/src/main/java/com/android/tools/r8/graph/DexType.java
+++ b/src/main/java/com/android/tools/r8/graph/DexType.java
@@ -52,6 +52,11 @@
     this.descriptor = descriptor;
   }
 
+  @Override
+  public DexType getContextType() {
+    return this;
+  }
+
   public DexString getDescriptor() {
     return descriptor;
   }
diff --git a/src/main/java/com/android/tools/r8/graph/DexTypeList.java b/src/main/java/com/android/tools/r8/graph/DexTypeList.java
index 87080e8..7d6ed51 100644
--- a/src/main/java/com/android/tools/r8/graph/DexTypeList.java
+++ b/src/main/java/com/android/tools/r8/graph/DexTypeList.java
@@ -129,4 +129,14 @@
   public Iterator<DexType> iterator() {
     return Iterators.forArray(values);
   }
+
+  public DexTypeList getSorted() {
+    if (values.length <= 1) {
+      return this;
+    }
+
+    DexType[] newValues = values.clone();
+    Arrays.sort(newValues, DexType::slowCompareTo);
+    return new DexTypeList(newValues);
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/graph/FieldAccessFlags.java b/src/main/java/com/android/tools/r8/graph/FieldAccessFlags.java
index bb39765..554df05 100644
--- a/src/main/java/com/android/tools/r8/graph/FieldAccessFlags.java
+++ b/src/main/java/com/android/tools/r8/graph/FieldAccessFlags.java
@@ -44,6 +44,10 @@
     super(originalFlags, modifiedFlags);
   }
 
+  public static Builder builder() {
+    return new Builder();
+  }
+
   @Override
   public FieldAccessFlags copy() {
     return new FieldAccessFlags(originalFlags, modifiedFlags);
@@ -100,4 +104,16 @@
   public void setEnum() {
     set(Constants.ACC_ENUM);
   }
+
+  public static class Builder extends BuilderBase<Builder, FieldAccessFlags> {
+
+    public Builder() {
+      super(FieldAccessFlags.fromSharedAccessFlags(0));
+    }
+
+    @Override
+    public Builder self() {
+      return this;
+    }
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/graph/GraphLens.java b/src/main/java/com/android/tools/r8/graph/GraphLens.java
index c788a1a..87cea9c 100644
--- a/src/main/java/com/android/tools/r8/graph/GraphLens.java
+++ b/src/main/java/com/android/tools/r8/graph/GraphLens.java
@@ -536,7 +536,15 @@
     return result;
   }
 
-  public ImmutableSortedSet<DexMethod> rewriteMethods(Set<DexMethod> methods) {
+  public ImmutableSet<DexMethod> rewriteMethods(Set<DexMethod> methods) {
+    ImmutableSet.Builder<DexMethod> builder = ImmutableSet.builder();
+    for (DexMethod method : methods) {
+      builder.add(getRenamedMethodSignature(method));
+    }
+    return builder.build();
+  }
+
+  public ImmutableSortedSet<DexMethod> rewriteMethodsSorted(Set<DexMethod> methods) {
     ImmutableSortedSet.Builder<DexMethod> builder =
         new ImmutableSortedSet.Builder<>(PresortedComparable::slowCompare);
     for (DexMethod method : methods) {
diff --git a/src/main/java/com/android/tools/r8/graph/InnerClassAttribute.java b/src/main/java/com/android/tools/r8/graph/InnerClassAttribute.java
index d54bc7b..bb0fbf8 100644
--- a/src/main/java/com/android/tools/r8/graph/InnerClassAttribute.java
+++ b/src/main/java/com/android/tools/r8/graph/InnerClassAttribute.java
@@ -107,7 +107,7 @@
           context = enclosingMethodAttribute.getEnclosingClass();
         } else {
           DexMethod enclosingMethod = enclosingMethodAttribute.getEnclosingMethod();
-          if (!appView.appInfo().liveMethods.contains(enclosingMethod)) {
+          if (!appView.appInfo().isLiveMethod(enclosingMethod)) {
             // EnclosingMethodAttribute will be pruned as it references the pruned method.
             // Hence, the current InnerClassAttribute will be removed too. No live context.
             return null;
diff --git a/src/main/java/com/android/tools/r8/graph/MethodAccessFlags.java b/src/main/java/com/android/tools/r8/graph/MethodAccessFlags.java
index c29ebde..61e54e9 100644
--- a/src/main/java/com/android/tools/r8/graph/MethodAccessFlags.java
+++ b/src/main/java/com/android/tools/r8/graph/MethodAccessFlags.java
@@ -61,6 +61,10 @@
     super(originalFlags, modifiedFlags);
   }
 
+  public static Builder builder() {
+    return new Builder();
+  }
+
   @Override
   public MethodAccessFlags copy() {
     return new MethodAccessFlags(originalFlags, modifiedFlags);
@@ -183,6 +187,12 @@
     set(Constants.ACC_CONSTRUCTOR);
   }
 
+  public void setConstructor(DexMethod method, DexItemFactory dexItemFactory) {
+    if (dexItemFactory.isConstructor(method) || dexItemFactory.isClassConstructor(method)) {
+      setConstructor();
+    }
+  }
+
   public void unsetConstructor() {
     unset(Constants.ACC_CONSTRUCTOR);
   }
@@ -200,4 +210,21 @@
   private void unsetDeclaredSynchronized() {
     unset(Constants.ACC_DECLARED_SYNCHRONIZED);
   }
+
+  public static class Builder extends BuilderBase<Builder, MethodAccessFlags> {
+
+    Builder() {
+      super(MethodAccessFlags.fromSharedAccessFlags(0, false));
+    }
+
+    public Builder setConstructor() {
+      flags.setConstructor();
+      return this;
+    }
+
+    @Override
+    public Builder self() {
+      return this;
+    }
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/graph/MethodCollection.java b/src/main/java/com/android/tools/r8/graph/MethodCollection.java
index b14ff47..d483a59 100644
--- a/src/main/java/com/android/tools/r8/graph/MethodCollection.java
+++ b/src/main/java/com/android/tools/r8/graph/MethodCollection.java
@@ -292,6 +292,10 @@
     backing.setDirectMethods(methods);
   }
 
+  public void setSingleDirectMethod(DexEncodedMethod method) {
+    setDirectMethods(new DexEncodedMethod[] {method});
+  }
+
   public void addVirtualMethods(Collection<DexEncodedMethod> methods) {
     assert verifyCorrectnessOfMethodHolders(methods);
     resetVirtualMethodCaches();
diff --git a/src/main/java/com/android/tools/r8/graph/MethodCollectionBacking.java b/src/main/java/com/android/tools/r8/graph/MethodCollectionBacking.java
index 37a46f0..301352a 100644
--- a/src/main/java/com/android/tools/r8/graph/MethodCollectionBacking.java
+++ b/src/main/java/com/android/tools/r8/graph/MethodCollectionBacking.java
@@ -19,13 +19,11 @@
   abstract boolean verify();
 
   boolean belongsToDirectPool(DexEncodedMethod method) {
-    return method.accessFlags.isStatic()
-        || method.accessFlags.isPrivate()
-        || method.accessFlags.isConstructor();
+    return method.belongsToDirectPool();
   }
 
   boolean belongsToVirtualPool(DexEncodedMethod method) {
-    return !belongsToDirectPool(method);
+    return method.belongsToVirtualPool();
   }
 
   // Collection methods.
diff --git a/src/main/java/com/android/tools/r8/graph/ProgramDefinition.java b/src/main/java/com/android/tools/r8/graph/ProgramDefinition.java
index e96d26c..6c5ff48 100644
--- a/src/main/java/com/android/tools/r8/graph/ProgramDefinition.java
+++ b/src/main/java/com/android/tools/r8/graph/ProgramDefinition.java
@@ -16,6 +16,8 @@
 
   DexDefinition getDefinition();
 
+  DexReference getReference();
+
   Origin getOrigin();
 
   default boolean isProgramClass() {
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/ClassMerger.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/ClassMerger.java
index d441d2c..79913ff 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/ClassMerger.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/ClassMerger.java
@@ -22,6 +22,7 @@
 import com.android.tools.r8.shaking.FieldAccessInfoCollectionModifier;
 import com.android.tools.r8.utils.MethodSignatureEquivalence;
 import com.google.common.base.Equivalence.Wrapper;
+import com.google.common.base.Predicates;
 import com.google.common.collect.Iterables;
 import it.unimi.dsi.fastutil.objects.Reference2IntMap;
 import it.unimi.dsi.fastutil.objects.Reference2IntOpenHashMap;
@@ -48,6 +49,7 @@
   private final HorizontallyMergedClasses.Builder mergedClassesBuilder;
   private final FieldAccessInfoCollectionModifier.Builder fieldAccessChangesBuilder;
 
+  private final ClassMethodsBuilder classMethodsBuilder = new ClassMethodsBuilder();
   private final Reference2IntMap<DexType> classIdentifiers = new Reference2IntOpenHashMap<>();
   private final ClassStaticFieldsMerger classStaticFieldsMerger;
   private final Collection<VirtualMethodMerger> virtualMethodMergers;
@@ -99,31 +101,33 @@
     }
   }
 
-  void merge(DexProgramClass toMerge) {
-    if (!toMerge.isFinal()) {
-      target.getAccessFlags().demoteFromFinal();
-    }
+  void mergeDirectMethods(SyntheticArgumentClass syntheticArgumentClass) {
+    mergeDirectMethods(target);
+    toMergeGroup.forEach(this::mergeDirectMethods);
 
+    mergeConstructors(syntheticArgumentClass);
+  }
+
+  void mergeDirectMethods(DexProgramClass toMerge) {
     toMerge.forEachProgramDirectMethod(
         method -> {
           DexEncodedMethod definition = method.getDefinition();
           assert !definition.isClassInitializer();
 
           if (!definition.isInstanceInitializer()) {
-            DexMethod newMethod = renameMethod(method);
-            // TODO(b/165000217): Add all methods to `target` in one go using addDirectMethods().
-            target.addDirectMethod(definition.toTypeSubstitutedMethod(newMethod));
-            lensBuilder.moveMethod(definition.getReference(), newMethod);
+            DexMethod newMethod = method.getReference().withHolder(target.type, dexItemFactory);
+            if (!classMethodsBuilder.isFresh(newMethod)) {
+              newMethod = renameDirectMethod(method);
+            }
+            classMethodsBuilder.addDirectMethod(definition.toTypeSubstitutedMethod(newMethod));
+            if (definition.getReference() != newMethod) {
+              lensBuilder.moveMethod(definition.getReference(), newMethod);
+            }
           }
         });
 
-    classStaticFieldsMerger.addFields(toMerge);
-
     // Clear the members of the class to be merged since they have now been moved to the target.
-    toMerge.setVirtualMethods(null);
-    toMerge.setDirectMethods(null);
-    toMerge.setInstanceFields(null);
-    toMerge.setStaticFields(null);
+    toMerge.getMethodCollection().clearDirectMethods();
   }
 
   /**
@@ -131,26 +135,33 @@
    *
    * @param method The class the method originally belonged to.
    */
-  DexMethod renameMethod(ProgramMethod method) {
+  DexMethod renameDirectMethod(ProgramMethod method) {
+    assert method.getDefinition().belongsToDirectPool();
     return dexItemFactory.createFreshMethodName(
         method.getDefinition().method.name.toSourceString(),
         method.getHolderType(),
         method.getDefinition().proto(),
         target.type,
-        tryMethod -> target.lookupMethod(tryMethod) == null);
+        classMethodsBuilder::isFresh);
   }
 
   void mergeConstructors(SyntheticArgumentClass syntheticArgumentClass) {
-    for (ConstructorMerger merger : constructorMergers) {
-      merger.merge(
-          lensBuilder, fieldAccessChangesBuilder, classIdentifiers, syntheticArgumentClass);
-    }
+    constructorMergers.forEach(
+        merger ->
+            merger.merge(
+                classMethodsBuilder,
+                lensBuilder,
+                fieldAccessChangesBuilder,
+                classIdentifiers,
+                syntheticArgumentClass));
   }
 
   void mergeVirtualMethods() {
-    for (VirtualMethodMerger merger : virtualMethodMergers) {
-      merger.merge(lensBuilder, fieldAccessChangesBuilder, classIdentifiers);
-    }
+    virtualMethodMergers.forEach(
+        merger ->
+            merger.merge(
+                classMethodsBuilder, lensBuilder, fieldAccessChangesBuilder, classIdentifiers));
+    toMergeGroup.forEach(clazz -> clazz.getMethodCollection().clearVirtualMethods());
   }
 
   void appendClassIdField() {
@@ -166,20 +177,37 @@
   }
 
   void mergeStaticFields() {
+    toMergeGroup.forEach(classStaticFieldsMerger::addFields);
     classStaticFieldsMerger.merge(target);
+    toMergeGroup.forEach(clazz -> clazz.setStaticFields(null));
+  }
+
+  void fixFinal() {
+    if (Iterables.any(toMergeGroup, Predicates.not(DexProgramClass::isFinal))) {
+      target.accessFlags.demoteFromFinal();
+    }
+  }
+
+  void mergeInstanceFields() {
+    // TODO: support instance field merging
+    assert Iterables.all(toMergeGroup, clazz -> !clazz.hasInstanceFields());
+
+    // The target should only have the class id field.
+    assert target.instanceFields().size() == 1;
   }
 
   public void mergeGroup(SyntheticArgumentClass syntheticArgumentClass) {
+    fixFinal();
     appendClassIdField();
 
-    mergedClassesBuilder.addMergeGroup(target, toMergeGroup);
-    for (DexProgramClass clazz : toMergeGroup) {
-      merge(clazz);
-    }
-
-    mergeConstructors(syntheticArgumentClass);
     mergeVirtualMethods();
+    mergeDirectMethods(syntheticArgumentClass);
+    classMethodsBuilder.setClassMethods(target);
+
     mergeStaticFields();
+    mergeInstanceFields();
+
+    mergedClassesBuilder.addMergeGroup(target, toMergeGroup);
   }
 
   public static class Builder {
@@ -252,7 +280,8 @@
       List<VirtualMethodMerger> virtualMethodMergers =
           new ArrayList<>(virtualMethodMergerBuilders.size());
       for (VirtualMethodMerger.Builder builder : virtualMethodMergerBuilders.values()) {
-        virtualMethodMergers.add(builder.build(appView, target, classIdField));
+        virtualMethodMergers.add(
+            builder.build(appView, target, classIdField, toMergeGroup.size() + 1));
       }
       // Try and merge the functions with the most arguments first, to avoid using synthetic
       // arguments if possible.
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/ClassMethodsBuilder.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/ClassMethodsBuilder.java
new file mode 100644
index 0000000..2516cad
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/ClassMethodsBuilder.java
@@ -0,0 +1,44 @@
+// Copyright (c) 2020, 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.horizontalclassmerging;
+
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexProgramClass;
+import com.google.common.collect.Sets;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Set;
+
+public class ClassMethodsBuilder {
+  private Set<DexMethod> reservedMethods = Sets.newIdentityHashSet();
+  private List<DexEncodedMethod> virtualMethods = new ArrayList<>();
+  private List<DexEncodedMethod> directMethods = new ArrayList<>();
+
+  public void addVirtualMethod(DexEncodedMethod virtualMethod) {
+    virtualMethods.add(virtualMethod);
+    boolean added = reservedMethods.add(virtualMethod.getReference());
+    assert added;
+  }
+
+  public void addDirectMethod(DexEncodedMethod directMethod) {
+    directMethods.add(directMethod);
+    boolean added = reservedMethods.add(directMethod.getReference());
+    assert added;
+  }
+
+  public boolean isFresh(DexMethod method) {
+    return !reservedMethods.contains(method);
+  }
+
+  public void setClassMethods(DexProgramClass clazz) {
+    assert virtualMethods.stream().allMatch(method -> method.holder() == clazz.type);
+    assert virtualMethods.stream().allMatch(method -> method.belongsToVirtualPool());
+    assert directMethods.stream().allMatch(method -> method.holder() == clazz.type);
+    assert directMethods.stream().allMatch(method -> method.belongsToDirectPool());
+    clazz.setVirtualMethods(virtualMethods);
+    clazz.setDirectMethods(directMethods);
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/ClassStaticFieldsMerger.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/ClassStaticFieldsMerger.java
index ce4b93e..d826b86 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/ClassStaticFieldsMerger.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/ClassStaticFieldsMerger.java
@@ -42,7 +42,8 @@
     DexField oldFieldReference = field.getReference();
     DexField templateReference = field.getReference().withHolder(target.type, dexItemFactory);
     DexField newFieldReference =
-        dexItemFactory.createFreshFieldName(templateReference, field.holder(), this::isFresh);
+        dexItemFactory.createFreshFieldNameWithHolderSuffix(
+            templateReference, field.holder(), this::isFresh);
 
     field = field.toTypeSubstitutedField(newFieldReference);
     targetFields.put(newFieldReference, field);
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/ConstructorMerger.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/ConstructorMerger.java
index f6127d9..d15ed7e 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/ConstructorMerger.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/ConstructorMerger.java
@@ -115,18 +115,15 @@
     return constructors.size() == 1;
   }
 
-  private DexMethod moveConstructor(DexEncodedMethod constructor) {
+  private DexMethod moveConstructor(
+      ClassMethodsBuilder classMethodsBuilder, DexEncodedMethod constructor) {
     DexMethod method =
         dexItemFactory.createFreshMethodName(
             "constructor",
             constructor.holder(),
             constructor.proto(),
             target.type,
-            tryMethod -> target.lookupMethod(tryMethod) == null);
-
-    if (constructor.holder() == target.type) {
-      target.removeMethod(constructor.getReference());
-    }
+            classMethodsBuilder::isFresh);
 
     DexEncodedMethod encodedMethod = constructor.toTypeSubstitutedMethod(method);
     encodedMethod.getMutableOptimizationInfo().markForceInline();
@@ -134,7 +131,8 @@
     encodedMethod.accessFlags.unsetPublic();
     encodedMethod.accessFlags.unsetProtected();
     encodedMethod.accessFlags.setPrivate();
-    target.addDirectMethod(encodedMethod);
+    classMethodsBuilder.addDirectMethod(encodedMethod);
+
     return method;
   }
 
@@ -146,6 +144,7 @@
 
   /** Synthesize a new method which selects the constructor based on a parameter type. */
   void merge(
+      ClassMethodsBuilder classMethodsBuilder,
       HorizontalClassMergerGraphLens.Builder lensBuilder,
       FieldAccessInfoCollectionModifier.Builder fieldAccessChangesBuilder,
       Reference2IntMap<DexType> classIdentifiers,
@@ -159,7 +158,7 @@
         classFileVersion =
             CfVersion.maxAllowNull(classFileVersion, constructor.getClassFileVersion());
       }
-      DexMethod movedConstructor = moveConstructor(constructor);
+      DexMethod movedConstructor = moveConstructor(classMethodsBuilder, constructor);
       lensBuilder.mapMethod(movedConstructor, movedConstructor);
       lensBuilder.mapMethodInverse(constructor.method, movedConstructor);
       typeConstructorClassMap.put(
@@ -169,9 +168,9 @@
     DexMethod methodReferenceTemplate = generateReferenceMethodTemplate();
     DexMethod newConstructorReference =
         dexItemFactory.createInstanceInitializerWithFreshProto(
-            methodReferenceTemplate,
+            methodReferenceTemplate.withHolder(target.type, dexItemFactory),
             syntheticArgumentClass.getArgumentClass(),
-            tryMethod -> target.lookupMethod(tryMethod) == null);
+            classMethodsBuilder::isFresh);
     int extraNulls = newConstructorReference.getArity() - methodReferenceTemplate.getArity();
 
     DexMethod representativeConstructorReference = constructors.iterator().next().method;
@@ -221,7 +220,7 @@
     lensBuilder.recordExtraOriginalSignature(
         representativeConstructorReference, newConstructorReference);
 
-    target.addDirectMethod(newConstructor);
+    classMethodsBuilder.addDirectMethod(newConstructor);
 
     fieldAccessChangesBuilder.fieldWrittenByMethod(classIdField, newConstructorReference);
   }
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMerger.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMerger.java
index a442450..2200267 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMerger.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMerger.java
@@ -8,6 +8,7 @@
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DirectMappedDexApplication;
 import com.android.tools.r8.horizontalclassmerging.policies.AllInstantiatedOrUninstantiated;
+import com.android.tools.r8.horizontalclassmerging.policies.ClassesHaveSameInterfaces;
 import com.android.tools.r8.horizontalclassmerging.policies.DontInlinePolicy;
 import com.android.tools.r8.horizontalclassmerging.policies.DontMergeIntoLessVisible;
 import com.android.tools.r8.horizontalclassmerging.policies.DontMergeSynchronizedClasses;
@@ -15,12 +16,12 @@
 import com.android.tools.r8.horizontalclassmerging.policies.NoAbstractClasses;
 import com.android.tools.r8.horizontalclassmerging.policies.NoAnnotations;
 import com.android.tools.r8.horizontalclassmerging.policies.NoClassesOrMembersWithAnnotations;
-import com.android.tools.r8.horizontalclassmerging.policies.NoClassesWithInterfaces;
 import com.android.tools.r8.horizontalclassmerging.policies.NoEnums;
 import com.android.tools.r8.horizontalclassmerging.policies.NoInnerClasses;
 import com.android.tools.r8.horizontalclassmerging.policies.NoInstanceFields;
 import com.android.tools.r8.horizontalclassmerging.policies.NoInterfaces;
 import com.android.tools.r8.horizontalclassmerging.policies.NoKeepRules;
+import com.android.tools.r8.horizontalclassmerging.policies.NoKotlinMetadata;
 import com.android.tools.r8.horizontalclassmerging.policies.NoNativeMethods;
 import com.android.tools.r8.horizontalclassmerging.policies.NoRuntimeTypeChecks;
 import com.android.tools.r8.horizontalclassmerging.policies.NoServiceLoaders;
@@ -30,6 +31,7 @@
 import com.android.tools.r8.horizontalclassmerging.policies.NotVerticallyMergedIntoSubtype;
 import com.android.tools.r8.horizontalclassmerging.policies.PreventChangingVisibility;
 import com.android.tools.r8.horizontalclassmerging.policies.PreventMergeIntoMainDex;
+import com.android.tools.r8.horizontalclassmerging.policies.PreventMethodImplementation;
 import com.android.tools.r8.horizontalclassmerging.policies.RespectPackageBoundaries;
 import com.android.tools.r8.horizontalclassmerging.policies.SameFeatureSplit;
 import com.android.tools.r8.horizontalclassmerging.policies.SameNestHost;
@@ -48,64 +50,28 @@
 
 public class HorizontalClassMerger {
   private final AppView<AppInfoWithLiveness> appView;
-  private final PolicyExecutor policyExecutor;
 
-  public HorizontalClassMerger(
-      AppView<AppInfoWithLiveness> appView,
-      MainDexTracingResult mainDexTracingResult,
-      RuntimeTypeCheckInfo runtimeTypeCheckInfo) {
+  public HorizontalClassMerger(AppView<AppInfoWithLiveness> appView) {
     this.appView = appView;
     assert appView.options().enableInlining;
-
-    List<Policy> policies =
-        ImmutableList.of(
-            new NotMatchedByNoHorizontalClassMerging(appView),
-            new NoInstanceFields(),
-            // TODO(b/166071504): Allow merging of classes that implement interfaces.
-            new NoInterfaces(),
-            new NoClassesWithInterfaces(),
-            new NoAnnotations(),
-            new NoEnums(appView),
-            new NoAbstractClasses(),
-            new IgnoreSynthetics(appView),
-            new NoClassesOrMembersWithAnnotations(),
-            new NoInnerClasses(),
-            new NoStaticClassInitializer(),
-            new NoNativeMethods(),
-            new NoKeepRules(appView),
-            new NoServiceLoaders(appView),
-            new NotVerticallyMergedIntoSubtype(appView),
-            new NoRuntimeTypeChecks(runtimeTypeCheckInfo),
-            new NotEntryPoint(appView.dexItemFactory()),
-            new DontInlinePolicy(appView, mainDexTracingResult),
-            new PreventMergeIntoMainDex(appView, mainDexTracingResult),
-            new AllInstantiatedOrUninstantiated(appView),
-            new SameParentClass(),
-            new SameNestHost(),
-            new PreventChangingVisibility(),
-            new SameFeatureSplit(appView),
-            new RespectPackageBoundaries(appView),
-            new DontMergeSynchronizedClasses(appView),
-            // TODO(b/166577694): no policies should be run after this policy, as it would
-            // potentially break tests
-            new DontMergeIntoLessVisible()
-            // TODO: add policies
-            );
-
-    this.policyExecutor = new SimplePolicyExecutor(policies);
   }
 
   // TODO(b/165577835): replace Collection<DexProgramClass> with MergeGroup
-  public HorizontalClassMergerGraphLens run(DirectMappedDexApplication.Builder appBuilder) {
+  public HorizontalClassMergerGraphLens run(
+      DirectMappedDexApplication.Builder appBuilder,
+      MainDexTracingResult mainDexTracingResult,
+      RuntimeTypeCheckInfo runtimeTypeCheckInfo) {
     Map<FieldMultiset, List<DexProgramClass>> classes = new LinkedHashMap<>();
 
     // Group classes by same field signature using the hash map.
-    for (DexProgramClass clazz : appView.appInfo().app().classesWithDeterministicOrder()) {
+    for (DexProgramClass clazz : appView.appInfo().classesWithDeterministicOrder()) {
       classes.computeIfAbsent(new FieldMultiset(clazz), ignore -> new ArrayList<>()).add(clazz);
     }
 
     // Run the policies on all collected classes to produce a final grouping.
-    Collection<List<DexProgramClass>> groups = policyExecutor.run(classes.values());
+    Collection<List<DexProgramClass>> groups =
+        new SimplePolicyExecutor()
+            .run(classes.values(), getPolicies(mainDexTracingResult, runtimeTypeCheckInfo));
     // If there are no groups, then end horizontal class merging.
     if (groups.isEmpty()) {
       appView.setHorizontallyMergedClasses(HorizontallyMergedClasses.empty());
@@ -138,6 +104,45 @@
         mergedClasses, lensBuilder, fieldAccessChangesBuilder, syntheticArgumentClass);
   }
 
+  private List<Policy> getPolicies(
+      MainDexTracingResult mainDexTracingResult,
+      RuntimeTypeCheckInfo runtimeTypeCheckInfo) {
+    return ImmutableList.of(
+        new NotMatchedByNoHorizontalClassMerging(appView),
+        new NoInstanceFields(),
+        new NoInterfaces(),
+        new ClassesHaveSameInterfaces(),
+        new NoAnnotations(),
+        new NoEnums(appView),
+        new NoAbstractClasses(),
+        new IgnoreSynthetics(appView),
+        new NoClassesOrMembersWithAnnotations(),
+        new NoInnerClasses(),
+        new NoStaticClassInitializer(),
+        new NoNativeMethods(),
+        new NoKeepRules(appView),
+        new NoKotlinMetadata(),
+        new NoServiceLoaders(appView),
+        new NotVerticallyMergedIntoSubtype(appView),
+        new NoRuntimeTypeChecks(runtimeTypeCheckInfo),
+        new NotEntryPoint(appView.dexItemFactory()),
+        new PreventMethodImplementation(appView),
+        new DontInlinePolicy(appView, mainDexTracingResult),
+        new PreventMergeIntoMainDex(appView, mainDexTracingResult),
+        new AllInstantiatedOrUninstantiated(appView),
+        new SameParentClass(),
+        new SameNestHost(),
+        new PreventChangingVisibility(),
+        new SameFeatureSplit(appView),
+        new RespectPackageBoundaries(appView),
+        new DontMergeSynchronizedClasses(appView),
+        // TODO(b/166577694): no policies should be run after this policy, as it would
+        // potentially break tests
+        new DontMergeIntoLessVisible()
+        // TODO: add policies
+        );
+  }
+
   /**
    * Prepare horizontal class merging by determining which virtual methods and constructors need to
    * be merged and how the merging should be performed.
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/MultiClassPolicy.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/MultiClassPolicy.java
index 2c8f10a..eb5d4d0 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/MultiClassPolicy.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/MultiClassPolicy.java
@@ -19,9 +19,11 @@
   /**
    * Remove all groups containing no or only a single class, as there is no point in merging these.
    */
-  protected void removeTrivialGroups(Collection<List<DexProgramClass>> groups) {
+  protected Collection<List<DexProgramClass>> removeTrivialGroups(
+      Collection<List<DexProgramClass>> groups) {
     assert !(groups instanceof ArrayList);
     groups.removeIf(this::isTrivial);
+    return groups;
   }
 
   /**
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/PolicyExecutor.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/PolicyExecutor.java
index cddca41..a5f58d2 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/PolicyExecutor.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/PolicyExecutor.java
@@ -9,16 +9,12 @@
 import java.util.List;
 
 public abstract class PolicyExecutor {
-  protected final Collection<Policy> policies;
-
-  public PolicyExecutor(Collection<Policy> policies) {
-    this.policies = policies;
-  }
 
   /**
    * Given an initial collection of class groups which can potentially be merged, run all of the
    * policies registered to this policy executor on the class groups yielding a new collection of
    * class groups.
    */
-  public abstract Collection<List<DexProgramClass>> run(Collection<List<DexProgramClass>> classes);
+  public abstract Collection<List<DexProgramClass>> run(
+      Collection<List<DexProgramClass>> classes, Collection<Policy> policies);
 }
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/SimplePolicyExecutor.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/SimplePolicyExecutor.java
index a5f26d8..1a3a965 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/SimplePolicyExecutor.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/SimplePolicyExecutor.java
@@ -17,9 +17,6 @@
  * against which more efficient policy executors can be compared.
  */
 public class SimplePolicyExecutor extends PolicyExecutor {
-  public SimplePolicyExecutor(Collection<Policy> policies) {
-    super(policies);
-  }
 
   // TODO(b/165506334): if performing mutable operation ensure that linked lists are used
   private LinkedList<List<DexProgramClass>> applySingleClassPolicy(
@@ -46,7 +43,8 @@
   }
 
   @Override
-  public Collection<List<DexProgramClass>> run(Collection<List<DexProgramClass>> inputGroups) {
+  public Collection<List<DexProgramClass>> run(
+      Collection<List<DexProgramClass>> inputGroups, Collection<Policy> policies) {
     LinkedList<List<DexProgramClass>> linkedGroups;
 
     if (inputGroups instanceof LinkedList) {
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/SubtypingForrestForClasses.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/SubtypingForrestForClasses.java
index b643225..05440b4 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/SubtypingForrestForClasses.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/SubtypingForrestForClasses.java
@@ -35,10 +35,9 @@
   private final Collection<DexProgramClass> roots = new ArrayList<>();
   private final Map<DexProgramClass, List<DexProgramClass>> subtypeMap = new IdentityHashMap<>();
 
-  public SubtypingForrestForClasses(
-      AppView<AppInfoWithLiveness> appView, List<DexProgramClass> classesWithDeterministicOrder) {
+  public SubtypingForrestForClasses(AppView<AppInfoWithLiveness> appView) {
     this.appView = appView;
-    calculateSubtyping(classesWithDeterministicOrder);
+    calculateSubtyping(appView.appInfo().classes());
   }
 
   private DexProgramClass superClass(DexProgramClass clazz) {
@@ -65,13 +64,14 @@
     return roots;
   }
 
-  private Collection<DexProgramClass> getSubtypesFor(DexProgramClass clazz) {
+  public Collection<DexProgramClass> getSubtypesFor(DexProgramClass clazz) {
     return subtypeMap.getOrDefault(clazz, Collections.emptyList());
   }
 
-  public <T> void traverseNodeDepthFirst(
+  public <T> T traverseNodeDepthFirst(
       DexProgramClass clazz, T state, BiFunction<DexProgramClass, T, T> consumer) {
     T newState = consumer.apply(clazz, state);
     getSubtypesFor(clazz).forEach(subClazz -> traverseNodeDepthFirst(subClazz, newState, consumer));
+    return newState;
   }
 }
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/TreeFixer.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/TreeFixer.java
index 8cf6265..a7ce343 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/TreeFixer.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/TreeFixer.java
@@ -11,6 +11,7 @@
 import com.android.tools.r8.graph.DexField;
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexMethodSignature;
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexProto;
 import com.android.tools.r8.graph.DexString;
@@ -19,15 +20,12 @@
 import com.android.tools.r8.shaking.AnnotationFixer;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.shaking.FieldAccessInfoCollectionModifier;
-import com.android.tools.r8.utils.MethodSignatureEquivalence;
 import com.android.tools.r8.utils.OptionalBool;
-import com.google.common.base.Equivalence.Wrapper;
 import com.google.common.collect.BiMap;
 import com.google.common.collect.HashBiMap;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Sets;
 import java.util.Collections;
-import java.util.HashMap;
 import java.util.IdentityHashMap;
 import java.util.LinkedHashSet;
 import java.util.List;
@@ -49,7 +47,7 @@
   private final DexItemFactory dexItemFactory;
   private final BiMap<DexMethod, DexMethod> movedMethods = HashBiMap.create();
   private final SyntheticArgumentClass syntheticArgumentClass;
-  private final BiMap<Wrapper<DexMethod>, Wrapper<DexMethod>> reservedInterfaceSignatures =
+  private final BiMap<DexMethodSignature, DexMethodSignature> reservedInterfaceSignatures =
       HashBiMap.create();
 
   public TreeFixer(
@@ -124,11 +122,10 @@
     Iterables.filter(classes, DexProgramClass::isInterface).forEach(this::fixupInterfaceClass);
 
     classes.forEach(this::fixupProgramClassSuperType);
-    SubtypingForrestForClasses subtypingForrest = new SubtypingForrestForClasses(appView, classes);
+    SubtypingForrestForClasses subtypingForrest = new SubtypingForrestForClasses(appView);
     // TODO(b/170078037): parallelize this code segment.
     for (DexProgramClass root : subtypingForrest.getProgramRoots()) {
-      subtypingForrest.traverseNodeDepthFirst(
-          root, new IdentityHashMap<>(), this::fixupProgramClass);
+      subtypingForrest.traverseNodeDepthFirst(root, HashBiMap.create(), this::fixupProgramClass);
     }
 
     lensBuilder.remapMethods(movedMethods);
@@ -143,28 +140,24 @@
     clazz.superType = fixupType(clazz.superType);
   }
 
-  private Map<Wrapper<DexMethod>, DexString> fixupProgramClass(
-      DexProgramClass clazz, Map<Wrapper<DexMethod>, DexString> remappedVirtualMethods) {
+  private BiMap<DexMethodSignature, DexMethodSignature> fixupProgramClass(
+      DexProgramClass clazz, BiMap<DexMethodSignature, DexMethodSignature> remappedVirtualMethods) {
     assert !clazz.isInterface();
 
     // TODO(b/169395592): ensure merged classes have been removed using:
     //   assert !mergedClasses.hasBeenMergedIntoDifferentType(clazz.type);
 
-    Map<Wrapper<DexMethod>, DexString> remappedClassVirtualMethods =
-        new HashMap<>(remappedVirtualMethods);
+    BiMap<DexMethodSignature, DexMethodSignature> remappedClassVirtualMethods =
+        HashBiMap.create(remappedVirtualMethods);
 
-    Set<DexMethod> newVirtualMethodReferences = Sets.newIdentityHashSet();
+    Set<DexMethodSignature> newMethodReferences = Sets.newHashSet();
     clazz
         .getMethodCollection()
         .replaceAllVirtualMethods(
-            method ->
-                fixupVirtualMethod(
-                    remappedClassVirtualMethods, newVirtualMethodReferences, method));
-
-    Set<DexMethod> newDirectMethodReferences = Sets.newIdentityHashSet();
+            method -> fixupVirtualMethod(remappedClassVirtualMethods, newMethodReferences, method));
     clazz
         .getMethodCollection()
-        .replaceAllDirectMethods(method -> fixupDirectMethod(newDirectMethodReferences, method));
+        .replaceAllDirectMethods(method -> fixupDirectMethod(newMethodReferences, method));
 
     fixupFields(clazz.staticFields(), clazz::setStaticField);
     fixupFields(clazz.instanceFields(), clazz::setInstanceField);
@@ -184,23 +177,19 @@
       return method;
     }
 
-    MethodSignatureEquivalence equivalence = MethodSignatureEquivalence.get();
-    Wrapper<DexMethod> originalMethodSignature = equivalence.wrap(originalMethodReference);
-    Wrapper<DexMethod> newMethodSignature =
+    DexMethodSignature originalMethodSignature = originalMethodReference.getSignature();
+    DexMethodSignature newMethodSignature =
         reservedInterfaceSignatures.get(originalMethodSignature);
 
     if (newMethodSignature == null) {
-      newMethodSignature = equivalence.wrap(fixupMethodReference(originalMethodReference));
+      newMethodSignature = fixupMethodReference(originalMethodReference).getSignature();
 
       // If the signature is already reserved by another interface, find a fresh one.
       if (reservedInterfaceSignatures.containsValue(newMethodSignature)) {
         DexString name =
             dexItemFactory.createGloballyFreshMemberString(
                 originalMethodReference.getName().toSourceString());
-        newMethodSignature =
-            equivalence.wrap(
-                dexItemFactory.createMethod(
-                    newMethodSignature.get().holder, newMethodSignature.get().proto, name));
+        newMethodSignature = newMethodSignature.withName(name);
       }
 
       assert !reservedInterfaceSignatures.containsValue(newMethodSignature);
@@ -208,16 +197,14 @@
     }
 
     DexMethod newMethodReference =
-        newMethodSignature
-            .get()
-            .withHolder(originalMethodReference.getHolderType(), dexItemFactory);
+        newMethodSignature.withHolder(originalMethodReference, dexItemFactory);
     movedMethods.put(originalMethodReference, newMethodReference);
 
     return method.toTypeSubstitutedMethod(newMethodReference);
   }
 
   private void fixupInterfaceClass(DexProgramClass iface) {
-    Set<DexMethod> newDirectMethods = new LinkedHashSet<>();
+    Set<DexMethodSignature> newDirectMethods = new LinkedHashSet<>();
 
     assert iface.superType == dexItemFactory.objectType;
     iface.superType = mergedClasses.getMergeTargetOrDefault(iface.superType);
@@ -251,13 +238,14 @@
     return newMethod;
   }
 
-  private DexEncodedMethod fixupDirectMethod(Set<DexMethod> newMethods, DexEncodedMethod method) {
+  private DexEncodedMethod fixupDirectMethod(
+      Set<DexMethodSignature> newMethods, DexEncodedMethod method) {
     DexMethod originalMethodReference = method.getReference();
 
     // Fix all type references in the method prototype.
     DexMethod newMethodReference = fixupMethodReference(originalMethodReference);
 
-    if (newMethods.contains(newMethodReference)) {
+    if (newMethods.contains(newMethodReference.getSignature())) {
       // If the method collides with a direct method on the same class then rename it to a globally
       // fresh name and record the signature.
 
@@ -267,45 +255,44 @@
             dexItemFactory.createInstanceInitializerWithFreshProto(
                 newMethodReference,
                 syntheticArgumentClass.getArgumentClass(),
-                tryMethod -> !newMethods.contains(tryMethod));
+                tryMethod -> !newMethods.contains(tryMethod.getSignature()));
         int extraNulls = newMethodReference.getArity() - originalMethodReference.getArity();
         lensBuilder.addExtraParameters(
             originalMethodReference,
             Collections.nCopies(extraNulls, new ExtraUnusedNullParameter()));
       } else {
-        DexString newMethodName =
-            dexItemFactory.createGloballyFreshMemberString(
-                originalMethodReference.getName().toSourceString(), null);
         newMethodReference =
-            dexItemFactory.createMethod(
-                newMethodReference.holder, newMethodReference.proto, newMethodName);
+            dexItemFactory.createFreshMethodName(
+                newMethodReference.getName().toSourceString(),
+                null,
+                newMethodReference.proto,
+                newMethodReference.holder,
+                tryMethod ->
+                    !reservedInterfaceSignatures.containsValue(tryMethod.getSignature())
+                        && !newMethods.contains(tryMethod.getSignature()));
       }
     }
 
-    boolean changed = newMethods.add(newMethodReference);
+    boolean changed = newMethods.add(newMethodReference.getSignature());
     assert changed;
 
     return fixupProgramMethod(newMethodReference, method);
   }
 
-  private DexString lookupReservedVirtualName(
+  private DexMethodSignature lookupReservedVirtualName(
       DexMethod originalMethodReference,
-      Map<Wrapper<DexMethod>, DexString> renamedClassVirtualMethods) {
-    Wrapper<DexMethod> originalSignature =
-        MethodSignatureEquivalence.get().wrap(originalMethodReference);
+      BiMap<DexMethodSignature, DexMethodSignature> renamedClassVirtualMethods) {
+    DexMethodSignature originalSignature = originalMethodReference.getSignature();
 
     // Determine if the original method has been rewritten by a parent class
-    DexString renamedVirtualName =
-        renamedClassVirtualMethods != null
-            ? renamedClassVirtualMethods.get(originalSignature)
-            : null;
+    DexMethodSignature renamedVirtualName = renamedClassVirtualMethods.get(originalSignature);
 
     if (renamedVirtualName == null) {
       // Determine if there is a signature mapping.
-      Wrapper<DexMethod> mappedInterfaceSignature =
+      DexMethodSignature mappedInterfaceSignature =
           reservedInterfaceSignatures.get(originalSignature);
       if (mappedInterfaceSignature != null) {
-        renamedVirtualName = mappedInterfaceSignature.get().name;
+        renamedVirtualName = mappedInterfaceSignature;
       }
     } else {
       assert !reservedInterfaceSignatures.containsKey(originalSignature);
@@ -315,51 +302,57 @@
   }
 
   private DexEncodedMethod fixupVirtualMethod(
-      Map<Wrapper<DexMethod>, DexString> renamedClassVirtualMethods,
-      Set<DexMethod> newMethods,
+      BiMap<DexMethodSignature, DexMethodSignature> renamedClassVirtualMethods,
+      Set<DexMethodSignature> newMethods,
       DexEncodedMethod method) {
     DexMethod originalMethodReference = method.getReference();
-    Wrapper<DexMethod> originalSignature =
-        MethodSignatureEquivalence.get().wrap(originalMethodReference);
+    DexMethodSignature originalSignature = originalMethodReference.getSignature();
 
-    DexString renamedVirtualName =
+    DexMethodSignature renamedVirtualName =
         lookupReservedVirtualName(originalMethodReference, renamedClassVirtualMethods);
 
     // Fix all type references in the method prototype.
-    DexMethod newMethodReference = fixupMethodReference(originalMethodReference);
-    Wrapper<DexMethod> newSignature = MethodSignatureEquivalence.get().wrap(newMethodReference);
+    DexMethodSignature newSignature = fixupMethodSignature(originalSignature);
 
     if (renamedVirtualName != null) {
       // If the method was renamed in a parent, rename it in the child.
-      newMethodReference = newMethodReference.withName(renamedVirtualName, dexItemFactory);
+      newSignature = renamedVirtualName;
 
-      assert !newMethods.contains(newMethodReference);
+      assert !newMethods.contains(newSignature);
     } else if (reservedInterfaceSignatures.containsValue(newSignature)
-        || newMethods.contains(newMethodReference)) {
+        || newMethods.contains(newSignature)
+        || renamedClassVirtualMethods.containsValue(newSignature)) {
       // If the method potentially collides with an interface method or with another virtual method
       // rename it to a globally fresh name and record the name.
 
-      DexString newMethodName =
-          dexItemFactory.createGloballyFreshMemberString(
-              originalMethodReference.getName().toSourceString(), null);
-      newMethodReference = newMethodReference.withName(newMethodName, dexItemFactory);
+      newSignature =
+          dexItemFactory.createFreshMethodSignatureName(
+              originalMethodReference.getName().toSourceString(),
+              null,
+              newSignature.getProto(),
+              trySignature ->
+                  !reservedInterfaceSignatures.containsValue(trySignature)
+                      && !newMethods.contains(trySignature)
+                      && !renamedClassVirtualMethods.containsValue(trySignature));
 
       // Record signature renaming so that subclasses perform the identical rename.
-      renamedClassVirtualMethods.put(originalSignature, newMethodReference.getName());
+      renamedClassVirtualMethods.put(originalSignature, newSignature);
     } else {
       // There was no reserved name and the new signature is available.
 
       if (Iterables.any(
-          newMethodReference.proto.getParameterBaseTypes(dexItemFactory),
+          newSignature.getProto().getParameterBaseTypes(dexItemFactory),
           mergedClasses::isMergeTarget)) {
         // If any of the parameter types have been merged, record the signature mapping.
-        renamedClassVirtualMethods.put(originalSignature, newMethodReference.getName());
+        renamedClassVirtualMethods.put(originalSignature, newSignature);
       }
     }
 
-    boolean changed = newMethods.add(newMethodReference);
+    boolean changed = newMethods.add(newSignature);
     assert changed;
 
+    DexMethod newMethodReference =
+        newSignature.withHolder(fixupType(originalMethodReference.holder), dexItemFactory);
     return fixupProgramMethod(newMethodReference, method);
   }
 
@@ -406,6 +399,10 @@
         .createMethod(fixupType(method.holder), fixupProto(method.proto), method.name);
   }
 
+  private DexMethodSignature fixupMethodSignature(DexMethodSignature signature) {
+    return signature.withProto(fixupProto(signature.getProto()));
+  }
+
   private DexProto fixupProto(DexProto proto) {
     DexProto result = protoFixupCache.get(proto);
     if (result == null) {
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/VirtualMethodMerger.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/VirtualMethodMerger.java
index 14488b6..07a3172 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/VirtualMethodMerger.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/VirtualMethodMerger.java
@@ -59,18 +59,15 @@
 
     /** Get the super method handle if this method overrides a parent method. */
     private DexMethod superMethod(AppView<AppInfoWithLiveness> appView, DexProgramClass target) {
-      // TODO(b/167981556): Correctly detect super methods defined on interfaces.
       DexMethod template = methods.iterator().next().getReference();
       SingleResolutionResult resolutionResult =
           appView
-              .withLiveness()
               .appInfo()
               .resolveMethodOnClass(template, target.getSuperType())
               .asSingleResolution();
-      if (resolutionResult == null) {
-        return null;
-      }
-      if (resolutionResult.getResolvedMethod().isAbstract()) {
+
+      if (resolutionResult == null || resolutionResult.getResolvedMethod().isAbstract()) {
+        // If there is no super method or the method is abstract it should not be called.
         return null;
       }
       if (resolutionResult.getResolvedHolder().isInterface()) {
@@ -84,17 +81,26 @@
     }
 
     public VirtualMethodMerger build(
-        AppView<AppInfoWithLiveness> appView, DexProgramClass target, DexField classIdField) {
-      DexMethod superMethod = superMethod(appView, target);
+        AppView<AppInfoWithLiveness> appView,
+        DexProgramClass target,
+        DexField classIdField,
+        int mergeGroupSize) {
+      // If not all the classes are in the merge group, find the fallback super method to call.
+      DexMethod superMethod = methods.size() < mergeGroupSize ? superMethod(appView, target) : null;
+
       return new VirtualMethodMerger(appView, target, methods, classIdField, superMethod);
     }
   }
 
-  public int getArity() {
-    return methods.iterator().next().getReference().getArity();
+  public DexMethod getMethodReference() {
+    return methods.iterator().next().getReference();
   }
 
-  private DexMethod moveMethod(ProgramMethod oldMethod) {
+  public int getArity() {
+    return getMethodReference().getArity();
+  }
+
+  private DexMethod moveMethod(ClassMethodsBuilder classMethodsBuilder, ProgramMethod oldMethod) {
     DexMethod oldMethodReference = oldMethod.getReference();
     DexMethod method =
         dexItemFactory.createFreshMethodName(
@@ -102,18 +108,14 @@
             oldMethod.getHolderType(),
             oldMethodReference.proto,
             target.type,
-            tryMethod -> target.lookupMethod(tryMethod) == null);
-
-    if (oldMethod.getHolderType() == target.type) {
-      target.removeMethod(oldMethod.getReference());
-    }
+            classMethodsBuilder::isFresh);
 
     DexEncodedMethod encodedMethod = oldMethod.getDefinition().toTypeSubstitutedMethod(method);
     MethodAccessFlags flags = encodedMethod.accessFlags;
     flags.unsetProtected();
     flags.unsetPublic();
     flags.setPrivate();
-    target.addDirectMethod(encodedMethod);
+    classMethodsBuilder.addDirectMethod(encodedMethod);
 
     return encodedMethod.method;
   }
@@ -127,24 +129,26 @@
     return flags;
   }
 
-
   /**
    * If there is only a single method that does not override anything then it is safe to just move
    * it to the target type if it is not already in it.
    */
-  public void mergeTrivial(HorizontalClassMergerGraphLens.Builder lensBuilder) {
-    ProgramMethod method = methods.iterator().next();
+  public void mergeTrivial(
+      ClassMethodsBuilder classMethodsBuilder, HorizontalClassMergerGraphLens.Builder lensBuilder) {
+    DexEncodedMethod method = methods.iterator().next().getDefinition();
 
     if (method.getHolderType() != target.type) {
       // If the method is not in the target type, move it and record it in the lens.
-      DexEncodedMethod newMethod =
-          method.getDefinition().toRenamedHolderMethod(target.type, dexItemFactory);
-      target.addVirtualMethod(newMethod);
-      lensBuilder.moveMethod(method.getReference(), newMethod.getReference());
+      DexMethod originalReference = method.getReference();
+      method = method.toRenamedHolderMethod(target.type, dexItemFactory);
+      lensBuilder.moveMethod(originalReference, method.getReference());
     }
+
+    classMethodsBuilder.addVirtualMethod(method);
   }
 
   public void merge(
+      ClassMethodsBuilder classMethodsBuilder,
       HorizontalClassMergerGraphLens.Builder lensBuilder,
       FieldAccessInfoCollectionModifier.Builder fieldAccessChangesBuilder,
       Reference2IntMap classIdentifiers) {
@@ -153,7 +157,7 @@
 
     // Handle trivial merges.
     if (superMethod == null && methods.size() == 1) {
-      mergeTrivial(lensBuilder);
+      mergeTrivial(classMethodsBuilder, lensBuilder);
       return;
     }
 
@@ -165,7 +169,7 @@
         CfVersion methodVersion = method.getDefinition().getClassFileVersion();
         classFileVersion = CfVersion.maxAllowNull(classFileVersion, methodVersion);
       }
-      DexMethod newMethod = moveMethod(method);
+      DexMethod newMethod = moveMethod(classMethodsBuilder, method);
       lensBuilder.mapMethod(newMethod, newMethod);
       lensBuilder.mapMethodInverse(method.getReference(), newMethod);
       classIdToMethodMap.put(classIdentifiers.getInt(method.getHolderType()), newMethod);
@@ -181,7 +185,7 @@
             null,
             originalMethodReference.proto,
             originalMethodReference.getHolderType(),
-            tryMethod -> target.lookupMethod(tryMethod) == null);
+            classMethodsBuilder::isFresh);
 
     DexMethod newMethodReference =
         dexItemFactory.createMethod(target.type, templateReference.proto, templateReference.name);
@@ -209,7 +213,7 @@
     }
     lensBuilder.recordExtraOriginalSignature(bridgeMethodReference, newMethodReference);
 
-    target.addVirtualMethod(newMethod);
+    classMethodsBuilder.addVirtualMethod(newMethod);
 
     fieldAccessChangesBuilder.fieldReadByMethod(classIdField, newMethod.method);
   }
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/ClassesHaveSameInterfaces.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/ClassesHaveSameInterfaces.java
new file mode 100644
index 0000000..060e1a6
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/ClassesHaveSameInterfaces.java
@@ -0,0 +1,17 @@
+// Copyright (c) 2020, 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.horizontalclassmerging.policies;
+
+import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.graph.DexTypeList;
+import com.android.tools.r8.horizontalclassmerging.MultiClassSameReferencePolicy;
+
+public class ClassesHaveSameInterfaces extends MultiClassSameReferencePolicy<DexTypeList> {
+
+  @Override
+  public DexTypeList getMergeKey(DexProgramClass clazz) {
+    return clazz.interfaces.getSorted();
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NoClassesWithInterfaces.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NoClassesWithInterfaces.java
deleted file mode 100644
index 56e6756..0000000
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NoClassesWithInterfaces.java
+++ /dev/null
@@ -1,16 +0,0 @@
-// Copyright (c) 2020, 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.horizontalclassmerging.policies;
-
-import com.android.tools.r8.graph.DexProgramClass;
-import com.android.tools.r8.horizontalclassmerging.SingleClassPolicy;
-
-public class NoClassesWithInterfaces extends SingleClassPolicy {
-
-  @Override
-  public boolean canMerge(DexProgramClass program) {
-    return program.interfaces.isEmpty();
-  }
-}
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NoKotlinMetadata.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NoKotlinMetadata.java
new file mode 100644
index 0000000..92f2938
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NoKotlinMetadata.java
@@ -0,0 +1,36 @@
+// Copyright (c) 2020, 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.horizontalclassmerging.policies;
+
+import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.horizontalclassmerging.SingleClassPolicy;
+import com.google.common.collect.Streams;
+
+public class NoKotlinMetadata extends SingleClassPolicy {
+
+  public NoKotlinMetadata() {}
+
+  @Override
+  public boolean canMerge(DexProgramClass clazz) {
+    assert verifyNoUnexpectedKotlinInfo(clazz);
+    return true;
+  }
+
+  private boolean verifyNoUnexpectedKotlinInfo(DexProgramClass clazz) {
+    if (clazz.getKotlinInfo().isNoKotlinInformation()) {
+      assert verifyNoUnexpectedKotlinMemberInfo(clazz);
+      return true;
+    }
+    assert clazz.getKotlinInfo().isSyntheticClass()
+        && clazz.getKotlinInfo().asSyntheticClass().isLambda();
+    return true;
+  }
+
+  private boolean verifyNoUnexpectedKotlinMemberInfo(DexProgramClass clazz) {
+    assert Streams.stream(clazz.members())
+        .allMatch(member -> member.getKotlinMemberInfo().isNoKotlinInformation());
+    return true;
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NotMatchedByNoHorizontalClassMerging.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NotMatchedByNoHorizontalClassMerging.java
index 2311f16..5b11ff5 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NotMatchedByNoHorizontalClassMerging.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/NotMatchedByNoHorizontalClassMerging.java
@@ -8,18 +8,26 @@
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.horizontalclassmerging.SingleClassPolicy;
+import com.android.tools.r8.ir.analysis.proto.EnumLiteProtoShrinker;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import java.util.Collections;
 import java.util.Set;
 
 public class NotMatchedByNoHorizontalClassMerging extends SingleClassPolicy {
+
+  private final Set<DexType> deadEnumLiteMaps;
   private final Set<DexType> neverMergeClassHorizontally;
 
   public NotMatchedByNoHorizontalClassMerging(AppView<AppInfoWithLiveness> appView) {
+    deadEnumLiteMaps =
+        appView.withProtoEnumShrinker(
+            EnumLiteProtoShrinker::getDeadEnumLiteMaps, Collections.emptySet());
     neverMergeClassHorizontally = appView.appInfo().getNoHorizontalClassMergingSet();
   }
 
   @Override
   public boolean canMerge(DexProgramClass program) {
-    return !neverMergeClassHorizontally.contains(program.getReference());
+    return !deadEnumLiteMaps.contains(program.getType())
+        && !neverMergeClassHorizontally.contains(program.getType());
   }
 }
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/PreventMethodImplementation.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/PreventMethodImplementation.java
new file mode 100644
index 0000000..b8083e1
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/policies/PreventMethodImplementation.java
@@ -0,0 +1,173 @@
+// Copyright (c) 2020, 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.horizontalclassmerging.policies;
+
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexClass;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexMethodSignature;
+import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.ResolutionResult.SingleResolutionResult;
+import com.android.tools.r8.horizontalclassmerging.MultiClassPolicy;
+import com.android.tools.r8.horizontalclassmerging.SubtypingForrestForClasses;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.utils.collections.DexMethodSignatureSet;
+import java.util.Collection;
+import java.util.IdentityHashMap;
+import java.util.LinkedHashMap;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+
+/**
+ * Prevent merging of classes where subclasses contain interface with default methods and the merged
+ * class would contain a method with the same signature. Consider the following example: <code>
+ *   class A {}
+ *   class B {
+ *     public void m() {
+ *       // ...
+ *     }
+ *   }
+ *
+ *   interface {
+ *     default void m() {
+ *       // ...
+ *     }
+ *   }
+ *
+ *   class C extends A implements I {
+ *   }
+ * </code>
+ *
+ * <p>If A and B are merged, then the resulting class contains the method {@code void m()}. When
+ * resolving m on C, the method would point to the method on the merged class rather than the
+ * default interface method, changing runtime behaviour.
+ *
+ * <p>See: https://docs.oracle.com/javase/specs/jvms/se15/html/jvms-5.html#jvms-5.4.3.3)
+ */
+public class PreventMethodImplementation extends MultiClassPolicy {
+  private final AppView<AppInfoWithLiveness> appView;
+  private final SubtypingForrestForClasses subtypingForrestForClasses;
+
+  private final InterfaceDefaultSignaturesCache interfaceDefaultMethodsCache =
+      new InterfaceDefaultSignaturesCache();
+  private final ParentClassSignaturesCache parentClassMethodsCache =
+      new ParentClassSignaturesCache();
+  private final ReservedInterfaceSignaturesFor reservedInterfaceSignaturesFor =
+      new ReservedInterfaceSignaturesFor();
+
+  private abstract static class SignaturesCache<C extends DexClass> {
+    private final Map<DexClass, DexMethodSignatureSet> memoizedSignatures = new IdentityHashMap<>();
+
+    public DexMethodSignatureSet getOrComputeSignatures(C clazz) {
+      return memoizedSignatures.computeIfAbsent(
+          clazz,
+          ignore -> {
+            DexMethodSignatureSet signatures = DexMethodSignatureSet.createLinked();
+            process(clazz, signatures);
+            return signatures;
+          });
+    }
+
+    abstract void process(C clazz, DexMethodSignatureSet signatures);
+  }
+
+  private abstract class DexClassSignaturesCache extends SignaturesCache<DexClass> {
+
+    DexMethodSignatureSet getOrComputeSignatures(DexType type) {
+      DexClass clazz = appView.definitionFor(type);
+      return clazz != null ? getOrComputeSignatures(clazz) : null;
+    }
+  }
+
+  private class InterfaceDefaultSignaturesCache extends DexClassSignaturesCache {
+
+    @Override
+    void process(DexClass clazz, DexMethodSignatureSet signatures) {
+      signatures.addAllMethods(clazz.virtualMethods(DexEncodedMethod::isDefaultMethod));
+      signatures.addAll(clazz.getInterfaces(), this::getOrComputeSignatures);
+    }
+  }
+
+  private class ParentClassSignaturesCache extends DexClassSignaturesCache {
+
+    @Override
+    void process(DexClass clazz, DexMethodSignatureSet signatures) {
+      signatures.addAllMethods(clazz.methods());
+      if (clazz.getSuperType() != null) {
+        DexClass superClass = appView.definitionFor(clazz.getSuperType());
+        if (superClass != null) {
+          signatures.addAll(getOrComputeSignatures(superClass));
+        }
+      }
+    }
+  }
+
+  private class ReservedInterfaceSignaturesFor extends SignaturesCache<DexProgramClass> {
+
+    @Override
+    void process(DexProgramClass clazz, DexMethodSignatureSet signatures) {
+      signatures.addAll(
+          clazz.getInterfaces(), interfaceDefaultMethodsCache::getOrComputeSignatures);
+      signatures.addAll(
+          subtypingForrestForClasses.getSubtypesFor(clazz), this::getOrComputeSignatures);
+      signatures.removeAllMethods(clazz.methods());
+    }
+  }
+
+  public PreventMethodImplementation(AppView<AppInfoWithLiveness> appView) {
+    this.appView = appView;
+    this.subtypingForrestForClasses = new SubtypingForrestForClasses(appView);
+  }
+
+  enum MethodCategory {
+    CLASS_HIERARCHY_SAFE,
+    KEEP_ABSENT,
+  }
+
+  static class DispatchSignature extends LinkedHashMap<DexMethodSignature, MethodCategory> {
+    void addSignature(DexMethodSignature signature, MethodCategory category) {
+      MethodCategory old = put(signature, category);
+      assert old == null;
+    }
+  }
+
+  DexMethodSignatureSet computeReservedSignaturesForClass(DexProgramClass clazz) {
+    DexMethodSignatureSet reservedSignatures =
+        DexMethodSignatureSet.create(reservedInterfaceSignaturesFor.getOrComputeSignatures(clazz));
+    reservedSignatures.removeAll(parentClassMethodsCache.getOrComputeSignatures(clazz));
+    return reservedSignatures;
+  }
+
+  @Override
+  public Collection<List<DexProgramClass>> apply(List<DexProgramClass> group) {
+    DexMethodSignatureSet signatures = DexMethodSignatureSet.createLinked();
+    for (DexProgramClass clazz : group) {
+      signatures.addAllMethods(clazz.methods());
+    }
+
+    Map<DispatchSignature, List<DexProgramClass>> newGroups = new LinkedHashMap<>();
+    for (DexProgramClass clazz : group) {
+      DexMethodSignatureSet clazzReserved = computeReservedSignaturesForClass(clazz);
+      DispatchSignature dispatchSignature = new DispatchSignature();
+      for (DexMethodSignature signature : signatures) {
+        MethodCategory category = MethodCategory.CLASS_HIERARCHY_SAFE;
+        if (clazzReserved.contains(signature)) {
+          DexMethod template = signature.withHolder(clazz, appView.dexItemFactory());
+          SingleResolutionResult result =
+              appView.appInfo().resolveMethodOnClass(template, clazz).asSingleResolution();
+          if (result == null || result.getResolvedHolder().isInterface()) {
+            category = MethodCategory.KEEP_ABSENT;
+          }
+        }
+        dispatchSignature.addSignature(signature, category);
+      }
+      newGroups.computeIfAbsent(dispatchSignature, ignore -> new LinkedList<>()).add(clazz);
+    }
+    return removeTrivialGroups(newGroups.values());
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/proto/EnumLiteProtoShrinker.java b/src/main/java/com/android/tools/r8/ir/analysis/proto/EnumLiteProtoShrinker.java
index 055882b..0b04f9b 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/proto/EnumLiteProtoShrinker.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/proto/EnumLiteProtoShrinker.java
@@ -45,6 +45,10 @@
     this.references = references;
   }
 
+  public Set<DexType> getDeadEnumLiteMaps() {
+    return deadEnumLiteMaps;
+  }
+
   private DexField createInternalValueMapField(DexType holder) {
     return appView
         .dexItemFactory()
@@ -52,9 +56,7 @@
   }
 
   public void clearDeadEnumLiteMaps() {
-    if (!appView.options().protoShrinking().enableEnumLiteProtoShrinking) {
-      return;
-    }
+    assert appView.options().protoShrinking().isProtoEnumShrinkingEnabled();
     // The optimization only enables further enums to be unboxed, no point to run it if enum
     // unboxing is disabled.
     if (!appView.options().enableEnumUnboxing) {
@@ -70,23 +72,28 @@
 
   private void internalClearDeadEnumLiteMaps() {
     for (DexProgramClass clazz : appView.appInfo().classes()) {
-      if (clazz.interfaces.contains(references.enumLiteMapType)) {
-        DexProgramClass enumLite = computeCorrespondingEnumLite(clazz);
-        if (enumLite != null) {
-          DexEncodedField field = enumLite.lookupField(createInternalValueMapField(enumLite.type));
-          if (field != null) {
-            if (appView.appInfo().isStaticFieldWrittenOnlyInEnclosingStaticInitializer(field)
-                && !appView.appInfo().isFieldRead(field)) {
-              deadEnumLiteMaps.add(clazz.type);
-              // Clears the EnumLiteMap methods to avoid them being IR processed.
-              clazz.setVirtualMethods(DexEncodedMethod.EMPTY_ARRAY);
-            }
-          }
-        }
+      if (isDeadEnumLiteMap(clazz)) {
+        deadEnumLiteMaps.add(clazz.getType());
+        // Clears the EnumLiteMap methods to avoid them being IR processed.
+        clazz.setVirtualMethods(DexEncodedMethod.EMPTY_ARRAY);
       }
     }
   }
 
+  public boolean isDeadEnumLiteMap(DexProgramClass clazz) {
+    if (clazz.getInterfaces().contains(references.enumLiteMapType)) {
+      DexProgramClass enumLite = computeCorrespondingEnumLite(clazz);
+      if (enumLite != null) {
+        DexEncodedField field =
+            enumLite.lookupField(createInternalValueMapField(enumLite.getType()));
+        return field != null
+            && appView.appInfo().isStaticFieldWrittenOnlyInEnclosingStaticInitializer(field)
+            && !appView.appInfo().isFieldRead(field);
+      }
+    }
+    return false;
+  }
+
   /**
    * Each EnumLiteMap subclass has only two virtual methods findValueByNumber:
    *
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/proto/ProtoShrinker.java b/src/main/java/com/android/tools/r8/ir/analysis/proto/ProtoShrinker.java
index 6cec099..2674265 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/proto/ProtoShrinker.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/proto/ProtoShrinker.java
@@ -42,7 +42,10 @@
         appView.options().protoShrinking().enableGeneratedMessageLiteBuilderShrinking
             ? new GeneratedMessageLiteBuilderShrinker(appView, references)
             : null;
-    this.enumProtoShrinker = new EnumLiteProtoShrinker(appView, references);
+    this.enumProtoShrinker =
+        appView.options().protoShrinking().isProtoEnumShrinkingEnabled()
+            ? new EnumLiteProtoShrinker(appView, references)
+            : null;
     this.references = references;
   }
 
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 b2c5888..8ba06e0 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
@@ -1497,7 +1497,7 @@
 
     if (interfaceMethodRewriter != null) {
       timing.begin("Rewrite interface methods");
-      interfaceMethodRewriter.rewriteMethodReferences(method, code);
+      interfaceMethodRewriter.rewriteMethodReferences(code);
       timing.end();
       assert code.isConsistentSSA();
     }
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 2f56b0d..d6f6264 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
@@ -5,6 +5,7 @@
 package com.android.tools.r8.ir.desugar;
 
 import com.android.tools.r8.DesugarGraphConsumer;
+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.AppInfo;
@@ -18,7 +19,6 @@
 import com.android.tools.r8.graph.DexEncodedField;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexItemFactory;
-import com.android.tools.r8.graph.DexLibraryClass;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexMethodHandle;
 import com.android.tools.r8.graph.DexProgramClass;
@@ -28,6 +28,7 @@
 import com.android.tools.r8.graph.DexValue;
 import com.android.tools.r8.graph.GenericSignature;
 import com.android.tools.r8.graph.GenericSignature.ClassSignature;
+import com.android.tools.r8.graph.MethodAccessFlags;
 import com.android.tools.r8.graph.ProgramMethod;
 import com.android.tools.r8.graph.ResolutionResult.SingleResolutionResult;
 import com.android.tools.r8.ir.code.BasicBlock;
@@ -41,6 +42,7 @@
 import com.android.tools.r8.ir.conversion.IRConverter;
 import com.android.tools.r8.ir.desugar.DefaultMethodsHelper.Collection;
 import com.android.tools.r8.ir.desugar.InterfaceProcessor.InterfaceProcessorNestedGraphLens;
+import com.android.tools.r8.ir.synthetic.ForwardMethodBuilder;
 import com.android.tools.r8.origin.Origin;
 import com.android.tools.r8.origin.SynthesizedOrigin;
 import com.android.tools.r8.position.MethodPosition;
@@ -61,10 +63,8 @@
 import java.util.List;
 import java.util.ListIterator;
 import java.util.Map;
-import java.util.Map.Entry;
 import java.util.Set;
 import java.util.concurrent.ConcurrentHashMap;
-import java.util.concurrent.ConcurrentMap;
 import java.util.concurrent.ExecutionException;
 import java.util.concurrent.ExecutorService;
 import java.util.function.BiConsumer;
@@ -120,10 +120,6 @@
   // Caches default interface method info for already processed interfaces.
   private final Map<DexType, DefaultMethodsHelper.Collection> cache = new ConcurrentHashMap<>();
 
-  /** Interfaces requiring dispatch classes to be created, and appropriate callers. */
-  private final ConcurrentMap<DexLibraryClass, Set<DexProgramClass>> requiredDispatchClasses =
-      new ConcurrentHashMap<>();
-
   /**
    * Defines a minor variation in desugaring.
    */
@@ -220,7 +216,9 @@
 
   // Rewrites the references to static and default interface methods.
   // NOTE: can be called for different methods concurrently.
-  public void rewriteMethodReferences(DexEncodedMethod encodedMethod, IRCode code) {
+  public void rewriteMethodReferences(IRCode code) {
+    ProgramMethod context = code.context();
+    DexEncodedMethod encodedMethod = context.getDefinition();
     if (synthesizedMethods.contains(encodedMethod)) {
       return;
     }
@@ -278,14 +276,36 @@
                 // so the user class is not rejected because it make this call directly.
                 // TODO(b/166247515): If this an incorrect invoke-static without the interface bit
                 //  we end up "fixing" the code and remove and ICCE error.
+                ProgramMethod newProgramMethod =
+                    appView
+                        .getSyntheticItems()
+                        .createMethod(
+                            context.getHolder(),
+                            factory,
+                            syntheticMethodBuilder -> {
+                              syntheticMethodBuilder
+                                  .setProto(method.proto)
+                                  .setAccessFlags(
+                                      MethodAccessFlags.fromSharedAccessFlags(
+                                          Constants.ACC_PUBLIC
+                                              | Constants.ACC_STATIC
+                                              | Constants.ACC_SYNTHETIC,
+                                          false))
+                                  .setCode(
+                                      m ->
+                                          ForwardMethodBuilder.builder(factory)
+                                              .setStaticTarget(method, true)
+                                              .setStaticSource(m)
+                                              .build());
+                            });
                 instructions.replaceCurrentInstruction(
                     new InvokeStatic(
-                        staticAsMethodOfDispatchClass(method),
+                        newProgramMethod.getReference(),
                         invokeStatic.outValue(),
                         invokeStatic.arguments()));
-                requiredDispatchClasses
-                    .computeIfAbsent(clazz.asLibraryClass(), k -> Sets.newConcurrentHashSet())
-                    .add(appInfo.definitionFor(encodedMethod.holder()).asProgramClass());
+                synchronized (synthesizedMethods) {
+                  synthesizedMethods.add(newProgramMethod);
+                }
               }
             } else {
               instructions.replaceCurrentInstruction(
@@ -961,7 +981,7 @@
     InterfaceProcessorNestedGraphLens.Builder graphLensBuilder =
         InterfaceProcessorNestedGraphLens.builder();
     Map<DexClass, DexProgramClass> classMapping =
-        processInterfaces(builder, flavour, graphLensBuilder);
+        processInterfaces(builder, flavour, graphLensBuilder, synthesizedMethods::add);
     InterfaceProcessorNestedGraphLens graphLens =
         graphLensBuilder.build(appView.dexItemFactory(), appView.graphLens());
     if (appView.enableWholeProgramOptimizations() && graphLens != null) {
@@ -1026,7 +1046,6 @@
   private void clear() {
     this.cache.clear();
     this.synthesizedMethods.clear();
-    this.requiredDispatchClasses.clear();
   }
 
   private static boolean shouldProcess(
@@ -1038,17 +1057,14 @@
   private Map<DexClass, DexProgramClass> processInterfaces(
       Builder<?> builder,
       Flavor flavour,
-      InterfaceProcessorNestedGraphLens.Builder graphLensBuilder) {
+      InterfaceProcessorNestedGraphLens.Builder graphLensBuilder,
+      Consumer<ProgramMethod> newSynthesizedMethodConsumer) {
     InterfaceProcessor processor = new InterfaceProcessor(appView, this);
     for (DexProgramClass clazz : builder.getProgramClasses()) {
       if (shouldProcess(clazz, flavour, true)) {
-        processor.process(clazz, graphLensBuilder);
+        processor.process(clazz, graphLensBuilder, newSynthesizedMethodConsumer);
       }
     }
-    for (Entry<DexLibraryClass, Set<DexProgramClass>> entry : requiredDispatchClasses.entrySet()) {
-      DexProgramClass dispatchClass = processor.process(entry.getKey(), entry.getValue());
-      dispatchClass.forEachProgramMethod(synthesizedMethods::add);
-    }
     return processor.syntheticClasses;
   }
 
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 99230aa..fbeb14a 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
@@ -4,14 +4,21 @@
 
 package com.android.tools.r8.ir.desugar;
 
+import static com.android.tools.r8.utils.PredicateUtils.not;
+
+import com.android.tools.r8.cf.code.CfFieldInstruction;
 import com.android.tools.r8.cf.code.CfInstruction;
 import com.android.tools.r8.cf.code.CfInvoke;
+import com.android.tools.r8.cf.code.CfReturnVoid;
+import com.android.tools.r8.cf.code.CfStackInstruction;
+import com.android.tools.r8.cf.code.CfStackInstruction.Opcode;
 import com.android.tools.r8.code.Instruction;
 import com.android.tools.r8.code.InvokeSuper;
 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.CfCode;
 import com.android.tools.r8.graph.ClassAccessFlags;
 import com.android.tools.r8.graph.Code;
 import com.android.tools.r8.graph.DexAnnotationSet;
@@ -26,18 +33,24 @@
 import com.android.tools.r8.graph.DexProgramClass.ChecksumSupplier;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.DexTypeList;
+import com.android.tools.r8.graph.DexValue.DexValueNull;
+import com.android.tools.r8.graph.FieldAccessFlags;
 import com.android.tools.r8.graph.GenericSignature.ClassSignature;
+import com.android.tools.r8.graph.GenericSignature.FieldTypeSignature;
 import com.android.tools.r8.graph.GenericSignature.MethodTypeSignature;
 import com.android.tools.r8.graph.GraphLens;
 import com.android.tools.r8.graph.GraphLens.NestedGraphLens;
 import com.android.tools.r8.graph.MethodAccessFlags;
+import com.android.tools.r8.graph.MethodCollection;
 import com.android.tools.r8.graph.ParameterAnnotationsList;
+import com.android.tools.r8.graph.ProgramMethod;
 import com.android.tools.r8.ir.code.Invoke.Type;
 import com.android.tools.r8.ir.synthetic.ForwardMethodBuilder;
 import com.android.tools.r8.origin.SynthesizedOrigin;
 import com.android.tools.r8.utils.Pair;
 import com.google.common.collect.BiMap;
 import com.google.common.collect.HashBiMap;
+import com.google.common.collect.ImmutableList;
 import java.util.ArrayDeque;
 import java.util.ArrayList;
 import java.util.Collections;
@@ -47,6 +60,8 @@
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
+import java.util.function.Consumer;
+import org.objectweb.asm.Opcodes;
 
 // Default and static method interface desugaring processor for interfaces.
 //
@@ -68,126 +83,22 @@
     this.rewriter = rewriter;
   }
 
-  void process(DexProgramClass iface, InterfaceProcessorNestedGraphLens.Builder graphLensBuilder) {
+  void process(
+      DexProgramClass iface,
+      InterfaceProcessorNestedGraphLens.Builder graphLensBuilder,
+      Consumer<ProgramMethod> newSynthesizedMethodConsumer) {
     assert iface.isInterface();
     // The list of methods to be created in companion class.
     List<DexEncodedMethod> companionMethods = new ArrayList<>();
 
+    ensureCompanionClassInitializesInterface(iface, companionMethods);
+
     // Process virtual interface methods first.
-    List<DexEncodedMethod> remainingMethods = new ArrayList<>();
-    for (DexEncodedMethod virtual : iface.virtualMethods()) {
-      if (rewriter.isDefaultMethod(virtual)) {
-        if (!canMoveToCompanionClass(virtual)) {
-          throw new CompilationError("One or more instruction is preventing default interface "
-              + "method from being desugared: " + virtual.method.toSourceString(), iface.origin);
-        }
-
-        // Create a new method in a companion class to represent default method implementation.
-        DexMethod companionMethod = rewriter.defaultAsMethodOfCompanionClass(virtual.method);
-
-        Code code = virtual.getCode();
-        if (code == null) {
-          throw new CompilationError("Code is missing for default "
-              + "interface method: " + virtual.method.toSourceString(), iface.origin);
-        }
-
-        MethodAccessFlags newFlags = virtual.accessFlags.copy();
-        newFlags.unsetBridge();
-        newFlags.promoteToStatic();
-        DexEncodedMethod.setDebugInfoWithFakeThisParameter(
-            code, companionMethod.getArity(), appView);
-        DexEncodedMethod implMethod =
-            new DexEncodedMethod(
-                companionMethod,
-                newFlags,
-                virtual.getGenericSignature(),
-                virtual.annotations(),
-                virtual.parameterAnnotationsList,
-                code,
-                true);
-        implMethod.copyMetadata(virtual);
-        virtual.setDefaultInterfaceMethodImplementation(implMethod);
-        companionMethods.add(implMethod);
-        graphLensBuilder.recordCodeMovedToCompanionClass(virtual.method, implMethod.method);
-      }
-
-      // Remove bridge methods.
-      if (interfaceMethodRemovalChangesApi(virtual, iface)) {
-        remainingMethods.add(virtual);
-      }
-    }
-
-    // If at least one bridge method was removed then update the table.
-    if (remainingMethods.size() < iface.getMethodCollection().numberOfVirtualMethods()) {
-      iface.setVirtualMethods(remainingMethods.toArray(DexEncodedMethod.EMPTY_ARRAY));
-    }
-    remainingMethods.clear();
+    processVirtualInterfaceMethods(iface, companionMethods, graphLensBuilder);
 
     // Process static and private methods, move them into companion class as well,
     // make private instance methods public static.
-    for (DexEncodedMethod direct : iface.directMethods()) {
-      MethodAccessFlags originalFlags = direct.accessFlags;
-      MethodAccessFlags newFlags = originalFlags.copy();
-      if (originalFlags.isPrivate()) {
-        newFlags.promoteToPublic();
-      }
-      DexMethod oldMethod = direct.method;
-      if (isStaticMethod(direct)) {
-        assert originalFlags.isPrivate() || originalFlags.isPublic()
-            : "Static interface method " + direct.toSourceString() + " is expected to "
-            + "either be public or private in " + iface.origin;
-        DexMethod companionMethod = rewriter.staticAsMethodOfCompanionClass(oldMethod);
-        DexEncodedMethod implMethod =
-            new DexEncodedMethod(
-                companionMethod,
-                newFlags,
-                direct.getGenericSignature(),
-                direct.annotations(),
-                direct.parameterAnnotationsList,
-                direct.getCode(),
-                true);
-        implMethod.copyMetadata(direct);
-        companionMethods.add(implMethod);
-        graphLensBuilder.move(oldMethod, companionMethod);
-      } else {
-        if (originalFlags.isPrivate()) {
-          assert !rewriter.factory.isClassConstructor(oldMethod)
-              : "Unexpected private constructor " + direct.toSourceString()
-              + " in " + iface.origin;
-          newFlags.promoteToStatic();
-
-          DexMethod companionMethod = rewriter.privateAsMethodOfCompanionClass(oldMethod);
-
-          Code code = direct.getCode();
-          if (code == null) {
-            throw new CompilationError("Code is missing for private instance "
-                + "interface method: " + oldMethod.toSourceString(), iface.origin);
-          }
-          DexEncodedMethod.setDebugInfoWithFakeThisParameter(
-              code, companionMethod.getArity(), appView);
-          DexEncodedMethod implMethod =
-              new DexEncodedMethod(
-                  companionMethod,
-                  newFlags,
-                  direct.getGenericSignature(),
-                  direct.annotations(),
-                  direct.parameterAnnotationsList,
-                  code,
-                  true);
-          implMethod.copyMetadata(direct);
-          companionMethods.add(implMethod);
-          graphLensBuilder.move(oldMethod, companionMethod);
-        } else {
-          // Since there are no interface constructors at this point,
-          // this should only be class constructor.
-          assert rewriter.factory.isClassConstructor(oldMethod);
-          remainingMethods.add(direct);
-        }
-      }
-    }
-    if (remainingMethods.size() < iface.getMethodCollection().numberOfDirectMethods()) {
-      iface.setDirectMethods(remainingMethods.toArray(DexEncodedMethod.EMPTY_ARRAY));
-    }
+    processDirectInterfaceMethods(iface, companionMethods, graphLensBuilder);
 
     if (companionMethods.isEmpty()) {
       return; // No methods to create, companion class not needed.
@@ -227,6 +138,218 @@
             getChecksumSupplier(iface),
             Collections.singletonList(iface));
     syntheticClasses.put(iface, companionClass);
+    if (companionClass.hasClassInitializer()) {
+      newSynthesizedMethodConsumer.accept(companionClass.getProgramClassInitializer());
+    }
+  }
+
+  private void ensureCompanionClassInitializesInterface(
+      DexProgramClass iface, List<DexEncodedMethod> companionMethods) {
+    if (!hasStaticMethodThatTriggersNonTrivialClassInitializer(iface)) {
+      return;
+    }
+    DexEncodedField clinitField =
+        findExistingStaticClinitFieldToTriggerInterfaceInitialization(iface);
+    if (clinitField == null) {
+      clinitField = createStaticClinitFieldToTriggerInterfaceInitialization(iface);
+      iface.appendStaticField(clinitField);
+    }
+    companionMethods.add(createCompanionClassInitializer(iface, clinitField));
+  }
+
+  private boolean hasStaticMethodThatTriggersNonTrivialClassInitializer(DexProgramClass iface) {
+    return iface.hasClassInitializer()
+        && iface
+            .getMethodCollection()
+            .hasDirectMethods(method -> method.isStatic() && !method.isClassInitializer());
+  }
+
+  private DexEncodedField findExistingStaticClinitFieldToTriggerInterfaceInitialization(
+      DexProgramClass iface) {
+    for (DexEncodedField field : iface.staticFields(not(DexEncodedField::isPrivate))) {
+      return field;
+    }
+    return null;
+  }
+
+  private DexEncodedField createStaticClinitFieldToTriggerInterfaceInitialization(
+      DexProgramClass iface) {
+    DexItemFactory dexItemFactory = appView.dexItemFactory();
+    DexField clinitFieldTemplateReference =
+        dexItemFactory.createField(iface.getType(), dexItemFactory.intType, "$desugar$clinit");
+    DexField clinitFieldReference =
+        dexItemFactory.createFreshFieldName(
+            clinitFieldTemplateReference, candidate -> iface.lookupField(candidate) != null);
+    return new DexEncodedField(
+        clinitFieldReference,
+        FieldAccessFlags.builder().setPackagePrivate().setStatic().setSynthetic().build(),
+        FieldTypeSignature.noSignature(),
+        DexAnnotationSet.empty(),
+        DexValueNull.NULL);
+  }
+
+  private DexEncodedMethod createCompanionClassInitializer(
+      DexProgramClass iface, DexEncodedField clinitField) {
+    DexType companionType = rewriter.getCompanionClassType(iface.getType());
+    DexMethod clinitMethodReference = appView.dexItemFactory().createClinitMethod(companionType);
+    CfCode code =
+        new CfCode(
+            companionType,
+            1,
+            0,
+            ImmutableList.of(
+                new CfFieldInstruction(
+                    Opcodes.GETSTATIC, clinitField.getReference(), clinitField.getReference()),
+                new CfStackInstruction(Opcode.Pop),
+                new CfReturnVoid()),
+            ImmutableList.of(),
+            ImmutableList.of());
+    return new DexEncodedMethod(
+        clinitMethodReference,
+        MethodAccessFlags.builder().setConstructor().setPackagePrivate().setStatic().build(),
+        MethodTypeSignature.noSignature(),
+        DexAnnotationSet.empty(),
+        ParameterAnnotationsList.empty(),
+        code,
+        true,
+        iface.hasClassFileVersion() ? iface.getInitialClassFileVersion() : null);
+  }
+
+  private void processVirtualInterfaceMethods(
+      DexProgramClass iface,
+      List<DexEncodedMethod> companionMethods,
+      InterfaceProcessorNestedGraphLens.Builder graphLensBuilder) {
+    List<DexEncodedMethod> newVirtualMethods = new ArrayList<>();
+    for (DexEncodedMethod virtual : iface.virtualMethods()) {
+      if (rewriter.isDefaultMethod(virtual)) {
+        if (!canMoveToCompanionClass(virtual)) {
+          throw new CompilationError("One or more instruction is preventing default interface "
+              + "method from being desugared: " + virtual.method.toSourceString(), iface.origin);
+        }
+
+        // Create a new method in a companion class to represent default method implementation.
+        DexMethod companionMethod = rewriter.defaultAsMethodOfCompanionClass(virtual.method);
+
+        Code code = virtual.getCode();
+        if (code == null) {
+          throw new CompilationError("Code is missing for default "
+              + "interface method: " + virtual.method.toSourceString(), iface.origin);
+        }
+
+        MethodAccessFlags newFlags = virtual.accessFlags.copy();
+        newFlags.unsetBridge();
+        newFlags.promoteToStatic();
+        DexEncodedMethod.setDebugInfoWithFakeThisParameter(
+            code, companionMethod.getArity(), appView);
+        DexEncodedMethod implMethod =
+            new DexEncodedMethod(
+                companionMethod,
+                newFlags,
+                virtual.getGenericSignature(),
+                virtual.annotations(),
+                virtual.parameterAnnotationsList,
+                code,
+                true);
+        implMethod.copyMetadata(virtual);
+        virtual.setDefaultInterfaceMethodImplementation(implMethod);
+        companionMethods.add(implMethod);
+        graphLensBuilder.recordCodeMovedToCompanionClass(virtual.method, implMethod.method);
+      }
+
+      // Remove bridge methods.
+      if (interfaceMethodRemovalChangesApi(virtual, iface)) {
+        newVirtualMethods.add(virtual);
+      }
+    }
+
+    // If at least one bridge method was removed then update the table.
+    if (newVirtualMethods.size() < iface.getMethodCollection().numberOfVirtualMethods()) {
+      iface.setVirtualMethods(newVirtualMethods.toArray(DexEncodedMethod.EMPTY_ARRAY));
+    }
+  }
+
+  private void processDirectInterfaceMethods(
+      DexProgramClass iface,
+      List<DexEncodedMethod> companionMethods,
+      InterfaceProcessorNestedGraphLens.Builder graphLensBuilder) {
+    DexEncodedMethod clinit = null;
+    for (DexEncodedMethod method : iface.directMethods()) {
+      if (method.isClassInitializer()) {
+        clinit = method;
+        continue;
+      }
+      if (method.isInstanceInitializer()) {
+        assert false
+            : "Unexpected interface instance initializer: "
+                + method.getReference().toSourceString();
+        continue;
+      }
+
+      MethodAccessFlags originalFlags = method.getAccessFlags();
+      MethodAccessFlags newFlags = originalFlags.copy();
+      if (originalFlags.isPrivate()) {
+        newFlags.promoteToPublic();
+      }
+
+      DexMethod oldMethod = method.getReference();
+      if (isStaticMethod(method)) {
+        assert originalFlags.isPrivate() || originalFlags.isPublic()
+            : "Static interface method "
+                + method.toSourceString()
+                + " is expected to "
+                + "either be public or private in "
+                + iface.origin;
+        DexMethod companionMethod = rewriter.staticAsMethodOfCompanionClass(oldMethod);
+        DexEncodedMethod implMethod =
+            new DexEncodedMethod(
+                companionMethod,
+                newFlags,
+                method.getGenericSignature(),
+                method.annotations(),
+                method.parameterAnnotationsList,
+                method.getCode(),
+                true);
+        implMethod.copyMetadata(method);
+        companionMethods.add(implMethod);
+        graphLensBuilder.move(oldMethod, companionMethod);
+        continue;
+      }
+
+      assert originalFlags.isPrivate();
+
+      newFlags.promoteToStatic();
+
+      DexMethod companionMethod = rewriter.privateAsMethodOfCompanionClass(oldMethod);
+
+      Code code = method.getCode();
+      if (code == null) {
+        throw new CompilationError(
+            "Code is missing for private instance "
+                + "interface method: "
+                + oldMethod.toSourceString(),
+            iface.origin);
+      }
+      DexEncodedMethod.setDebugInfoWithFakeThisParameter(code, companionMethod.getArity(), appView);
+      DexEncodedMethod implMethod =
+          new DexEncodedMethod(
+              companionMethod,
+              newFlags,
+              method.getGenericSignature(),
+              method.annotations(),
+              method.parameterAnnotationsList,
+              code,
+              true);
+      implMethod.copyMetadata(method);
+      companionMethods.add(implMethod);
+      graphLensBuilder.move(oldMethod, companionMethod);
+    }
+
+    MethodCollection methodCollection = iface.getMethodCollection();
+    if (clinit != null) {
+      methodCollection.setSingleDirectMethod(clinit);
+    } else {
+      methodCollection.clearDirectMethods();
+    }
   }
 
   private ChecksumSupplier getChecksumSupplier(DexProgramClass iface) {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/ArgumentRemovalUtils.java b/src/main/java/com/android/tools/r8/ir/optimize/ArgumentRemovalUtils.java
index 5892466..28bbf14 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/ArgumentRemovalUtils.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/ArgumentRemovalUtils.java
@@ -14,9 +14,9 @@
   // remove method arguments.
   public static boolean isPinned(DexEncodedMethod method, AppView<AppInfoWithLiveness> appView) {
     return appView.appInfo().isPinned(method.method)
-        || appView.appInfo().bootstrapMethods.contains(method.method)
-        || appView.appInfo().failedResolutionTargets.contains(method.method)
-        || appView.appInfo().methodsTargetedByInvokeDynamic.contains(method.method)
+        || appView.appInfo().isBootstrapMethod(method.method)
+        || appView.appInfo().isFailedResolutionTarget(method.method)
+        || appView.appInfo().isMethodTargetedByInvokeDynamic(method.method)
         || method.accessFlags.isNative();
   }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java b/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java
index 9f790ec..945d9fe 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java
@@ -126,7 +126,7 @@
     AppInfoWithLiveness appInfo = appView.appInfo();
     DexMethod singleTargetReference = singleTarget.getReference();
     if (singleTarget.getDefinition().getOptimizationInfo().forceInline()
-        && appInfo.neverInline.contains(singleTargetReference)) {
+        && appInfo.isNeverInlineMethod(singleTargetReference)) {
       throw new Unreachable();
     }
 
@@ -143,7 +143,7 @@
       return true;
     }
 
-    if (appInfo.neverInline.contains(singleTargetReference)) {
+    if (appInfo.isNeverInlineMethod(singleTargetReference)) {
       whyAreYouNotInliningReporter.reportMarkedAsNeverInline();
       return true;
     }
@@ -1091,8 +1091,8 @@
 
           if (inlineeMayHaveInvokeMethod && options.applyInliningToInlinee) {
             if (inlineeStack.size() + 1 > options.applyInliningToInlineeMaxDepth
-                && appView.appInfo().alwaysInline.isEmpty()
-                && appView.appInfo().forceInline.isEmpty()) {
+                && appView.appInfo().hasNoAlwaysInlineMethods()
+                && appView.appInfo().hasNoForceInlineMethods()) {
               continue;
             }
             // Record that we will be inside the inlinee until the next block.
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/UnusedArgumentsCollector.java b/src/main/java/com/android/tools/r8/ir/optimize/UnusedArgumentsCollector.java
index 0dd84e7..509daa1 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/UnusedArgumentsCollector.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/UnusedArgumentsCollector.java
@@ -224,7 +224,7 @@
 
               // If this is a method with known resolution issues, then don't remove any unused
               // arguments.
-              if (appView.appInfo().failedResolutionTargets.contains(method.method)) {
+              if (appView.appInfo().isFailedResolutionTarget(method.method)) {
                 return method;
               }
 
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/inliner/DefaultInliningReasonStrategy.java b/src/main/java/com/android/tools/r8/ir/optimize/inliner/DefaultInliningReasonStrategy.java
index ae543a2..bb270b9 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/inliner/DefaultInliningReasonStrategy.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/inliner/DefaultInliningReasonStrategy.java
@@ -36,12 +36,12 @@
     DexMethod targetReference = target.getReference();
     if (targetMethod.getOptimizationInfo().forceInline()
         || (appView.appInfo().hasLiveness()
-            && appView.withLiveness().appInfo().forceInline.contains(targetReference))) {
-      assert !appView.appInfo().neverInline.contains(targetReference);
+            && appView.withLiveness().appInfo().isForceInlineMethod(targetReference))) {
+      assert !appView.appInfo().isNeverInlineMethod(targetReference);
       return Reason.FORCE;
     }
     if (appView.appInfo().hasLiveness()
-        && appView.withLiveness().appInfo().alwaysInline.contains(targetReference)) {
+        && appView.withLiveness().appInfo().isAlwaysInlineMethod(targetReference)) {
       return Reason.ALWAYS;
     }
     if (appView.options().disableInliningOfLibraryMethodOverrides
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinClassMetadataReader.java b/src/main/java/com/android/tools/r8/kotlin/KotlinClassMetadataReader.java
index df06499..6b011a6 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinClassMetadataReader.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinClassMetadataReader.java
@@ -5,6 +5,7 @@
 
 import static com.android.tools.r8.kotlin.KotlinMetadataUtils.INVALID_KOTLIN_INFO;
 import static com.android.tools.r8.kotlin.KotlinMetadataUtils.NO_KOTLIN_INFO;
+import static com.android.tools.r8.kotlin.KotlinSyntheticClassInfo.getFlavour;
 
 import com.android.tools.r8.graph.DexAnnotation;
 import com.android.tools.r8.graph.DexAnnotationElement;
@@ -16,6 +17,7 @@
 import com.android.tools.r8.graph.DexString;
 import com.android.tools.r8.graph.DexValue;
 import com.android.tools.r8.graph.DexValue.DexValueArray;
+import com.android.tools.r8.kotlin.KotlinSyntheticClassInfo.Flavour;
 import com.android.tools.r8.utils.Reporter;
 import com.android.tools.r8.utils.StringDiagnostic;
 import java.util.IdentityHashMap;
@@ -24,11 +26,10 @@
 import kotlinx.metadata.InconsistentKotlinMetadataException;
 import kotlinx.metadata.jvm.KotlinClassHeader;
 import kotlinx.metadata.jvm.KotlinClassMetadata;
+import kotlinx.metadata.jvm.KotlinClassMetadata.SyntheticClass;
 
 public final class KotlinClassMetadataReader {
 
-  private static int KOTLIN_METADATA_KIND_LAMBDA = 3;
-
   public static KotlinClassLevelInfo getKotlinInfo(
       Kotlin kotlin,
       DexClass clazz,
@@ -53,7 +54,7 @@
       DexAnnotation annotation) {
     try {
       KotlinClassMetadata kMetadata = toKotlinClassMetadata(kotlin, annotation.annotation);
-      if (onlyProcessLambda && kMetadata.getHeader().getKind() != KOTLIN_METADATA_KIND_LAMBDA) {
+      if (onlyProcessLambda && !isSyntheticClassifiedLambda(kotlin, clazz, kMetadata)) {
         return NO_KOTLIN_INFO;
       }
       return createKotlinInfo(kotlin, clazz, kMetadata, factory, reporter, keepByteCode);
@@ -76,6 +77,16 @@
     }
   }
 
+  private static boolean isSyntheticClassifiedLambda(
+      Kotlin kotlin, DexClass clazz, KotlinClassMetadata kMetadata) {
+    if (kMetadata instanceof SyntheticClass) {
+      SyntheticClass syntheticClass = (SyntheticClass) kMetadata;
+      return syntheticClass.isLambda()
+          && getFlavour(syntheticClass, clazz, kotlin) != Flavour.Unclassified;
+    }
+    return false;
+  }
+
   public static boolean hasKotlinClassMetadataAnnotation(
       DexClass clazz, DexDefinitionSupplier definitionSupplier) {
     return clazz
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinFieldLevelInfo.java b/src/main/java/com/android/tools/r8/kotlin/KotlinFieldLevelInfo.java
index 8d9d468..acf2d64 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinFieldLevelInfo.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinFieldLevelInfo.java
@@ -4,9 +4,7 @@
 
 package com.android.tools.r8.kotlin;
 
-import com.android.tools.r8.shaking.EnqueuerMetadataTraceable;
-
-public interface KotlinFieldLevelInfo extends EnqueuerMetadataTraceable {
+public interface KotlinFieldLevelInfo extends KotlinMemberLevelInfo {
 
   default boolean isCompanion() {
     return false;
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinMemberLevelInfo.java b/src/main/java/com/android/tools/r8/kotlin/KotlinMemberLevelInfo.java
new file mode 100644
index 0000000..f7312ad
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinMemberLevelInfo.java
@@ -0,0 +1,14 @@
+// Copyright (c) 2020, 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.shaking.EnqueuerMetadataTraceable;
+
+public interface KotlinMemberLevelInfo extends EnqueuerMetadataTraceable {
+
+  default boolean isNoKotlinInformation() {
+    return false;
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinMethodLevelInfo.java b/src/main/java/com/android/tools/r8/kotlin/KotlinMethodLevelInfo.java
index a02cb0a..a43e677 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinMethodLevelInfo.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinMethodLevelInfo.java
@@ -4,9 +4,7 @@
 
 package com.android.tools.r8.kotlin;
 
-import com.android.tools.r8.shaking.EnqueuerMetadataTraceable;
-
-public interface KotlinMethodLevelInfo extends EnqueuerMetadataTraceable {
+public interface KotlinMethodLevelInfo extends KotlinMemberLevelInfo {
 
   default boolean isConstructor() {
     return false;
diff --git a/src/main/java/com/android/tools/r8/kotlin/KotlinSyntheticClassInfo.java b/src/main/java/com/android/tools/r8/kotlin/KotlinSyntheticClassInfo.java
index 41147a5..36bf5cf 100644
--- a/src/main/java/com/android/tools/r8/kotlin/KotlinSyntheticClassInfo.java
+++ b/src/main/java/com/android/tools/r8/kotlin/KotlinSyntheticClassInfo.java
@@ -110,7 +110,7 @@
     return metadataVersion;
   }
 
-  private static Flavour getFlavour(
+  public static Flavour getFlavour(
       KotlinClassMetadata.SyntheticClass metadata, DexClass clazz, Kotlin kotlin) {
     // Returns KotlinStyleLambda if the given clazz is a Kotlin-style lambda:
     //   a class that
diff --git a/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java b/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java
index 0922f50..30d9b7d 100644
--- a/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java
+++ b/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java
@@ -176,7 +176,8 @@
       // and there is therefore no need to check the hierarchy above.
       MemberPool<DexMethod> memberPool = methodPoolCollection.get(method.getHolder());
       Wrapper<DexMethod> methodKey = MethodSignatureEquivalence.get().wrap(method.getReference());
-      if (memberPool.hasSeenStrictlyBelow(methodKey)) {
+      if (memberPool.hasSeenStrictlyBelow(methodKey)
+          && appView.options().enablePackagePrivateAwarePublicization) {
         return false;
       }
       doPublicize(method);
diff --git a/src/main/java/com/android/tools/r8/repackaging/RepackagingTreeFixer.java b/src/main/java/com/android/tools/r8/repackaging/RepackagingTreeFixer.java
index 845df2c..07af4a3 100644
--- a/src/main/java/com/android/tools/r8/repackaging/RepackagingTreeFixer.java
+++ b/src/main/java/com/android/tools/r8/repackaging/RepackagingTreeFixer.java
@@ -36,6 +36,7 @@
   private final Map<DexType, DexType> repackagedClasses;
 
   private final Map<DexType, DexProgramClass> newProgramClasses = new IdentityHashMap<>();
+  private final Map<DexType, DexProgramClass> synthesizedFromClasses = new IdentityHashMap<>();
   private final Map<DexProto, DexProto> protoFixupCache = new IdentityHashMap<>();
 
   public RepackagingTreeFixer(
@@ -241,8 +242,12 @@
     for (DexProgramClass clazz : synthesizedFrom) {
       // TODO(b/165783399): What do we want to put here if the class that this was synthesized from
       //  is no longer in the application?
+      Map<DexType, DexProgramClass> classes =
+          appView.appInfo().definitionForWithoutExistenceAssert(clazz.getType()) != null
+              ? newProgramClasses
+              : synthesizedFromClasses;
       DexProgramClass newClass =
-          newProgramClasses.computeIfAbsent(clazz.getType(), ignore -> fixupClass(clazz));
+          classes.computeIfAbsent(clazz.getType(), ignore -> fixupClass(clazz));
       newSynthesizedFrom.add(newClass);
       changed |= newClass != clazz;
     }
diff --git a/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java b/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
index 6922939..4d5a549 100644
--- a/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
+++ b/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
@@ -99,24 +99,25 @@
    * contained in {@link #liveMethods}, it may be marked as abstract and its implementation may be
    * removed.
    */
-  final SortedSet<DexMethod> targetedMethods;
+  private final Set<DexMethod> targetedMethods;
 
   /** Set of targets that lead to resolution errors, such as non-existing or invalid targets. */
-  public final Set<DexMethod> failedResolutionTargets;
+  private final Set<DexMethod> failedResolutionTargets;
 
   /**
    * Set of program methods that are used as the bootstrap method for an invoke-dynamic instruction.
    */
-  public final SortedSet<DexMethod> bootstrapMethods;
+  private final Set<DexMethod> bootstrapMethods;
+
   /** Set of methods that are the immediate target of an invoke-dynamic. */
-  public final SortedSet<DexMethod> methodsTargetedByInvokeDynamic;
+  private final Set<DexMethod> methodsTargetedByInvokeDynamic;
   /** Set of virtual methods that are the immediate target of an invoke-direct. */
-  final SortedSet<DexMethod> virtualMethodsTargetedByInvokeDirect;
+  private final Set<DexMethod> virtualMethodsTargetedByInvokeDirect;
   /**
    * Set of methods that belong to live classes and can be reached by invokes. These need to be
    * kept.
    */
-  public final SortedSet<DexMethod> liveMethods;
+  private final Set<DexMethod> liveMethods;
   /**
    * Information about all fields that are accessed by the program. The information includes whether
    * a given field is read/written by the program, and it also includes all indirect accesses to
@@ -141,11 +142,11 @@
   /** All items with assumevalues rule. */
   public final Map<DexMember<?, ?>, ProguardMemberRule> assumedValues;
   /** All methods that should be inlined if possible due to a configuration directive. */
-  public final Set<DexMethod> alwaysInline;
+  private final Set<DexMethod> alwaysInline;
   /** All methods that *must* be inlined due to a configuration directive (testing only). */
-  public final Set<DexMethod> forceInline;
+  private final Set<DexMethod> forceInline;
   /** All methods that *must* never be inlined due to a configuration directive (testing only). */
-  public final Set<DexMethod> neverInline;
+  private final Set<DexMethod> neverInline;
   /** Items for which to print inlining decisions for (testing only). */
   public final Set<DexMethod> whyAreYouNotInlining;
   /** All methods that may not have any parameters with a constant value removed. */
@@ -205,12 +206,12 @@
       Set<DexType> missingTypes,
       Set<DexType> liveTypes,
       Set<DexType> instantiatedAppServices,
-      SortedSet<DexMethod> targetedMethods,
+      Set<DexMethod> targetedMethods,
       Set<DexMethod> failedResolutionTargets,
-      SortedSet<DexMethod> bootstrapMethods,
-      SortedSet<DexMethod> methodsTargetedByInvokeDynamic,
-      SortedSet<DexMethod> virtualMethodsTargetedByInvokeDirect,
-      SortedSet<DexMethod> liveMethods,
+      Set<DexMethod> bootstrapMethods,
+      Set<DexMethod> methodsTargetedByInvokeDynamic,
+      Set<DexMethod> virtualMethodsTargetedByInvokeDirect,
+      Set<DexMethod> liveMethods,
       FieldAccessInfoCollectionImpl fieldAccessInfoCollection,
       MethodAccessInfoCollection methodAccessInfoCollection,
       ObjectAllocationInfoCollectionImpl objectAllocationInfoCollection,
@@ -288,10 +289,10 @@
       Set<DexType> missingTypes,
       Set<DexType> liveTypes,
       Set<DexType> instantiatedAppServices,
-      SortedSet<DexMethod> targetedMethods,
+      Set<DexMethod> targetedMethods,
       Set<DexMethod> failedResolutionTargets,
-      SortedSet<DexMethod> bootstrapMethods,
-      SortedSet<DexMethod> methodsTargetedByInvokeDynamic,
+      Set<DexMethod> bootstrapMethods,
+      Set<DexMethod> methodsTargetedByInvokeDynamic,
       SortedSet<DexMethod> virtualMethodsTargetedByInvokeDirect,
       SortedSet<DexMethod> liveMethods,
       FieldAccessInfoCollectionImpl fieldAccessInfoCollection,
@@ -626,6 +627,54 @@
     return clazz == null || !clazz.isProgramClass();
   }
 
+  public boolean isLiveMethod(DexMethod method) {
+    return liveMethods.contains(method);
+  }
+
+  public boolean isTargetedMethod(DexMethod method) {
+    return targetedMethods.contains(method);
+  }
+
+  public boolean isFailedResolutionTarget(DexMethod method) {
+    return failedResolutionTargets.contains(method);
+  }
+
+  public Set<DexMethod> getFailedResolutionTargets() {
+    return failedResolutionTargets;
+  }
+
+  public boolean isBootstrapMethod(DexMethod method) {
+    return bootstrapMethods.contains(method);
+  }
+
+  public boolean isMethodTargetedByInvokeDynamic(DexMethod method) {
+    return methodsTargetedByInvokeDynamic.contains(method);
+  }
+
+  public Set<DexMethod> getVirtualMethodsTargetedByInvokeDirect() {
+    return virtualMethodsTargetedByInvokeDirect;
+  }
+
+  public boolean isAlwaysInlineMethod(DexMethod method) {
+    return alwaysInline.contains(method);
+  }
+
+  public boolean hasNoAlwaysInlineMethods() {
+    return alwaysInline.isEmpty();
+  }
+
+  public boolean isForceInlineMethod(DexMethod method) {
+    return forceInline.contains(method);
+  }
+
+  public boolean hasNoForceInlineMethods() {
+    return forceInline.isEmpty();
+  }
+
+  public boolean isNeverInlineMethod(DexMethod method) {
+    return neverInline.contains(method);
+  }
+
   public Collection<DexClass> computeReachableInterfaces() {
     Set<DexClass> interfaces = Sets.newIdentityHashSet();
     WorkList<DexType> worklist = WorkList.newIdentityWorkList();
@@ -1036,11 +1085,11 @@
         lens.rewriteMethods(alwaysInline),
         lens.rewriteMethods(forceInline),
         lens.rewriteMethods(neverInline),
-        lens.rewriteMethods(whyAreYouNotInlining),
-        lens.rewriteMethods(keepConstantArguments),
-        lens.rewriteMethods(keepUnusedArguments),
-        lens.rewriteMethods(reprocess),
-        lens.rewriteMethods(neverReprocess),
+        lens.rewriteMethodsSorted(whyAreYouNotInlining),
+        lens.rewriteMethodsSorted(keepConstantArguments),
+        lens.rewriteMethodsSorted(keepUnusedArguments),
+        lens.rewriteMethodsSorted(reprocess),
+        lens.rewriteMethodsSorted(neverReprocess),
         alwaysClassInline.rewriteItems(lens::lookupType),
         lens.rewriteTypes(neverClassInline),
         lens.rewriteTypes(noUnusedInterfaceRemoval),
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 8e6142e..e032ea2 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -58,7 +58,6 @@
 import com.android.tools.r8.graph.LookupTarget;
 import com.android.tools.r8.graph.MethodAccessInfoCollection;
 import com.android.tools.r8.graph.ObjectAllocationInfoCollectionImpl;
-import com.android.tools.r8.graph.PresortedComparable;
 import com.android.tools.r8.graph.ProgramDefinition;
 import com.android.tools.r8.graph.ProgramField;
 import com.android.tools.r8.graph.ProgramMember;
@@ -104,7 +103,6 @@
 import com.android.tools.r8.shaking.RootSetBuilder.RootSet;
 import com.android.tools.r8.shaking.ScopedDexMethodSet.AddMethodIfMoreVisibleResult;
 import com.android.tools.r8.utils.Action;
-import com.android.tools.r8.utils.DequeUtils;
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.InternalOptions.DesugarState;
 import com.android.tools.r8.utils.IteratorUtils;
@@ -120,7 +118,6 @@
 import com.android.tools.r8.utils.collections.ProgramMethodSet;
 import com.google.common.base.Equivalence.Wrapper;
 import com.google.common.collect.ImmutableSet;
-import com.google.common.collect.ImmutableSortedSet;
 import com.google.common.collect.Maps;
 import com.google.common.collect.Sets;
 import com.google.common.collect.Sets.SetView;
@@ -142,7 +139,6 @@
 import java.util.Map;
 import java.util.Map.Entry;
 import java.util.Set;
-import java.util.SortedSet;
 import java.util.concurrent.ExecutionException;
 import java.util.concurrent.ExecutorService;
 import java.util.function.BiConsumer;
@@ -233,10 +229,25 @@
    * Set of types that are mentioned in the program. We at least need an empty abstract class item
    * for these.
    */
-  private final SetWithReportedReason<DexProgramClass> liveTypes;
+  private final SetWithReportedReason<DexProgramClass> liveTypes = new SetWithReportedReason<>();
 
-  /** Set of types whose class initializer may execute. */
-  private final SetWithReportedReason<DexProgramClass> initializedTypes;
+  /** Set of classes whose initializer may execute. */
+  private final SetWithReportedReason<DexProgramClass> initializedClasses =
+      new SetWithReportedReason<>();
+
+  /**
+   * Set of interfaces whose interface initializer may execute directly in response to a static
+   * field or method access on the interface.
+   */
+  private final SetWithReportedReason<DexProgramClass> directlyInitializedInterfaces =
+      new SetWithReportedReason<>();
+
+  /**
+   * Set of interfaces whose interface initializer may execute indirectly as a side-effect of the
+   * class initialization of a (non-interface) subclass.
+   */
+  private final SetWithReportedReason<DexProgramClass> indirectlyInitializedInterfaces =
+      new SetWithReportedReason<>();
 
   /**
    * Set of live types defined in the library and classpath.
@@ -387,9 +398,6 @@
           shrinker -> registerAnalysis(shrinker.createEnqueuerAnalysis()));
     }
 
-
-    liveTypes = new SetWithReportedReason<>();
-    initializedTypes = new SetWithReportedReason<>();
     targetedMethods = new SetWithReason<>(graphReporter::registerMethod);
     // This set is only populated in edge cases due to multiple default interface methods.
     // The set is generally expected to be empty and in the unlikely chance it is not, it will
@@ -1884,31 +1892,41 @@
   }
 
   private void markDirectAndIndirectClassInitializersAsLive(DexProgramClass clazz) {
-    Deque<DexProgramClass> worklist = DequeUtils.newArrayDeque(clazz);
-    Set<DexProgramClass> visited = SetUtils.newIdentityHashSet(clazz);
-    while (!worklist.isEmpty()) {
-      DexProgramClass current = worklist.removeFirst();
-      assert visited.contains(current);
+    if (clazz.isInterface()) {
+      // Accessing a static field or method on an interface does not trigger the class initializer
+      // of any parent interfaces.
+      markInterfaceInitializedDirectly(clazz);
+      return;
+    }
 
-      if (!markDirectClassInitializerAsLive(current)) {
-        continue;
+    WorkList<DexProgramClass> worklist = WorkList.newIdentityWorkList(clazz);
+    while (worklist.hasNext()) {
+      DexProgramClass current = worklist.next();
+      if (current.isInterface()) {
+        if (!markInterfaceInitializedIndirectly(current)) {
+          continue;
+        }
+      } else {
+        if (!markDirectClassInitializerAsLive(current)) {
+          continue;
+        }
       }
 
       // Mark all class initializers in all super types as live.
-      for (DexType superType : clazz.allImmediateSupertypes()) {
+      for (DexType superType : current.allImmediateSupertypes()) {
         DexProgramClass superClass = getProgramClassOrNull(superType);
-        if (superClass != null && visited.add(superClass)) {
-          worklist.add(superClass);
+        if (superClass != null) {
+          worklist.addIfNotSeen(superClass);
         }
       }
     }
   }
 
-  /** Returns true if the class initializer became live for the first time. */
+  /** Returns true if the class became initialized for the first time. */
   private boolean markDirectClassInitializerAsLive(DexProgramClass clazz) {
     ProgramMethod clinit = clazz.getProgramClassInitializer();
     KeepReasonWitness witness = graphReporter.reportReachableClassInitializer(clazz, clinit);
-    if (!initializedTypes.add(clazz, witness)) {
+    if (!initializedClasses.add(clazz, witness)) {
       return false;
     }
     if (clinit != null && clinit.getDefinition().getOptimizationInfo().mayHaveSideEffects()) {
@@ -1917,6 +1935,57 @@
     return true;
   }
 
+  /**
+   * Marks the interface as initialized directly and promotes the interface initializer to being
+   * live if it isn't already.
+   */
+  private void markInterfaceInitializedDirectly(DexProgramClass clazz) {
+    ProgramMethod clinit = clazz.getProgramClassInitializer();
+    // Mark the interface as initialized directly.
+    KeepReasonWitness witness = graphReporter.reportReachableClassInitializer(clazz, clinit);
+    if (!directlyInitializedInterfaces.add(clazz, witness)) {
+      return;
+    }
+    // Promote the interface initializer to being live if it isn't already.
+    if (clinit == null || !clinit.getDefinition().getOptimizationInfo().mayHaveSideEffects()) {
+      return;
+    }
+    if (indirectlyInitializedInterfaces.contains(clazz)
+        && clazz.getMethodCollection().hasVirtualMethods(DexEncodedMethod::isDefaultMethod)) {
+      assert liveMethods.contains(clinit);
+      return;
+    }
+    markDirectStaticOrConstructorMethodAsLive(clinit, witness);
+  }
+
+  /**
+   * Marks the interface as initialized indirectly and promotes the interface initializer to being
+   * live if the interface has a default interface method and is not already live.
+   *
+   * @return true if the interface became initialized indirectly for the first time.
+   */
+  private boolean markInterfaceInitializedIndirectly(DexProgramClass clazz) {
+    ProgramMethod clinit = clazz.getProgramClassInitializer();
+    // Mark the interface as initialized indirectly.
+    KeepReasonWitness witness = graphReporter.reportReachableClassInitializer(clazz, clinit);
+    if (!indirectlyInitializedInterfaces.add(clazz, witness)) {
+      return false;
+    }
+    // Promote the interface initializer to being live if it has a default interface method and
+    // isn't already live.
+    if (clinit == null
+        || !clinit.getDefinition().getOptimizationInfo().mayHaveSideEffects()
+        || !clazz.getMethodCollection().hasVirtualMethods(DexEncodedMethod::isDefaultMethod)) {
+      return true;
+    }
+    if (directlyInitializedInterfaces.contains(clazz)) {
+      assert liveMethods.contains(clinit);
+      return true;
+    }
+    markDirectStaticOrConstructorMethodAsLive(clinit, witness);
+    return true;
+  }
+
   // Package protected due to entry point from worklist.
   void markNonStaticDirectMethodAsReachable(DexMethod method, KeepReason reason) {
     handleInvokeOfDirectTarget(method, reason);
@@ -3174,13 +3243,12 @@
                 : missingTypes,
             SetUtils.mapIdentityHashSet(liveTypes.getItems(), DexProgramClass::getType),
             Collections.unmodifiableSet(instantiatedAppServices),
-            Enqueuer.toSortedDescriptorSet(targetedMethods.getItems()),
+            Enqueuer.toDescriptorSet(targetedMethods.getItems()),
             Collections.unmodifiableSet(failedResolutionTargets),
-            ImmutableSortedSet.copyOf(DexMethod::slowCompareTo, bootstrapMethods),
-            ImmutableSortedSet.copyOf(DexMethod::slowCompareTo, methodsTargetedByInvokeDynamic),
-            ImmutableSortedSet.copyOf(
-                DexMethod::slowCompareTo, virtualMethodsTargetedByInvokeDirect),
-            toSortedDescriptorSet(liveMethods.getItems()),
+            Collections.unmodifiableSet(bootstrapMethods),
+            Collections.unmodifiableSet(methodsTargetedByInvokeDynamic),
+            Collections.unmodifiableSet(virtualMethodsTargetedByInvokeDirect),
+            toDescriptorSet(liveMethods.getItems()),
             // Filter out library fields and pinned fields, because these are read by default.
             fieldAccessInfoCollection,
             methodAccessInfoCollection.build(),
@@ -3349,9 +3417,8 @@
   }
 
   private static <D extends DexEncodedMember<D, R>, R extends DexMember<D, R>>
-      SortedSet<R> toSortedDescriptorSet(Set<D> set) {
-    ImmutableSortedSet.Builder<R> builder =
-        new ImmutableSortedSet.Builder<>(PresortedComparable::slowCompareTo);
+      Set<R> toDescriptorSet(Set<D> set) {
+    ImmutableSet.Builder<R> builder = new ImmutableSet.Builder<>();
     for (D item : set) {
       builder.add(item.getReference());
     }
@@ -3845,7 +3912,8 @@
         return;
       }
       markTypeAsLive(clazz, KeepReason.reflectiveUseIn(method));
-      if (identifierTypeLookupResult.isTypeInstantiatedFromUse(options)) {
+      if (clazz.canBeInstantiatedByNewInstance()
+          && identifierTypeLookupResult.isTypeInstantiatedFromUse(options)) {
         workList.enqueueMarkInstantiatedAction(
             clazz, null, InstantiationReason.REFLECTION, KeepReason.reflectiveUseIn(method));
         if (clazz.hasDefaultInitializer()) {
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 5199435..7267bac 100644
--- a/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java
+++ b/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java
@@ -1970,12 +1970,12 @@
     public boolean verifyKeptMethodsAreTargetedAndLive(AppInfoWithLiveness appInfo) {
       noShrinking.forEachMethod(
           reference -> {
-            assert appInfo.targetedMethods.contains(reference)
+            assert appInfo.isTargetedMethod(reference)
                 : "Expected kept method `" + reference.toSourceString() + "` to be targeted";
             DexEncodedMethod method =
                 appInfo.definitionForHolder(reference).lookupMethod(reference);
             if (!method.isAbstract() && isKeptDirectlyOrIndirectly(method.holder(), appInfo)) {
-              assert appInfo.liveMethods.contains(reference)
+              assert appInfo.isLiveMethod(reference)
                   : "Expected non-abstract kept method `"
                       + reference.toSourceString()
                       + "` to be live";
diff --git a/src/main/java/com/android/tools/r8/shaking/StaticClassMerger.java b/src/main/java/com/android/tools/r8/shaking/StaticClassMerger.java
index fe5a13a..2a72863 100644
--- a/src/main/java/com/android/tools/r8/shaking/StaticClassMerger.java
+++ b/src/main/java/com/android/tools/r8/shaking/StaticClassMerger.java
@@ -284,7 +284,7 @@
                     || appView.appInfo().isPinned(method.method)
                     // TODO(christofferqa): Remove the invariant that the graph lens should not
                     // modify any methods from the sets alwaysInline and noSideEffects.
-                    || appView.appInfo().alwaysInline.contains(method.method)
+                    || appView.appInfo().isAlwaysInlineMethod(method.method)
                     || appView.appInfo().noSideEffects.keySet().contains(method.method))) {
       return MergeGroup.DONT_MERGE;
     }
diff --git a/src/main/java/com/android/tools/r8/shaking/TreePruner.java b/src/main/java/com/android/tools/r8/shaking/TreePruner.java
index caade38..9d0b174 100644
--- a/src/main/java/com/android/tools/r8/shaking/TreePruner.java
+++ b/src/main/java/com/android/tools/r8/shaking/TreePruner.java
@@ -249,8 +249,7 @@
   private boolean isAttributeReferencingPrunedItem(EnclosingMethodAttribute attr) {
     AppInfoWithLiveness appInfo = appView.appInfo();
     return (attr.getEnclosingClass() != null && !isTypeLive(attr.getEnclosingClass()))
-        || (attr.getEnclosingMethod() != null
-            && !appInfo.liveMethods.contains(attr.getEnclosingMethod()));
+        || (attr.getEnclosingMethod() != null && !appInfo.isLiveMethod(attr.getEnclosingMethod()));
   }
 
   private boolean isAttributeReferencingMissingOrPrunedType(InnerClassAttribute attr) {
@@ -279,7 +278,7 @@
     AppInfoWithLiveness appInfo = appView.appInfo();
     InternalOptions options = appView.options();
     int firstUnreachable =
-        firstUnreachableIndex(methods, method -> appInfo.liveMethods.contains(method.method));
+        firstUnreachableIndex(methods, method -> appInfo.isLiveMethod(method.method));
     // Return the original array if all methods are used.
     if (firstUnreachable == -1) {
       return null;
@@ -290,7 +289,7 @@
     }
     for (int i = firstUnreachable; i < methods.size(); i++) {
       DexEncodedMethod method = methods.get(i);
-      if (appInfo.liveMethods.contains(method.getReference())) {
+      if (appInfo.isLiveMethod(method.getReference())) {
         reachableMethods.add(method);
       } else if (options.configurationDebugging) {
         // Keep the method but rewrite its body, if it has one.
@@ -299,7 +298,7 @@
                 ? method
                 : method.toMethodThatLogsError(appView));
         methodsToKeepForConfigurationDebugging.add(method.method);
-      } else if (appInfo.targetedMethods.contains(method.getReference())) {
+      } else if (appInfo.isTargetedMethod(method.getReference())) {
         // If the method is already abstract, and doesn't have code, let it be.
         if (method.shouldNotHaveCode() && !method.hasCode()) {
           reachableMethods.add(method);
@@ -318,7 +317,7 @@
                 && !method.isSynchronized()
                 && !method.accessFlags.isPrivate()
                 && !method.isStatic()
-                && !appInfo.failedResolutionTargets.contains(method.method);
+                && !appInfo.isFailedResolutionTarget(method.method);
         // Private methods and static methods can only be targeted yet non-live as the result of
         // an invalid invoke. They will not actually be called at runtime but we have to keep them
         // as non-abstract (see above) to produce the same failure mode.
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 9831468..a294f1d 100644
--- a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
+++ b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
@@ -292,12 +292,12 @@
     // another default method in the same interface (see InterfaceMethodDesugaringTests.testInvoke-
     // SpecialToDefaultMethod). However, in a class, that would lead to a verification error.
     // Therefore, we disallow merging such interfaces into their subtypes.
-    for (DexMethod signature : appInfo.virtualMethodsTargetedByInvokeDirect) {
+    for (DexMethod signature : appInfo.getVirtualMethodsTargetedByInvokeDirect()) {
       markTypeAsPinned(signature.holder, AbortReason.UNHANDLED_INVOKE_DIRECT);
     }
 
     // The set of targets that must remain for proper resolution error cases should not be merged.
-    for (DexMethod method : appInfo.failedResolutionTargets) {
+    for (DexMethod method : appInfo.getFailedResolutionTargets()) {
       markTypeAsPinned(method.holder, AbortReason.RESOLUTION_FOR_METHODS_MAY_CHANGE);
     }
   }
@@ -1110,8 +1110,8 @@
       target.forEachField(feedback::markFieldCannotBeKept);
       target.forEachMethod(feedback::markMethodCannotBeKept);
       // Step 3: Clear the members of the source class since they have now been moved to the target.
-      source.setDirectMethods(null);
-      source.setVirtualMethods(null);
+      source.getMethodCollection().clearDirectMethods();
+      source.getMethodCollection().clearVirtualMethods();
       source.setInstanceFields(null);
       source.setStaticFields(null);
       // Step 4: Record merging.
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 dd85ad0..c74ed38 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -262,6 +262,8 @@
   public boolean encodeChecksums = false;
   public BiPredicate<String, Long> dexClassChecksumFilter = (name, checksum) -> true;
   public boolean cfToCfDesugar = false;
+  // TODO(b/172496438): Temporarily enable publicizing package-private overrides.
+  public boolean enablePackagePrivateAwarePublicization = false;
 
   public int callGraphLikelySpuriousCallEdgeThreshold = 50;
 
@@ -1235,6 +1237,10 @@
           || enableGeneratedMessageLiteBuilderShrinking
           || enableEnumLiteProtoShrinking;
     }
+
+    public boolean isProtoEnumShrinkingEnabled() {
+      return enableEnumLiteProtoShrinking;
+    }
   }
 
   public static class TestingOptions {
diff --git a/src/main/java/com/android/tools/r8/utils/ObjectUtils.java b/src/main/java/com/android/tools/r8/utils/ObjectUtils.java
index ac07151..1f3ad9d 100644
--- a/src/main/java/com/android/tools/r8/utils/ObjectUtils.java
+++ b/src/main/java/com/android/tools/r8/utils/ObjectUtils.java
@@ -4,6 +4,7 @@
 
 package com.android.tools.r8.utils;
 
+import java.util.function.Function;
 import java.util.function.Predicate;
 
 public class ObjectUtils {
@@ -14,4 +15,11 @@
     }
     return orElse;
   }
+
+  public static <S, T> T mapNotNull(S object, Function<? super S, ? extends T> fn) {
+    if (object != null) {
+      return fn.apply(object);
+    }
+    return null;
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/utils/collections/DexMethodSignatureSet.java b/src/main/java/com/android/tools/r8/utils/collections/DexMethodSignatureSet.java
new file mode 100644
index 0000000..5a4bc89
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/utils/collections/DexMethodSignatureSet.java
@@ -0,0 +1,95 @@
+// Copyright (c) 2020, 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.utils.collections;
+
+import com.android.tools.r8.graph.DexClassAndMethod;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexMethodSignature;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.LinkedHashSet;
+import java.util.Set;
+import java.util.function.Function;
+
+public class DexMethodSignatureSet implements Iterable<DexMethodSignature> {
+
+  private final Set<DexMethodSignature> backing;
+
+  private DexMethodSignatureSet(Set<DexMethodSignature> backing) {
+    this.backing = backing;
+  }
+
+  public static DexMethodSignatureSet create() {
+    return new DexMethodSignatureSet(new HashSet<>());
+  }
+
+  public static DexMethodSignatureSet create(DexMethodSignatureSet collection) {
+    return new DexMethodSignatureSet(new HashSet<>(collection.backing));
+  }
+
+  public static DexMethodSignatureSet createLinked() {
+    return new DexMethodSignatureSet(new LinkedHashSet<>());
+  }
+
+  public boolean add(DexMethodSignature signature) {
+    return backing.add(signature);
+  }
+
+  public boolean add(DexMethod method) {
+    return add(method.getSignature());
+  }
+
+  public boolean add(DexEncodedMethod method) {
+    return add(method.getReference());
+  }
+
+  public boolean add(DexClassAndMethod method) {
+    return add(method.getReference());
+  }
+
+  public void addAll(Iterable<DexMethodSignature> signatures) {
+    signatures.forEach(this::add);
+  }
+
+  public void addAllMethods(Iterable<DexEncodedMethod> methods) {
+    methods.forEach(this::add);
+  }
+
+  public void addAll(DexMethodSignatureSet signatures) {
+    addAll(signatures.backing);
+  }
+
+  public <T> void addAll(Iterable<T> elements, Function<T, Iterable<DexMethodSignature>> fn) {
+    for (T element : elements) {
+      addAll(fn.apply(element));
+    }
+  }
+
+  public boolean contains(DexMethodSignature signature) {
+    return backing.contains(signature);
+  }
+
+  @Override
+  public Iterator<DexMethodSignature> iterator() {
+    return backing.iterator();
+  }
+
+  public boolean remove(DexMethodSignature signature) {
+    return backing.remove(signature);
+  }
+
+  public boolean remove(DexEncodedMethod method) {
+    return remove(method.getSignature());
+  }
+
+  public void removeAll(Iterable<DexMethodSignature> signatures) {
+    signatures.forEach(this::remove);
+  }
+
+  public void removeAllMethods(Iterable<DexEncodedMethod> methods) {
+    methods.forEach(this::remove);
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/D8IncrementalRunExamplesAndroidOTest.java b/src/test/java/com/android/tools/r8/D8IncrementalRunExamplesAndroidOTest.java
index 84b6675..726136f 100644
--- a/src/test/java/com/android/tools/r8/D8IncrementalRunExamplesAndroidOTest.java
+++ b/src/test/java/com/android/tools/r8/D8IncrementalRunExamplesAndroidOTest.java
@@ -15,6 +15,7 @@
 import com.android.tools.r8.ir.desugar.InterfaceMethodRewriter;
 import com.android.tools.r8.ir.desugar.LambdaRewriter;
 import com.android.tools.r8.ir.desugar.TwrCloseResourceRewriter;
+import com.android.tools.r8.synthesis.SyntheticItems;
 import com.android.tools.r8.utils.AndroidApiLevel;
 import com.android.tools.r8.utils.AndroidApp;
 import com.android.tools.r8.utils.DescriptorUtils;
@@ -67,7 +68,7 @@
       List<String> classFiles = collectClassFiles(testJarFile);
       for (String classFile : classFiles) {
         AndroidApp app =
-            compileClassFiles(
+            compileClassFilesInIntermediate(
                 testJarFile, Collections.singletonList(classFile), null, OutputMode.DexIndexed);
         assert app.getDexProgramResourcesForTesting().size() == 1;
         fileToResource.put(
@@ -83,7 +84,8 @@
       TreeMap<String, ProgramResource> fileToResource = new TreeMap<>();
       List<String> classFiles = collectClassFiles(testJarFile);
       AndroidApp app =
-          compileClassFiles(testJarFile, classFiles, output, OutputMode.DexFilePerClassFile);
+          compileClassFilesInIntermediate(
+              testJarFile, classFiles, output, OutputMode.DexFilePerClassFile);
       for (ProgramResource resource : app.getDexProgramResourcesForTesting()) {
         Set<String> descriptors = resource.getClassDescriptors();
         String mainClassDescriptor = app.getPrimaryClassDescriptor(resource);
@@ -91,11 +93,13 @@
         for (String descriptor : descriptors) {
           // classes are either lambda classes used by the main class, companion classes of the main
           // interface, the main class/interface, or for JDK9, desugaring of try-with-resources.
-          Assert.assertTrue(descriptor.contains(LambdaRewriter.LAMBDA_CLASS_NAME_PREFIX)
-              || descriptor.endsWith(InterfaceMethodRewriter.COMPANION_CLASS_NAME_SUFFIX + ";")
-              || descriptor.endsWith(InterfaceMethodRewriter.DISPATCH_CLASS_NAME_SUFFIX + ";")
-              || descriptor.equals(TwrCloseResourceRewriter.UTILITY_CLASS_DESCRIPTOR)
-              || descriptor.equals(mainClassDescriptor));
+          Assert.assertTrue(
+              descriptor.contains(LambdaRewriter.LAMBDA_CLASS_NAME_PREFIX)
+                  || descriptor.endsWith(InterfaceMethodRewriter.COMPANION_CLASS_NAME_SUFFIX + ";")
+                  || descriptor.endsWith(InterfaceMethodRewriter.DISPATCH_CLASS_NAME_SUFFIX + ";")
+                  || descriptor.equals(TwrCloseResourceRewriter.UTILITY_CLASS_DESCRIPTOR)
+                  || descriptor.contains(SyntheticItems.EXTERNAL_SYNTHETIC_CLASS_SEPARATOR)
+                  || descriptor.equals(mainClassDescriptor));
         }
         String classDescriptor =
             DescriptorUtils.getClassBinaryNameFromDescriptor(mainClassDescriptor);
@@ -159,7 +163,7 @@
       }
     }
 
-    AndroidApp compileClassFiles(
+    AndroidApp compileClassFilesInIntermediate(
         Path testJarFile, List<String> inputFiles, Path outputPath, OutputMode outputMode)
         throws Throwable {
       D8Command.Builder builder = D8Command.builder();
@@ -179,6 +183,7 @@
       } else {
         throw new Unreachable("Unexpected output mode " + outputMode);
       }
+      builder.setIntermediate(true);
       addLibraryReference(builder, ToolHelper.getAndroidJar(
           androidJarVersion == null ? builder.getMinApiLevel() : androidJarVersion.getLevel()));
       try {
@@ -312,7 +317,6 @@
 
     // TODO(b/123504206): This test throws an index out of bounds exception.
     // Re-write or verify running fails in the expected way.
-
     Assert.assertArrayEquals(
         readResource(mergedFromCompiledSeparately.getDexProgramResourcesForTesting().get(0)),
         readResource(mergedFromCompiledTogether.getDexProgramResourcesForTesting().get(0)));
diff --git a/src/test/java/com/android/tools/r8/TestBase.java b/src/test/java/com/android/tools/r8/TestBase.java
index 1b417b3..a8b5af7 100644
--- a/src/test/java/com/android/tools/r8/TestBase.java
+++ b/src/test/java/com/android/tools/r8/TestBase.java
@@ -1682,6 +1682,13 @@
     return AndroidApiLevel.N;
   }
 
+  public static boolean hasDefaultInterfaceMethodsSupport(TestParameters parameters) {
+    return parameters.isCfRuntime()
+        || parameters
+            .getApiLevel()
+            .isGreaterThanOrEqualTo(apiLevelWithDefaultInterfaceMethodsSupport());
+  }
+
   public static AndroidApiLevel apiLevelWithStaticInterfaceMethodsSupport() {
     return AndroidApiLevel.N;
   }
diff --git a/src/test/java/com/android/tools/r8/accessrelaxation/PackagePrivateOverridePublicizerTest.java b/src/test/java/com/android/tools/r8/accessrelaxation/PackagePrivateOverridePublicizerTest.java
index ccd0b21..630ff62 100644
--- a/src/test/java/com/android/tools/r8/accessrelaxation/PackagePrivateOverridePublicizerTest.java
+++ b/src/test/java/com/android/tools/r8/accessrelaxation/PackagePrivateOverridePublicizerTest.java
@@ -50,6 +50,10 @@
         .enableInliningAnnotations()
         .enableNeverClassInliningAnnotations()
         .allowAccessModification()
+        .addOptionsModification(
+            options -> {
+              options.enablePackagePrivateAwarePublicization = true;
+            })
         .run(parameters.getRuntime(), Main.class)
         .apply(this::assertSuccessOutput);
   }
diff --git a/src/test/java/com/android/tools/r8/classmerging/horizontal/NoInterfacesTest.java b/src/test/java/com/android/tools/r8/classmerging/horizontal/ClassesWithDifferentInterfacesTest.java
similarity index 70%
copy from src/test/java/com/android/tools/r8/classmerging/horizontal/NoInterfacesTest.java
copy to src/test/java/com/android/tools/r8/classmerging/horizontal/ClassesWithDifferentInterfacesTest.java
index f286bfd..d1333a3 100644
--- a/src/test/java/com/android/tools/r8/classmerging/horizontal/NoInterfacesTest.java
+++ b/src/test/java/com/android/tools/r8/classmerging/horizontal/ClassesWithDifferentInterfacesTest.java
@@ -9,11 +9,14 @@
 
 import com.android.tools.r8.NeverClassInline;
 import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.NoVerticalClassMerging;
 import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.utils.codeinspector.HorizontallyMergedClassesInspector;
 import org.junit.Test;
 
-public class NoInterfacesTest extends HorizontalClassMergingTestBase {
-  public NoInterfacesTest(TestParameters parameters, boolean enableHorizontalClassMerging) {
+public class ClassesWithDifferentInterfacesTest extends HorizontalClassMergingTestBase {
+  public ClassesWithDifferentInterfacesTest(
+      TestParameters parameters, boolean enableHorizontalClassMerging) {
     super(parameters, enableHorizontalClassMerging);
   }
 
@@ -26,9 +29,12 @@
             options -> options.enableHorizontalClassMerging = enableHorizontalClassMerging)
         .enableInliningAnnotations()
         .enableNeverClassInliningAnnotations()
+        .enableNoVerticalClassMergingAnnotations()
         .setMinApi(parameters.getApiLevel())
+        .addHorizontallyMergedClassesInspector(
+            HorizontallyMergedClassesInspector::assertNoClassesMerged)
         .run(parameters.getRuntime(), Main.class)
-        .assertSuccessWithOutputLines("bar", "foo y", "foo z")
+        .assertSuccessWithOutputLines("bar", "foo y", "bar")
         .inspect(
             codeInspector -> {
               assertThat(codeInspector.clazz(I.class), isPresent());
@@ -38,20 +44,26 @@
             });
   }
 
+  @NoVerticalClassMerging
   public interface I {
     void foo();
   }
 
+  @NoVerticalClassMerging
+  public interface J {
+    void bar();
+  }
+
   @NeverClassInline
   public static class X {
     @NeverInline
-    public static void bar() {
+    public void bar() {
       System.out.println("bar");
     }
   }
 
   @NeverClassInline
-  public static class Y implements I {
+  public static class Y extends X implements I {
     @NeverInline
     @Override
     public void foo() {
@@ -60,9 +72,8 @@
   }
 
   @NeverClassInline
-  public static class Z implements I {
+  public static class Z extends X implements J {
     @NeverInline
-    @Override
     public void foo() {
       System.out.println("foo z");
     }
@@ -74,13 +85,18 @@
       i.foo();
     }
 
+    @NeverInline
+    public static void bar(J j) {
+      j.bar();
+    }
+
     public static void main(String[] args) {
       X x = new X();
       x.bar();
       Y y = new Y();
       Z z = new Z();
       foo(y);
-      foo(z);
+      bar(z);
     }
   }
 }
diff --git a/src/test/java/com/android/tools/r8/classmerging/horizontal/NoInterfacesTest.java b/src/test/java/com/android/tools/r8/classmerging/horizontal/ClassesWithIdenticalInterfacesTest.java
similarity index 79%
rename from src/test/java/com/android/tools/r8/classmerging/horizontal/NoInterfacesTest.java
rename to src/test/java/com/android/tools/r8/classmerging/horizontal/ClassesWithIdenticalInterfacesTest.java
index f286bfd..456d29e 100644
--- a/src/test/java/com/android/tools/r8/classmerging/horizontal/NoInterfacesTest.java
+++ b/src/test/java/com/android/tools/r8/classmerging/horizontal/ClassesWithIdenticalInterfacesTest.java
@@ -5,6 +5,7 @@
 package com.android.tools.r8.classmerging.horizontal;
 
 import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static com.android.tools.r8.utils.codeinspector.Matchers.notIf;
 import static org.hamcrest.MatcherAssert.assertThat;
 
 import com.android.tools.r8.NeverClassInline;
@@ -12,8 +13,9 @@
 import com.android.tools.r8.TestParameters;
 import org.junit.Test;
 
-public class NoInterfacesTest extends HorizontalClassMergingTestBase {
-  public NoInterfacesTest(TestParameters parameters, boolean enableHorizontalClassMerging) {
+public class ClassesWithIdenticalInterfacesTest extends HorizontalClassMergingTestBase {
+  public ClassesWithIdenticalInterfacesTest(
+      TestParameters parameters, boolean enableHorizontalClassMerging) {
     super(parameters, enableHorizontalClassMerging);
   }
 
@@ -27,6 +29,8 @@
         .enableInliningAnnotations()
         .enableNeverClassInliningAnnotations()
         .setMinApi(parameters.getApiLevel())
+        .addHorizontallyMergedClassesInspector(
+            inspector -> inspector.assertMergedInto(Z.class, Y.class))
         .run(parameters.getRuntime(), Main.class)
         .assertSuccessWithOutputLines("bar", "foo y", "foo z")
         .inspect(
@@ -34,7 +38,8 @@
               assertThat(codeInspector.clazz(I.class), isPresent());
               assertThat(codeInspector.clazz(X.class), isPresent());
               assertThat(codeInspector.clazz(Y.class), isPresent());
-              assertThat(codeInspector.clazz(Z.class), isPresent());
+              assertThat(
+                  codeInspector.clazz(Z.class), notIf(isPresent(), enableHorizontalClassMerging));
             });
   }
 
@@ -45,7 +50,7 @@
   @NeverClassInline
   public static class X {
     @NeverInline
-    public static void bar() {
+    public void bar() {
       System.out.println("bar");
     }
   }
diff --git a/src/test/java/com/android/tools/r8/classmerging/horizontal/InheritInterfaceWithDefaultTest.java b/src/test/java/com/android/tools/r8/classmerging/horizontal/InheritInterfaceWithDefaultTest.java
new file mode 100644
index 0000000..9bdaca6
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/classmerging/horizontal/InheritInterfaceWithDefaultTest.java
@@ -0,0 +1,77 @@
+// Copyright (c) 2020, 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.classmerging.horizontal;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static com.android.tools.r8.utils.codeinspector.Matchers.notIf;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import com.android.tools.r8.NeverClassInline;
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.classmerging.horizontal.EmptyClassTest.A;
+import com.android.tools.r8.classmerging.horizontal.EmptyClassTest.B;
+import com.android.tools.r8.classmerging.horizontal.EmptyClassTest.Main;
+import org.junit.Test;
+
+public class InheritInterfaceWithDefaultTest extends HorizontalClassMergingTestBase {
+
+  public InheritInterfaceWithDefaultTest(
+      TestParameters parameters, boolean enableHorizontalClassMerging) {
+    super(parameters, enableHorizontalClassMerging);
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(getClass())
+        .addKeepMainRule(Main.class)
+        .allowStdoutMessages()
+        .addOptionsModification(
+            options -> options.enableHorizontalClassMerging = enableHorizontalClassMerging)
+        .enableInliningAnnotations()
+        .enableNeverClassInliningAnnotations()
+        .setMinApi(parameters.getApiLevel())
+        .addHorizontallyMergedClassesInspectorIf(
+            enableHorizontalClassMerging, inspector -> inspector.assertMergedInto(B.class, A.class))
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines(
+            "print interface", "print interface", "print interface", "print interface")
+        .inspect(
+            codeInspector -> {
+              assertThat(codeInspector.clazz(A.class), isPresent());
+              assertThat(
+                  codeInspector.clazz(B.class), notIf(isPresent(), enableHorizontalClassMerging));
+            });
+  }
+
+  public interface Interface {
+    @NeverInline
+    default void print() {
+      System.out.println("print interface");
+    }
+  }
+
+  @NeverClassInline
+  public static class A implements Interface {}
+
+  @NeverClassInline
+  public static class B implements Interface {}
+
+  public static class Main {
+
+    @NeverInline
+    public static void print(Interface i) {
+      i.print();
+    }
+
+    public static void main(String[] args) {
+      new A().print();
+      new B().print();
+      print(new A());
+      print(new B());
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/classmerging/horizontal/InheritOverrideInterfaceTest.java b/src/test/java/com/android/tools/r8/classmerging/horizontal/InheritOverrideInterfaceTest.java
new file mode 100644
index 0000000..cedee87
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/classmerging/horizontal/InheritOverrideInterfaceTest.java
@@ -0,0 +1,83 @@
+// Copyright (c) 2020, 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.classmerging.horizontal;
+
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.NoVerticalClassMerging;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.classmerging.horizontal.EmptyClassTest.A;
+import com.android.tools.r8.classmerging.horizontal.EmptyClassTest.B;
+import com.android.tools.r8.classmerging.horizontal.EmptyClassTest.Main;
+import org.junit.Test;
+
+public class InheritOverrideInterfaceTest extends HorizontalClassMergingTestBase {
+  public InheritOverrideInterfaceTest(
+      TestParameters parameters, boolean enableHorizontalClassMerging) {
+    super(parameters, enableHorizontalClassMerging);
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(getClass())
+        .addKeepMainRule(Main.class)
+        .addOptionsModification(
+            options -> options.enableHorizontalClassMerging = enableHorizontalClassMerging)
+        .enableInliningAnnotations()
+        .enableNoVerticalClassMergingAnnotations()
+        .setMinApi(parameters.getApiLevel())
+        .addHorizontallyMergedClassesInspectorIf(
+            enableHorizontalClassMerging, inspector -> inspector.assertMergedInto(B.class, A.class))
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines("A", "B", "A")
+        .inspect(codeInspector -> {});
+  }
+
+  @NoVerticalClassMerging
+  interface I {
+    @NeverInline
+    default void m() {
+      System.out.println("I");
+    }
+  }
+
+  public static class A implements I {
+    @NeverInline
+    @Override
+    public void m() {
+      System.out.println("A");
+    }
+  }
+
+  public static class B implements I {
+    @NeverInline
+    @Override
+    public void m() {
+      System.out.println("B");
+    }
+  }
+
+  @NoVerticalClassMerging
+  interface J extends I {
+    default void m() {
+      System.out.println("J");
+    }
+  }
+
+  public static class C extends A implements J {}
+
+  public static class Main {
+    @NeverInline
+    public static void doI(I i) {
+      i.m();
+    }
+
+    public static void main(String[] args) {
+      doI(new A());
+      doI(new B());
+      doI(new C());
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/classmerging/horizontal/MergedSuperMethodIsDefaultMethodTest.java b/src/test/java/com/android/tools/r8/classmerging/horizontal/MergedSuperMethodIsDefaultMethodTest.java
deleted file mode 100644
index 483e702..0000000
--- a/src/test/java/com/android/tools/r8/classmerging/horizontal/MergedSuperMethodIsDefaultMethodTest.java
+++ /dev/null
@@ -1,84 +0,0 @@
-// Copyright (c) 2020, 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.classmerging.horizontal;
-
-import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
-import static com.android.tools.r8.utils.codeinspector.Matchers.notIf;
-import static org.hamcrest.MatcherAssert.assertThat;
-
-import com.android.tools.r8.CompilationFailedException;
-import com.android.tools.r8.NeverClassInline;
-import com.android.tools.r8.NeverInline;
-import com.android.tools.r8.NoVerticalClassMerging;
-import com.android.tools.r8.TestParameters;
-import java.io.IOException;
-import java.util.concurrent.ExecutionException;
-import org.junit.Test;
-
-public class MergedSuperMethodIsDefaultMethodTest extends HorizontalClassMergingTestBase {
-  public MergedSuperMethodIsDefaultMethodTest(
-      TestParameters parameters, boolean enableHorizontalClassMerging) {
-    super(parameters, enableHorizontalClassMerging);
-  }
-
-  @Test
-  public void testR8() throws IOException, CompilationFailedException, ExecutionException {
-    testForR8(parameters.getBackend())
-        .addInnerClasses(this.getClass())
-        .addOptionsModification(
-            options -> options.enableHorizontalClassMerging = enableHorizontalClassMerging)
-        .enableNoVerticalClassMergingAnnotations()
-        .enableNeverClassInliningAnnotations()
-        .enableInliningAnnotations()
-        .addKeepMainRule(Main.class)
-        .setMinApi(parameters.getApiLevel())
-        .run(parameters.getRuntime(), Main.class)
-        .assertSuccessWithOutputLines("I.foo")
-        .inspect(
-            codeInspector -> {
-              assertThat(codeInspector.clazz(I.class), isPresent());
-              assertThat(codeInspector.clazz(A.class), isPresent());
-              assertThat(codeInspector.clazz(B.class), isPresent());
-              assertThat(
-                  codeInspector.clazz(C.class), notIf(isPresent(), enableHorizontalClassMerging));
-            });
-  }
-
-  @NoVerticalClassMerging
-  public interface I {
-    @NeverInline
-    default void foo() {
-      System.out.println("I.foo");
-    }
-  }
-
-  @NoVerticalClassMerging
-  public abstract static class A implements I {}
-
-  @NeverClassInline
-  public static class B extends A {
-
-    @Override
-    @NeverInline
-    public void foo() {
-      System.out.println("B.foo");
-    }
-  }
-
-  @NeverClassInline
-  public static class C extends A {}
-
-  public static class Main {
-
-    public static void main(String[] args) {
-      callA(args.length == 0 ? new C() : new B());
-    }
-
-    @NeverInline
-    private static void callA(A a) {
-      a.foo();
-    }
-  }
-}
diff --git a/src/test/java/com/android/tools/r8/classmerging/horizontal/PrivateAndInterfaceMethodCollisionTest.java b/src/test/java/com/android/tools/r8/classmerging/horizontal/PrivateAndInterfaceMethodCollisionTest.java
index 3b957c4..af37199 100644
--- a/src/test/java/com/android/tools/r8/classmerging/horizontal/PrivateAndInterfaceMethodCollisionTest.java
+++ b/src/test/java/com/android/tools/r8/classmerging/horizontal/PrivateAndInterfaceMethodCollisionTest.java
@@ -9,7 +9,7 @@
 import com.android.tools.r8.NoUnusedInterfaceRemoval;
 import com.android.tools.r8.NoVerticalClassMerging;
 import com.android.tools.r8.TestParameters;
-import com.android.tools.r8.TestRuntime.CfVm;
+import com.android.tools.r8.utils.codeinspector.HorizontallyMergedClassesInspector;
 import org.junit.Test;
 
 public class PrivateAndInterfaceMethodCollisionTest extends HorizontalClassMergingTestBase {
@@ -21,18 +21,13 @@
 
   @Test
   public void test() throws Exception {
-    // TODO(b/167981556): Should always succeed.
-    boolean expectedToSucceed =
-        !enableHorizontalClassMerging
-            || parameters.isCfRuntime(CfVm.JDK11)
-            || parameters.isDexRuntime();
     testForR8(parameters.getBackend())
         .addInnerClasses(getClass())
         .addKeepMainRule(Main.class)
         .addOptionsModification(
             options -> options.enableHorizontalClassMerging = enableHorizontalClassMerging)
-        .addHorizontallyMergedClassesInspectorIf(
-            enableHorizontalClassMerging, inspector -> inspector.assertMergedInto(B.class, A.class))
+        .addHorizontallyMergedClassesInspector(
+            HorizontallyMergedClassesInspector::assertNoClassesMerged)
         .enableInliningAnnotations()
         .enableNeverClassInliningAnnotations()
         .enableNoUnusedInterfaceRemovalAnnotations()
@@ -40,8 +35,7 @@
         .setMinApi(parameters.getApiLevel())
         .compile()
         .run(parameters.getRuntime(), Main.class)
-        .assertSuccessWithOutputLinesIf(expectedToSucceed, "A.foo()", "B.bar()", "J.foo()")
-        .assertFailureWithErrorThatThrowsIf(!expectedToSucceed, IllegalAccessError.class);
+        .assertSuccessWithOutputLines("A.foo()", "B.bar()", "J.foo()");
   }
 
   static class Main {
diff --git a/src/test/java/com/android/tools/r8/classmerging/horizontal/StaticAndInterfaceMethodCollisionTest.java b/src/test/java/com/android/tools/r8/classmerging/horizontal/StaticAndInterfaceMethodCollisionTest.java
index 356acd7..ebbfd86 100644
--- a/src/test/java/com/android/tools/r8/classmerging/horizontal/StaticAndInterfaceMethodCollisionTest.java
+++ b/src/test/java/com/android/tools/r8/classmerging/horizontal/StaticAndInterfaceMethodCollisionTest.java
@@ -9,6 +9,7 @@
 import com.android.tools.r8.NoUnusedInterfaceRemoval;
 import com.android.tools.r8.NoVerticalClassMerging;
 import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.utils.codeinspector.HorizontallyMergedClassesInspector;
 import org.junit.Test;
 
 public class StaticAndInterfaceMethodCollisionTest extends HorizontalClassMergingTestBase {
@@ -25,8 +26,8 @@
         .addKeepMainRule(Main.class)
         .addOptionsModification(
             options -> options.enableHorizontalClassMerging = enableHorizontalClassMerging)
-        .addHorizontallyMergedClassesInspectorIf(
-            enableHorizontalClassMerging, inspector -> inspector.assertMergedInto(B.class, A.class))
+        .addHorizontallyMergedClassesInspector(
+            HorizontallyMergedClassesInspector::assertNoClassesMerged)
         .enableInliningAnnotations()
         .enableNeverClassInliningAnnotations()
         .enableNoUnusedInterfaceRemovalAnnotations()
diff --git a/src/test/java/com/android/tools/r8/classmerging/horizontal/StaticAndVirtualMethodCollisionTest.java b/src/test/java/com/android/tools/r8/classmerging/horizontal/StaticAndVirtualMethodCollisionTest.java
index 52b506f..edca180 100644
--- a/src/test/java/com/android/tools/r8/classmerging/horizontal/StaticAndVirtualMethodCollisionTest.java
+++ b/src/test/java/com/android/tools/r8/classmerging/horizontal/StaticAndVirtualMethodCollisionTest.java
@@ -4,9 +4,6 @@
 
 package com.android.tools.r8.classmerging.horizontal;
 
-import static com.android.tools.r8.utils.codeinspector.AssertUtils.assertFailsCompilationIf;
-import static org.hamcrest.CoreMatchers.containsString;
-import static org.hamcrest.MatcherAssert.assertThat;
 
 import com.android.tools.r8.NeverClassInline;
 import com.android.tools.r8.NeverInline;
@@ -22,24 +19,18 @@
 
   @Test
   public void test() throws Exception {
-    // TODO(b/172415620): Handle static/virtual method collisions.
-    assertFailsCompilationIf(
-        enableHorizontalClassMerging,
-        () ->
-            testForR8(parameters.getBackend())
-                .addInnerClasses(getClass())
-                .addKeepMainRule(Main.class)
-                .addOptionsModification(
-                    options -> options.enableHorizontalClassMerging = enableHorizontalClassMerging)
-                .addHorizontallyMergedClassesInspectorIf(
-                    enableHorizontalClassMerging,
-                    inspector -> inspector.assertMergedInto(B.class, A.class))
-                .enableInliningAnnotations()
-                .enableNeverClassInliningAnnotations()
-                .setMinApi(parameters.getApiLevel())
-                .run(parameters.getRuntime(), Main.class)
-                .assertSuccessWithOutputLines("A.foo()", "A.bar()", "B.foo()", "B.bar()"),
-        e -> assertThat(e.getCause().getMessage(), containsString("Duplicate method")));
+    testForR8(parameters.getBackend())
+        .addInnerClasses(getClass())
+        .addKeepMainRule(Main.class)
+        .addOptionsModification(
+            options -> options.enableHorizontalClassMerging = enableHorizontalClassMerging)
+        .addHorizontallyMergedClassesInspectorIf(
+            enableHorizontalClassMerging, inspector -> inspector.assertMergedInto(B.class, A.class))
+        .enableInliningAnnotations()
+        .enableNeverClassInliningAnnotations()
+        .setMinApi(parameters.getApiLevel())
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines("A.foo()", "A.bar()", "B.foo()", "B.bar()");
   }
 
   static class Main {
diff --git a/src/test/java/com/android/tools/r8/classmerging/horizontal/TreeFixerSubClassCollisionTest.java b/src/test/java/com/android/tools/r8/classmerging/horizontal/TreeFixerSubClassCollisionTest.java
index e5c6561..aad0efa 100644
--- a/src/test/java/com/android/tools/r8/classmerging/horizontal/TreeFixerSubClassCollisionTest.java
+++ b/src/test/java/com/android/tools/r8/classmerging/horizontal/TreeFixerSubClassCollisionTest.java
@@ -36,7 +36,8 @@
         .enableNoHorizontalClassMergingAnnotations()
         .setMinApi(parameters.getApiLevel())
         .run(parameters.getRuntime(), Main.class)
-        .assertSuccessWithOutputLines("print a: foo c a", "print b: foo c b", "print b: foo d b")
+        .assertSuccessWithOutputLines(
+            "print a: foo c a", "print b: foo c b", "print b: foo c b", "print b: foo d b")
         .inspect(
             codeInspector -> {
               assertThat(codeInspector.clazz(A.class), isPresent());
@@ -45,15 +46,19 @@
 
               ClassSubject cClassSubject = codeInspector.clazz(C.class);
               assertThat(cClassSubject, isPresent());
-              // C#foo(B) is renamed to C#foo$2(A) to not collide with D#foo$1(A).
+              // C#foo(B) is renamed to C#foo$1(A).
               if (enableHorizontalClassMerging) {
                 assertThat(cClassSubject.uniqueMethodWithFinalName("foo"), isPresent());
-                assertThat(cClassSubject.uniqueMethodWithFinalName("foo$2"), isPresent());
+                assertThat(cClassSubject.uniqueMethodWithFinalName("foo$1"), isPresent());
               }
 
               ClassSubject dClassSubject = codeInspector.clazz(D.class);
               assertThat(dClassSubject, isPresent());
-              assertThat(dClassSubject.uniqueMethodWithFinalName("foo$1"), isPresent());
+              // D#foo$1(B) is renamed to D#foo$2(A).
+              assertThat(
+                  dClassSubject.uniqueMethodWithFinalName(
+                      enableHorizontalClassMerging ? "foo$1$1" : "foo$1"),
+                  isPresent());
             });
   }
 
@@ -104,6 +109,7 @@
       c.foo(a);
       c.foo(b);
       D d = new D();
+      d.foo(b);
       d.foo$1(b);
     }
   }
diff --git a/src/test/java/com/android/tools/r8/classmerging/horizontal/VirtualMethodMergingOfPublicizedMethodsTest.java b/src/test/java/com/android/tools/r8/classmerging/horizontal/VirtualMethodMergingOfPublicizedMethodsTest.java
index 5df1264..8178138 100644
--- a/src/test/java/com/android/tools/r8/classmerging/horizontal/VirtualMethodMergingOfPublicizedMethodsTest.java
+++ b/src/test/java/com/android/tools/r8/classmerging/horizontal/VirtualMethodMergingOfPublicizedMethodsTest.java
@@ -4,7 +4,6 @@
 
 package com.android.tools.r8.classmerging.horizontal;
 
-import com.android.tools.r8.CompilationFailedException;
 import com.android.tools.r8.NeverClassInline;
 import com.android.tools.r8.NeverInline;
 import com.android.tools.r8.TestParameters;
diff --git a/src/test/java/com/android/tools/r8/classmerging/horizontal/VirtualMethodNotOverlappingTest.java b/src/test/java/com/android/tools/r8/classmerging/horizontal/dispatch/NotOverlappingTest.java
similarity index 86%
rename from src/test/java/com/android/tools/r8/classmerging/horizontal/VirtualMethodNotOverlappingTest.java
rename to src/test/java/com/android/tools/r8/classmerging/horizontal/dispatch/NotOverlappingTest.java
index c80c1ef..8742e67 100644
--- a/src/test/java/com/android/tools/r8/classmerging/horizontal/VirtualMethodNotOverlappingTest.java
+++ b/src/test/java/com/android/tools/r8/classmerging/horizontal/dispatch/NotOverlappingTest.java
@@ -2,18 +2,18 @@
 // 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.classmerging.horizontal;
+package com.android.tools.r8.classmerging.horizontal.dispatch;
 
 import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
 import static org.hamcrest.MatcherAssert.assertThat;
 import static org.hamcrest.core.IsNot.not;
 
 import com.android.tools.r8.*;
+import com.android.tools.r8.classmerging.horizontal.HorizontalClassMergingTestBase;
 import org.junit.Test;
 
-public class VirtualMethodNotOverlappingTest extends HorizontalClassMergingTestBase {
-  public VirtualMethodNotOverlappingTest(
-      TestParameters parameters, boolean enableHorizontalClassMerging) {
+public class NotOverlappingTest extends HorizontalClassMergingTestBase {
+  public NotOverlappingTest(TestParameters parameters, boolean enableHorizontalClassMerging) {
     super(parameters, enableHorizontalClassMerging);
   }
 
diff --git a/src/test/java/com/android/tools/r8/classmerging/horizontal/dispatch/OverrideAbstractMethodWithDefaultTest.java b/src/test/java/com/android/tools/r8/classmerging/horizontal/dispatch/OverrideAbstractMethodWithDefaultTest.java
new file mode 100644
index 0000000..87f4dc3
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/classmerging/horizontal/dispatch/OverrideAbstractMethodWithDefaultTest.java
@@ -0,0 +1,89 @@
+// Copyright (c) 2020, 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.classmerging.horizontal.dispatch;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.NoVerticalClassMerging;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.classmerging.horizontal.HorizontalClassMergingTestBase;
+import org.junit.Test;
+
+public class OverrideAbstractMethodWithDefaultTest extends HorizontalClassMergingTestBase {
+  public OverrideAbstractMethodWithDefaultTest(
+      TestParameters parameters, boolean enableHorizontalClassMerging) {
+    super(parameters, enableHorizontalClassMerging);
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(getClass())
+        .addKeepMainRule(Main.class)
+        .addOptionsModification(
+            options -> options.enableHorizontalClassMerging = enableHorizontalClassMerging)
+        .enableInliningAnnotations()
+        .enableNoVerticalClassMergingAnnotations()
+        .setMinApi(parameters.getApiLevel())
+        .addHorizontallyMergedClassesInspectorIf(
+            enableHorizontalClassMerging, inspector -> inspector.assertNoClassesMerged())
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines("J", "B2")
+        .inspect(
+            codeInspector -> {
+              assertThat(codeInspector.clazz(I.class), isPresent());
+              assertThat(codeInspector.clazz(J.class), isPresent());
+              assertThat(codeInspector.clazz(A.class), isPresent());
+              assertThat(codeInspector.clazz(B1.class), isPresent());
+              assertThat(codeInspector.clazz(B2.class), isPresent());
+              assertThat(codeInspector.clazz(C1.class), isPresent());
+              assertThat(codeInspector.clazz(C2.class), isPresent());
+            });
+  }
+
+  @NoVerticalClassMerging
+  interface I {
+    void m();
+  }
+
+  @NoVerticalClassMerging
+  interface J extends I {
+    default void m() {
+      System.out.println("J");
+    }
+  }
+
+  abstract static class A implements I {}
+
+  @NoVerticalClassMerging
+  abstract static class B1 extends A {}
+
+  @NoVerticalClassMerging
+  abstract static class B2 extends A {
+    @Override
+    @NeverInline
+    public void m() {
+      System.out.println("B2");
+    }
+  }
+
+  static class C1 extends B1 implements J {}
+
+  static class C2 extends B2 {}
+
+  static class Main {
+    @NeverInline
+    public static void doI(I i) {
+      i.m();
+    }
+
+    public static void main(String[] args) {
+      doI(new C1());
+      doI(new C2());
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/classmerging/horizontal/dispatch/OverrideDefaultMethodTest.java b/src/test/java/com/android/tools/r8/classmerging/horizontal/dispatch/OverrideDefaultMethodTest.java
new file mode 100644
index 0000000..dd8183d
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/classmerging/horizontal/dispatch/OverrideDefaultMethodTest.java
@@ -0,0 +1,85 @@
+// Copyright (c) 2020, 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.classmerging.horizontal.dispatch;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.NoVerticalClassMerging;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.classmerging.horizontal.HorizontalClassMergingTestBase;
+import com.android.tools.r8.utils.codeinspector.HorizontallyMergedClassesInspector;
+import org.junit.Test;
+
+public class OverrideDefaultMethodTest extends HorizontalClassMergingTestBase {
+  public OverrideDefaultMethodTest(
+      TestParameters parameters, boolean enableHorizontalClassMerging) {
+    super(parameters, enableHorizontalClassMerging);
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(getClass())
+        .addKeepMainRule(Main.class)
+        .addOptionsModification(
+            options -> options.enableHorizontalClassMerging = enableHorizontalClassMerging)
+        .enableInliningAnnotations()
+        .enableNoVerticalClassMergingAnnotations()
+        .setMinApi(parameters.getApiLevel())
+        .addHorizontallyMergedClassesInspectorIf(
+            enableHorizontalClassMerging, HorizontallyMergedClassesInspector::assertNoClassesMerged)
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines("I", "B", "J")
+        .inspect(
+            codeInspector -> {
+              assertThat(codeInspector.clazz(I.class), isPresent());
+              assertThat(codeInspector.clazz(J.class), isPresent());
+              assertThat(codeInspector.clazz(A.class), isPresent());
+              assertThat(codeInspector.clazz(B.class), isPresent());
+              assertThat(codeInspector.clazz(C.class), isPresent());
+            });
+  }
+
+  interface I {
+    @NeverInline
+    default void m() {
+      System.out.println("I");
+    }
+  }
+
+  public static class A implements I {}
+
+  public static class B implements I {
+    @NeverInline
+    @Override
+    public void m() {
+      System.out.println("B");
+    }
+  }
+
+  @NoVerticalClassMerging
+  interface J extends I {
+    default void m() {
+      System.out.println("J");
+    }
+  }
+
+  public static class C extends A implements J {}
+
+  public static class Main {
+    @NeverInline
+    public static void doI(I i) {
+      i.m();
+    }
+
+    public static void main(String[] args) {
+      doI(new A());
+      doI(new B());
+      doI(new C());
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/classmerging/horizontal/dispatch/OverrideDefaultOnSuperMethodTest.java b/src/test/java/com/android/tools/r8/classmerging/horizontal/dispatch/OverrideDefaultOnSuperMethodTest.java
new file mode 100644
index 0000000..bd41f8f
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/classmerging/horizontal/dispatch/OverrideDefaultOnSuperMethodTest.java
@@ -0,0 +1,92 @@
+// Copyright (c) 2020, 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.classmerging.horizontal.dispatch;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.NoUnusedInterfaceRemoval;
+import com.android.tools.r8.NoVerticalClassMerging;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.classmerging.horizontal.HorizontalClassMergingTestBase;
+import com.android.tools.r8.utils.codeinspector.HorizontallyMergedClassesInspector;
+import org.junit.Test;
+
+public class OverrideDefaultOnSuperMethodTest extends HorizontalClassMergingTestBase {
+  public OverrideDefaultOnSuperMethodTest(
+      TestParameters parameters, boolean enableHorizontalClassMerging) {
+    super(parameters, enableHorizontalClassMerging);
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(getClass())
+        .addKeepMainRule(Main.class)
+        .addOptionsModification(
+            options -> options.enableHorizontalClassMerging = enableHorizontalClassMerging)
+        .enableInliningAnnotations()
+        .enableNoUnusedInterfaceRemovalAnnotations()
+        .enableNoVerticalClassMergingAnnotations()
+        .setMinApi(parameters.getApiLevel())
+        .addHorizontallyMergedClassesInspectorIf(
+            enableHorizontalClassMerging, HorizontallyMergedClassesInspector::assertNoClassesMerged)
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines("I", "B", "J")
+        .inspect(
+            codeInspector -> {
+              assertThat(codeInspector.clazz(I.class), isPresent());
+              assertThat(codeInspector.clazz(J.class), isPresent());
+              assertThat(codeInspector.clazz(Parent.class), isPresent());
+              assertThat(codeInspector.clazz(A.class), isPresent());
+              assertThat(codeInspector.clazz(B.class), isPresent());
+              assertThat(codeInspector.clazz(C.class), isPresent());
+            });
+  }
+
+  @NoVerticalClassMerging
+  interface I {
+    @NeverInline
+    default void m() {
+      System.out.println("I");
+    }
+  }
+
+  public static class Parent implements I {}
+
+  public static class A extends Parent {}
+
+  public static class B extends Parent {
+    @NeverInline
+    @Override
+    public void m() {
+      System.out.println("B");
+    }
+  }
+
+  @NoUnusedInterfaceRemoval
+  @NoVerticalClassMerging
+  interface J extends I {
+    default void m() {
+      System.out.println("J");
+    }
+  }
+
+  public static class C extends A implements J {}
+
+  public static class Main {
+    @NeverInline
+    public static void doI(I i) {
+      i.m();
+    }
+
+    public static void main(String[] args) {
+      doI(new A());
+      doI(new B());
+      doI(new C());
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/classmerging/horizontal/dispatch/OverrideMergeAbsentTest.java b/src/test/java/com/android/tools/r8/classmerging/horizontal/dispatch/OverrideMergeAbsentTest.java
new file mode 100644
index 0000000..fe0bc23
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/classmerging/horizontal/dispatch/OverrideMergeAbsentTest.java
@@ -0,0 +1,84 @@
+// Copyright (c) 2020, 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.classmerging.horizontal.dispatch;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import com.android.tools.r8.NeverClassInline;
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.NoVerticalClassMerging;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.classmerging.horizontal.HorizontalClassMergingTestBase;
+import org.junit.Test;
+
+public class OverrideMergeAbsentTest extends HorizontalClassMergingTestBase {
+  public OverrideMergeAbsentTest(TestParameters parameters, boolean enableHorizontalClassMerging) {
+    super(parameters, enableHorizontalClassMerging);
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(getClass())
+        .addKeepMainRule(Main.class)
+        .addOptionsModification(
+            options -> options.enableHorizontalClassMerging = enableHorizontalClassMerging)
+        .enableInliningAnnotations()
+        .enableNeverClassInliningAnnotations()
+        .enableNoVerticalClassMergingAnnotations()
+        .setMinApi(parameters.getApiLevel())
+        .addHorizontallyMergedClassesInspectorIf(
+            enableHorizontalClassMerging, inspector -> inspector.assertNoClassesMerged())
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines("A", "B", "A", "J")
+        .inspect(
+            codeInspector -> {
+              assertThat(codeInspector.clazz(J.class), isPresent());
+              assertThat(codeInspector.clazz(A.class), isPresent());
+              assertThat(codeInspector.clazz(B.class), isPresent());
+              assertThat(codeInspector.clazz(C.class), isPresent());
+            });
+  }
+
+  @NeverClassInline
+  public static class A {
+    public A() {
+      System.out.println("A");
+    }
+  }
+
+  @NeverClassInline
+  public static class B {
+    @NeverInline
+    public void m() {
+      System.out.println("B");
+    }
+  }
+
+  @NoVerticalClassMerging
+  interface J {
+    @NeverInline
+    default void m() {
+      System.out.println("J");
+    }
+  }
+
+  @NeverClassInline
+  public static class C extends A implements J {}
+
+  public static class Main {
+    @NeverInline
+    public static void doI(J i) {
+      i.m();
+    }
+
+    public static void main(String[] args) {
+      new A();
+      new B().m();
+      doI(new C());
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/classmerging/horizontal/VirtualMethodOverrideParentCollisionTest.java b/src/test/java/com/android/tools/r8/classmerging/horizontal/dispatch/OverrideParentCollisionTest.java
similarity index 92%
rename from src/test/java/com/android/tools/r8/classmerging/horizontal/VirtualMethodOverrideParentCollisionTest.java
rename to src/test/java/com/android/tools/r8/classmerging/horizontal/dispatch/OverrideParentCollisionTest.java
index e304a70..94b643a 100644
--- a/src/test/java/com/android/tools/r8/classmerging/horizontal/VirtualMethodOverrideParentCollisionTest.java
+++ b/src/test/java/com/android/tools/r8/classmerging/horizontal/dispatch/OverrideParentCollisionTest.java
@@ -2,7 +2,7 @@
 // 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.horizontalclassmerging;
+package com.android.tools.r8.classmerging.horizontal.dispatch;
 
 import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
 import static org.hamcrest.MatcherAssert.assertThat;
@@ -14,9 +14,9 @@
 import com.android.tools.r8.classmerging.horizontal.HorizontalClassMergingTestBase;
 import org.junit.Test;
 
-public class VirtualMethodOverrideParentCollisionTest extends HorizontalClassMergingTestBase {
+public class OverrideParentCollisionTest extends HorizontalClassMergingTestBase {
 
-  public VirtualMethodOverrideParentCollisionTest(
+  public OverrideParentCollisionTest(
       TestParameters parameters, boolean enableHorizontalClassMerging) {
     super(parameters, enableHorizontalClassMerging);
   }
diff --git a/src/test/java/com/android/tools/r8/classmerging/horizontal/VirtualMethodSuperMergedTest.java b/src/test/java/com/android/tools/r8/classmerging/horizontal/dispatch/SuperMethodMergedTest.java
similarity index 89%
rename from src/test/java/com/android/tools/r8/classmerging/horizontal/VirtualMethodSuperMergedTest.java
rename to src/test/java/com/android/tools/r8/classmerging/horizontal/dispatch/SuperMethodMergedTest.java
index 3d29697..228223f 100644
--- a/src/test/java/com/android/tools/r8/classmerging/horizontal/VirtualMethodSuperMergedTest.java
+++ b/src/test/java/com/android/tools/r8/classmerging/horizontal/dispatch/SuperMethodMergedTest.java
@@ -2,7 +2,7 @@
 // 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.classmerging.horizontal;
+package com.android.tools.r8.classmerging.horizontal.dispatch;
 
 import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
 import static org.hamcrest.MatcherAssert.assertThat;
@@ -12,11 +12,11 @@
 import com.android.tools.r8.NeverInline;
 import com.android.tools.r8.NoVerticalClassMerging;
 import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.classmerging.horizontal.HorizontalClassMergingTestBase;
 import org.junit.Test;
 
-public class VirtualMethodSuperMergedTest extends HorizontalClassMergingTestBase {
-  public VirtualMethodSuperMergedTest(
-      TestParameters parameters, boolean enableHorizontalClassMerging) {
+public class SuperMethodMergedTest extends HorizontalClassMergingTestBase {
+  public SuperMethodMergedTest(TestParameters parameters, boolean enableHorizontalClassMerging) {
     super(parameters, enableHorizontalClassMerging);
   }
 
diff --git a/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/DesugaredLibraryTestBase.java b/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/DesugaredLibraryTestBase.java
index c7465ca..5856c44 100644
--- a/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/DesugaredLibraryTestBase.java
+++ b/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/DesugaredLibraryTestBase.java
@@ -24,15 +24,20 @@
 import com.android.tools.r8.ir.desugar.DesugaredLibraryConfiguration;
 import com.android.tools.r8.ir.desugar.DesugaredLibraryConfigurationParser;
 import com.android.tools.r8.origin.Origin;
+import com.android.tools.r8.tracereferences.TraceReferences;
 import com.android.tools.r8.utils.AndroidApiLevel;
+import com.android.tools.r8.utils.FileUtils;
 import com.android.tools.r8.utils.InternalOptions;
+import com.google.common.base.Charsets;
 import com.google.common.collect.ImmutableList;
 import java.io.IOException;
 import java.nio.file.Files;
 import java.nio.file.Path;
 import java.util.ArrayList;
 import java.util.Arrays;
+import java.util.HashMap;
 import java.util.List;
+import java.util.Map;
 import java.util.function.Consumer;
 
 public class DesugaredLibraryTestBase extends TestBase {
@@ -208,6 +213,50 @@
             builder -> builder.setSupportAllCallbacksFromLibrary(supportAllCallbacksFromLibrary));
   }
 
+  private Map<AndroidApiLevel, Path> desugaredLibraryClassFileCache = new HashMap<>();
+
+  // Build the desugared library in class file format.
+  public Path buildDesugaredLibraryClassFile(AndroidApiLevel apiLevel) throws Exception {
+    Path desugaredLib = desugaredLibraryClassFileCache.get(apiLevel);
+    if (desugaredLib != null) {
+      return desugaredLib;
+    }
+    desugaredLib = temp.newFolder().toPath().resolve("desugar_jdk_libs.jar");
+    L8Command.Builder l8Builder =
+        L8Command.builder()
+            .addLibraryFiles(ToolHelper.getAndroidJar(AndroidApiLevel.P))
+            .addProgramFiles(ToolHelper.getDesugarJDKLibs())
+            .addProgramFiles(ToolHelper.DESUGAR_LIB_CONVERSIONS)
+            .setMode(CompilationMode.DEBUG)
+            .addDesugaredLibraryConfiguration(
+                StringResource.fromFile(ToolHelper.DESUGAR_LIB_JSON_FOR_TESTING))
+            .setMinApiLevel(apiLevel.getLevel())
+            .setOutput(desugaredLib, OutputMode.ClassFile);
+    ToolHelper.runL8(l8Builder.build());
+    desugaredLibraryClassFileCache.put(apiLevel, desugaredLib);
+    return desugaredLib;
+  }
+
+  public String collectKeepRulesWithTraceReferences(
+      Path desugaredProgramClassFile, Path desugaredLibraryClassFile) throws Exception {
+    Path generatedKeepRules = temp.newFile().toPath();
+    TraceReferences.run(
+        "--format",
+        "keep",
+        "--lib",
+        ToolHelper.getAndroidJar(AndroidApiLevel.P).toString(),
+        "--target",
+        desugaredLibraryClassFile.toString(),
+        "--source",
+        desugaredProgramClassFile.toString(),
+        "--output",
+        generatedKeepRules.toString(),
+        "--map-diagnostics",
+        "error",
+        "info");
+    return FileUtils.readTextFile(generatedKeepRules, Charsets.UTF_8);
+  }
+
   public interface KeepRuleConsumer extends StringConsumer {
 
     String get();
diff --git a/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/JavaTimeTest.java b/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/JavaTimeTest.java
index 70b46ae..3e40117 100644
--- a/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/JavaTimeTest.java
+++ b/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/JavaTimeTest.java
@@ -7,21 +7,13 @@
 import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
 import static org.hamcrest.MatcherAssert.assertThat;
 import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.fail;
 
-import com.android.tools.r8.CompilationMode;
-import com.android.tools.r8.L8Command;
 import com.android.tools.r8.NeverInline;
-import com.android.tools.r8.OutputMode;
-import com.android.tools.r8.StringResource;
 import com.android.tools.r8.TestCompileResult;
 import com.android.tools.r8.TestParameters;
-import com.android.tools.r8.ToolHelper;
 import com.android.tools.r8.graph.DexType;
-import com.android.tools.r8.tracereferences.TraceReferences;
 import com.android.tools.r8.utils.AndroidApiLevel;
 import com.android.tools.r8.utils.BooleanUtils;
-import com.android.tools.r8.utils.FileUtils;
 import com.android.tools.r8.utils.StringUtils;
 import com.android.tools.r8.utils.ThrowingSupplier;
 import com.android.tools.r8.utils.codeinspector.CheckCastInstructionSubject;
@@ -32,13 +24,10 @@
 import com.android.tools.r8.utils.codeinspector.MethodSubject;
 import com.android.tools.r8.utils.codeinspector.TryCatchSubject;
 import com.android.tools.r8.utils.codeinspector.TypeSubject;
-import com.google.common.base.Charsets;
-import com.google.common.base.Suppliers;
 import com.google.common.collect.ImmutableSet;
 import java.nio.file.Path;
 import java.util.List;
 import java.util.Set;
-import java.util.function.Supplier;
 import java.util.stream.Collectors;
 import org.junit.Assume;
 import org.junit.Test;
@@ -131,46 +120,6 @@
     assertEquals(expectedCatchGuards, foundCatchGuards);
   }
 
-  // Build the desugared library in class file format.
-  private Path buildDesugaredLibraryClassFile() throws Exception {
-    Path desugaredLib = temp.newFolder().toPath().resolve("desugar_jdk_libs.jar");
-    L8Command.Builder l8Builder =
-        L8Command.builder()
-            .addLibraryFiles(ToolHelper.getAndroidJar(AndroidApiLevel.P))
-            .addProgramFiles(ToolHelper.getDesugarJDKLibs())
-            .addProgramFiles(ToolHelper.DESUGAR_LIB_CONVERSIONS)
-            .setMode(CompilationMode.DEBUG)
-            .addDesugaredLibraryConfiguration(
-                StringResource.fromFile(ToolHelper.DESUGAR_LIB_JSON_FOR_TESTING))
-            .setMinApiLevel(parameters.getApiLevel().getLevel())
-            .setOutput(desugaredLib, OutputMode.ClassFile);
-    ToolHelper.runL8(l8Builder.build());
-    return desugaredLib;
-  }
-
-  Supplier<Path> desugaredLibraryClassFile =
-      Suppliers.memoize(
-          () -> {
-            try {
-              return buildDesugaredLibraryClassFile();
-            } catch (Exception e) {
-              fail("Unexpected");
-              return null;
-            }
-          });
-
-  private String collectKeepRulesWithTraceReferences(
-      Path desugaredProgramClassFile, Path desugaredLibraryClassFile) throws Exception {
-    Path generatedKeepRules = temp.newFile().toPath();
-    TraceReferences.run(
-        "--format", "keep",
-        "--lib", ToolHelper.getAndroidJar(AndroidApiLevel.P).toString(),
-        "--target", desugaredLibraryClassFile.toString(),
-        "--source", desugaredProgramClassFile.toString(),
-        "--output", generatedKeepRules.toString());
-    return FileUtils.readTextFile(generatedKeepRules, Charsets.UTF_8);
-  }
-
   private String desugaredLibraryKeepRules(
       KeepRuleConsumer keepRuleConsumer, ThrowingSupplier<Path, Exception> programSupplier)
       throws Exception {
@@ -181,7 +130,7 @@
         if (traceReferencesKeepRules) {
           desugaredLibraryKeepRules =
               collectKeepRulesWithTraceReferences(
-                  programSupplier.get(), desugaredLibraryClassFile.get());
+                  programSupplier.get(), buildDesugaredLibraryClassFile(parameters.getApiLevel()));
         }
       }
     }
@@ -231,7 +180,7 @@
       // Run on the JVM with desugared library on classpath.
       testForJvm()
           .addProgramFiles(jar)
-          .addRunClasspathFiles(desugaredLibraryClassFile.get())
+          .addRunClasspathFiles(buildDesugaredLibraryClassFile(parameters.getApiLevel()))
           .run(parameters.getRuntime(), TestClass.class)
           .assertSuccessWithOutput(expectedOutput);
     }
diff --git a/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/conversiontests/CallBackConversionTest.java b/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/conversiontests/CallBackConversionTest.java
index 04630af..92d2394 100644
--- a/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/conversiontests/CallBackConversionTest.java
+++ b/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/conversiontests/CallBackConversionTest.java
@@ -102,6 +102,37 @@
   }
 
   @Test
+  public void testCallBackD8Cf() throws Exception {
+    // Use D8 to desugar with Java classfile output.
+    Path jar =
+        testForD8(Backend.CF)
+            .setMinApi(parameters.getApiLevel())
+            .addProgramClasses(Impl.class)
+            .addLibraryClasses(CustomLibClass.class)
+            .enableCoreLibraryDesugaring(parameters.getApiLevel(), new AbsentKeepRuleConsumer())
+            .compile()
+            .inspect(CallBackConversionTest::assertDuplicatedAPI)
+            .writeToZip();
+
+    // Convert to DEX without desugaring and run.
+    testForD8()
+        .addProgramFiles(jar)
+        .setMinApi(parameters.getApiLevel())
+        .disableDesugaring()
+        .compile()
+        .inspect(CallBackConversionTest::assertDuplicatedAPI)
+        .addDesugaredCoreLibraryRunClassPath(
+            this::buildDesugaredLibrary,
+            parameters.getApiLevel(),
+            collectKeepRulesWithTraceReferences(
+                jar, buildDesugaredLibraryClassFile(parameters.getApiLevel())),
+            shrinkDesugaredLibrary)
+        .addRunClasspathFiles(CUSTOM_LIB)
+        .run(parameters.getRuntime(), Impl.class)
+        .assertSuccessWithOutput(EXPECTED_RESULT);
+  }
+
+  @Test
   public void testCallBackR8() throws Exception {
     KeepRuleConsumer keepRuleConsumer = createKeepRuleConsumer(parameters);
     testForR8(Backend.DEX)
diff --git a/src/test/java/com/android/tools/r8/desugaring/interfacemethods/Regress171867367.java b/src/test/java/com/android/tools/r8/desugaring/interfacemethods/Regress171867367.java
index 76366e4..6e01196 100644
--- a/src/test/java/com/android/tools/r8/desugaring/interfacemethods/Regress171867367.java
+++ b/src/test/java/com/android/tools/r8/desugaring/interfacemethods/Regress171867367.java
@@ -3,9 +3,6 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.desugaring.interfacemethods;
 
-import static org.junit.Assert.assertThrows;
-
-import com.android.tools.r8.CompilationFailedException;
 import com.android.tools.r8.D8TestBuilder;
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.TestParameters;
@@ -48,11 +45,7 @@
             .addAndroidBuildVersion()
             .addProgramClasses(TestClass2.class)
             .setMinApi(parameters.getApiLevel());
-    if (parameters.getApiLevel().isLessThan(AndroidApiLevel.L)) {
-      // TODO(b/171867367): Make us not fail when desugaring mixed (desugared and non desugared)
-      // inputs introduce a synthetic already present in the program input.
-      assertThrows(CompilationFailedException.class, d8TestBuilder::compile);
-    } else if (parameters.getApiLevel().isLessThan(AndroidApiLevel.N)) {
+    if (parameters.getApiLevel().isLessThan(AndroidApiLevel.N)) {
       d8TestBuilder
           .run(parameters.getRuntime(), TestClass.class)
           .assertSuccessWithOutputLines("42", "45", "43");
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/callsites/InvokeInterfaceWithRefinedReceiverTest.java b/src/test/java/com/android/tools/r8/ir/optimize/callsites/InvokeInterfaceWithRefinedReceiverTest.java
index d6bcd2b..b53f23c 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/callsites/InvokeInterfaceWithRefinedReceiverTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/callsites/InvokeInterfaceWithRefinedReceiverTest.java
@@ -10,6 +10,7 @@
 
 import com.android.tools.r8.NeverClassInline;
 import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.NoHorizontalClassMerging;
 import com.android.tools.r8.NoVerticalClassMerging;
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.TestParameters;
@@ -45,6 +46,7 @@
         .addInnerClasses(InvokeInterfaceWithRefinedReceiverTest.class)
         .addKeepMainRule(MAIN)
         .enableNoVerticalClassMergingAnnotations()
+        .enableNoHorizontalClassMergingAnnotations()
         .enableNeverClassInliningAnnotations()
         .enableInliningAnnotations()
         .addOptionsModification(
@@ -149,6 +151,7 @@
     }
   }
 
+  @NoHorizontalClassMerging
   @NoVerticalClassMerging
   @NeverClassInline
   static class C implements I {
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/callsites/constants/InvokeInterfacePositiveTest.java b/src/test/java/com/android/tools/r8/ir/optimize/callsites/constants/InvokeInterfacePositiveTest.java
index cb8dfec..9f25fdb 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/callsites/constants/InvokeInterfacePositiveTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/callsites/constants/InvokeInterfacePositiveTest.java
@@ -9,6 +9,7 @@
 
 import com.android.tools.r8.NeverClassInline;
 import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.NoHorizontalClassMerging;
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestParametersCollection;
@@ -47,6 +48,7 @@
         .addKeepMainRule(MAIN)
         .enableNeverClassInliningAnnotations()
         .enableInliningAnnotations()
+        .enableNoHorizontalClassMergingAnnotations()
         .addOptionsModification(CallSiteOptimizationOptions::enableConstantPropagationForTesting)
         .addOptionsModification(
             o -> {
@@ -107,6 +109,7 @@
   }
 
   @NeverClassInline
+  @NoHorizontalClassMerging
   static class B implements I {
     @NeverInline
     @Override
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/callsites/dynamicupperboundtype/InvokeInterfacePositiveTest.java b/src/test/java/com/android/tools/r8/ir/optimize/callsites/dynamicupperboundtype/InvokeInterfacePositiveTest.java
index 4091161..5a06d91 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/callsites/dynamicupperboundtype/InvokeInterfacePositiveTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/callsites/dynamicupperboundtype/InvokeInterfacePositiveTest.java
@@ -9,6 +9,7 @@
 
 import com.android.tools.r8.NeverClassInline;
 import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.NoHorizontalClassMerging;
 import com.android.tools.r8.NoVerticalClassMerging;
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.TestParameters;
@@ -44,6 +45,7 @@
     testForR8(parameters.getBackend())
         .addInnerClasses(InvokeInterfacePositiveTest.class)
         .addKeepMainRule(MAIN)
+        .enableNoHorizontalClassMergingAnnotations()
         .enableNoVerticalClassMergingAnnotations()
         .enableNeverClassInliningAnnotations()
         .enableInliningAnnotations()
@@ -121,6 +123,7 @@
   }
 
   @NeverClassInline
+  @NoHorizontalClassMerging
   static class B implements I {
     @NeverInline
     @Override
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/callsites/nullability/InvokeInterfacePositiveTest.java b/src/test/java/com/android/tools/r8/ir/optimize/callsites/nullability/InvokeInterfacePositiveTest.java
index 27612a2..19fa2a1 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/callsites/nullability/InvokeInterfacePositiveTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/callsites/nullability/InvokeInterfacePositiveTest.java
@@ -9,6 +9,7 @@
 
 import com.android.tools.r8.NeverClassInline;
 import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.NoHorizontalClassMerging;
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestParametersCollection;
@@ -44,6 +45,7 @@
         .addKeepMainRule(MAIN)
         .enableNeverClassInliningAnnotations()
         .enableInliningAnnotations()
+        .enableNoHorizontalClassMergingAnnotations()
         .addOptionsModification(
             o -> {
               // To prevent invoke-interface from being rewritten to invoke-virtual w/ a single
@@ -111,6 +113,7 @@
   }
 
   @NeverClassInline
+  @NoHorizontalClassMerging
   static class B implements I {
     @NeverInline
     @Override
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/classinliner/LibraryOverrideClassInliningTest.java b/src/test/java/com/android/tools/r8/ir/optimize/classinliner/LibraryOverrideClassInliningTest.java
index e3ed9c2..4f020fd 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/classinliner/LibraryOverrideClassInliningTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/classinliner/LibraryOverrideClassInliningTest.java
@@ -9,6 +9,7 @@
 import static org.junit.Assert.assertTrue;
 
 import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.NoHorizontalClassMerging;
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestParametersCollection;
@@ -22,6 +23,7 @@
 @RunWith(Parameterized.class)
 public class LibraryOverrideClassInliningTest extends TestBase {
 
+  @NoHorizontalClassMerging
   public static class SimpleLibraryOverride implements Runnable {
 
     @NeverInline
@@ -90,6 +92,7 @@
             .addProgramClasses(
                 Main.class, SimpleLibraryOverride.class, NonSimpleLibraryOverride.class)
             .addKeepMainRule(Main.class)
+            .enableNoHorizontalClassMergingAnnotations()
             .setMinApi(parameters.getApiLevel())
             .run(parameters.getRuntime(), Main.class)
             .assertSuccessWithOutputLines("running...", "Hello world!")
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/inliner/whyareyounotinlining/WhyAreYouNotInliningInvokeWithUnknownTargetTest.java b/src/test/java/com/android/tools/r8/ir/optimize/inliner/whyareyounotinlining/WhyAreYouNotInliningInvokeWithUnknownTargetTest.java
index 9e862dd..1231e9b 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/inliner/whyareyounotinlining/WhyAreYouNotInliningInvokeWithUnknownTargetTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/inliner/whyareyounotinlining/WhyAreYouNotInliningInvokeWithUnknownTargetTest.java
@@ -6,6 +6,7 @@
 
 import static org.junit.Assert.assertEquals;
 
+import com.android.tools.r8.NoHorizontalClassMerging;
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.utils.StringUtils;
@@ -44,6 +45,7 @@
         .addKeepRules("-whyareyounotinlining class " + A.class.getTypeName() + " { void m(); }")
         .addOptionsModification(options -> options.testing.whyAreYouNotInliningConsumer = out)
         .enableProguardTestOptions()
+        .enableNoHorizontalClassMergingAnnotations()
         .compile();
     out.close();
 
@@ -78,6 +80,7 @@
     }
   }
 
+  @NoHorizontalClassMerging
   static class B implements I {
 
     @Override
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/reflection/GetClassTest.java b/src/test/java/com/android/tools/r8/ir/optimize/reflection/GetClassTest.java
index 1452fd4..8dbe868 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/reflection/GetClassTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/reflection/GetClassTest.java
@@ -46,6 +46,7 @@
     }
   }
 
+  @NoHorizontalClassMerging
   static class GetClassTestMain implements Callable<Class<?>> {
 
     @NeverInline
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/uninstantiatedtypes/InterfaceMethodTest.java b/src/test/java/com/android/tools/r8/ir/optimize/uninstantiatedtypes/InterfaceMethodTest.java
index 9fd146d..f489112 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/uninstantiatedtypes/InterfaceMethodTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/uninstantiatedtypes/InterfaceMethodTest.java
@@ -8,6 +8,7 @@
 import static org.hamcrest.MatcherAssert.assertThat;
 
 import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.NoHorizontalClassMerging;
 import com.android.tools.r8.NoVerticalClassMerging;
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.ToolHelper;
@@ -48,6 +49,7 @@
             .addKeepMainRule(TestClass.class)
             .enableInliningAnnotations()
             .enableNoVerticalClassMergingAnnotations()
+            .enableNoHorizontalClassMergingAnnotations()
             .run(TestClass.class)
             .assertSuccessWithOutput(expectedOutput)
             .inspector();
@@ -95,6 +97,7 @@
   // The purpose of this class is merely to avoid that the invoke-interface instruction in
   // TestClass.test() gets devirtualized to an invoke-virtual instruction. Otherwise the method
   // I.m() would not be present in the output.
+  @NoHorizontalClassMerging
   static class B implements I {
 
     @Override
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/unusedinterfaces/UnusedInterfaceRemovalTest.java b/src/test/java/com/android/tools/r8/ir/optimize/unusedinterfaces/UnusedInterfaceRemovalTest.java
index 413937e..9d11655 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/unusedinterfaces/UnusedInterfaceRemovalTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/unusedinterfaces/UnusedInterfaceRemovalTest.java
@@ -9,6 +9,7 @@
 import static org.hamcrest.MatcherAssert.assertThat;
 import static org.junit.Assert.assertEquals;
 
+import com.android.tools.r8.NoHorizontalClassMerging;
 import com.android.tools.r8.NoVerticalClassMerging;
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.TestParameters;
@@ -40,6 +41,7 @@
         .addInnerClasses(UnusedInterfaceRemovalTest.class)
         .addKeepMainRule(TestClass.class)
         .enableNoVerticalClassMergingAnnotations()
+        .enableNoHorizontalClassMergingAnnotations()
         .setMinApi(parameters.getApiLevel())
         .compile()
         .inspect(this::inspect)
@@ -106,6 +108,7 @@
 
   // To prevent that we detect a single target and start inlining or rewriting the signature in the
   // invoke.
+  @NoHorizontalClassMerging
   static class B implements K {
 
     @Override
diff --git a/src/test/java/com/android/tools/r8/kotlin/lambda/JStyleKotlinLambdaMergingWithEnumUnboxingTest.java b/src/test/java/com/android/tools/r8/kotlin/lambda/JStyleKotlinLambdaMergingWithEnumUnboxingTest.java
index eb7b242..1aef013 100644
--- a/src/test/java/com/android/tools/r8/kotlin/lambda/JStyleKotlinLambdaMergingWithEnumUnboxingTest.java
+++ b/src/test/java/com/android/tools/r8/kotlin/lambda/JStyleKotlinLambdaMergingWithEnumUnboxingTest.java
@@ -6,6 +6,7 @@
 
 import com.android.tools.r8.NeverClassInline;
 import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.NoHorizontalClassMerging;
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestParametersCollection;
@@ -49,6 +50,7 @@
         .addEnumUnboxingInspector(inspector -> inspector.assertUnboxed(EnumUnboxingCandidate.class))
         .enableInliningAnnotations()
         .enableNeverClassInliningAnnotations()
+        .enableNoHorizontalClassMergingAnnotations()
         .setMinApi(parameters.getApiLevel())
         .compile()
         .run(parameters.getRuntime(), Main.class)
@@ -111,6 +113,7 @@
   }
 
   @NeverClassInline
+  @NoHorizontalClassMerging
   public static final class Lambda2 implements I {
 
     @NeverInline
diff --git a/src/test/java/com/android/tools/r8/kotlin/lambda/KStyleKotlinLambdaMergingWithEnumUnboxingTest.java b/src/test/java/com/android/tools/r8/kotlin/lambda/KStyleKotlinLambdaMergingWithEnumUnboxingTest.java
index 61abad2..6edeebc 100644
--- a/src/test/java/com/android/tools/r8/kotlin/lambda/KStyleKotlinLambdaMergingWithEnumUnboxingTest.java
+++ b/src/test/java/com/android/tools/r8/kotlin/lambda/KStyleKotlinLambdaMergingWithEnumUnboxingTest.java
@@ -6,6 +6,7 @@
 
 import com.android.tools.r8.NeverClassInline;
 import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.NoHorizontalClassMerging;
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestParametersCollection;
@@ -48,6 +49,7 @@
         .addEnumUnboxingInspector(inspector -> inspector.assertUnboxed(EnumUnboxingCandidate.class))
         .enableInliningAnnotations()
         .enableNeverClassInliningAnnotations()
+        .enableNoHorizontalClassMergingAnnotations()
         .noMinification()
         .setMinApi(parameters.getApiLevel())
         .compile()
@@ -112,6 +114,7 @@
   }
 
   @NeverClassInline
+  @NoHorizontalClassMerging
   public static final class Lambda2 extends kotlin.jvm.internal.Lambda<kotlin.Unit>
       implements kotlin.jvm.functions.Function0<kotlin.Unit> {
 
diff --git a/src/test/java/com/android/tools/r8/kotlin/lambda/KotlinLambdaMergingTest.java b/src/test/java/com/android/tools/r8/kotlin/lambda/KotlinLambdaMergingTest.java
index 2498467..9f51143 100644
--- a/src/test/java/com/android/tools/r8/kotlin/lambda/KotlinLambdaMergingTest.java
+++ b/src/test/java/com/android/tools/r8/kotlin/lambda/KotlinLambdaMergingTest.java
@@ -528,6 +528,7 @@
     runTest(
         "lambdas_singleton",
         mainClassName,
+        "-nohorizontalclassmerging class *",
         getOptionsModifier(),
         app -> {
           Verifier verifier = new Verifier(app);
diff --git a/src/test/java/com/android/tools/r8/naming/PackagePrivateAllowAccessModificationPackageTest.java b/src/test/java/com/android/tools/r8/naming/PackagePrivateAllowAccessModificationPackageTest.java
new file mode 100644
index 0000000..473df64
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/naming/PackagePrivateAllowAccessModificationPackageTest.java
@@ -0,0 +1,106 @@
+// Copyright (c) 2020, 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.naming;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresentAndRenamed;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import com.android.tools.r8.NeverClassInline;
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.NoHorizontalClassMerging;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class PackagePrivateAllowAccessModificationPackageTest extends TestBase {
+
+  private final TestParameters parameters;
+  private final String[] EXPECTED = new String[] {"B::foo", "ASub::foo", "A::foo"};
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  public PackagePrivateAllowAccessModificationPackageTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void testRuntime() throws Exception {
+    testForRuntime(parameters)
+        .addProgramClasses(A.class, ASub.class, B.class, Main.class)
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines(EXPECTED);
+  }
+
+  @Test
+  public void testR8() throws Exception {
+    testForR8(parameters.getBackend())
+        .addProgramClasses(A.class, ASub.class, B.class, Main.class)
+        .addKeepMainRule(Main.class)
+        .addKeepClassAndMembersRules(A.class)
+        .allowAccessModification()
+        .enableNoHorizontalClassMergingAnnotations()
+        .enableInliningAnnotations()
+        .enableNeverClassInliningAnnotations()
+        .setMinApi(parameters.getApiLevel())
+        .addOptionsModification(
+            options -> {
+              options.enablePackagePrivateAwarePublicization = true;
+            })
+        .compile()
+        .inspect(
+            inspector -> {
+              ClassSubject clazz = inspector.clazz(ASub.class);
+              assertThat(clazz, isPresentAndRenamed());
+            })
+        .run(parameters.getRuntime(), Main.class)
+        // TODO(b/172496438): This should not fail.
+        .assertFailureWithErrorThatThrows(IllegalAccessError.class);
+  }
+
+  @NeverClassInline
+  public static class A {
+
+    @NeverInline
+    void foo() {
+      System.out.println("A::foo");
+    }
+  }
+
+  public static class ASub extends A {
+
+    @Override
+    void foo() {
+      System.out.println("ASub::foo");
+      super.foo();
+    }
+  }
+
+  @NeverClassInline
+  @NoHorizontalClassMerging
+  public static class B {
+
+    @NeverInline
+    void foo() {
+      System.out.println("B::foo");
+      ((A) new ASub()).foo();
+    }
+  }
+
+  public static class Main {
+
+    public static void main(String[] args) {
+      new B().foo();
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/regress/b63935662/Regress63935662.java b/src/test/java/com/android/tools/r8/regress/b63935662/Regress63935662.java
index bc53ac7..1151d20 100644
--- a/src/test/java/com/android/tools/r8/regress/b63935662/Regress63935662.java
+++ b/src/test/java/com/android/tools/r8/regress/b63935662/Regress63935662.java
@@ -4,14 +4,12 @@
 
 package com.android.tools.r8.regress.b63935662;
 
-import com.android.tools.r8.R8Command;
+import com.android.tools.r8.R8FullTestBuilder;
 import com.android.tools.r8.TestBase;
-import com.android.tools.r8.ToolHelper;
-import com.android.tools.r8.utils.AndroidApiLevel;
-import com.android.tools.r8.utils.AndroidApp;
-import com.android.tools.r8.utils.OffOrAuto;
-import java.nio.file.Path;
-import org.junit.Assert;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.google.common.collect.ImmutableList;
+import java.util.List;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.Parameterized;
@@ -19,58 +17,63 @@
 @RunWith(Parameterized.class)
 public class Regress63935662 extends TestBase {
 
-  private Backend backend;
+  private TestParameters parameters;
 
-  @Parameterized.Parameters(name = "Backend: {0}")
-  public static Backend[] data() {
-    return ToolHelper.getBackends();
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
   }
 
-  public Regress63935662(Backend backend) {
-    this.backend = backend;
+  public Regress63935662(TestParameters parameters) {
+    this.parameters = parameters;
   }
 
-  void run(AndroidApp app, Class mainClass) throws Exception {
-    Path proguardConfig =
-        writeTextToTempFile(keepMainProguardConfiguration(mainClass, true, false));
-    R8Command.Builder builder =
-        ToolHelper.prepareR8CommandBuilder(app, emptyConsumer(backend))
-            .addLibraryFiles(runtimeJar(backend))
-            .addProguardConfigurationFiles(proguardConfig);
-    if (backend == Backend.DEX) {
-      builder.setMinApiLevel(AndroidApiLevel.L.getLevel());
-    }
-    String resultFromJava = runOnJava(mainClass);
-    app =
-        ToolHelper.runR8(
-            builder.build(), options -> options.interfaceMethodDesugaring = OffOrAuto.Auto);
-    String result;
-    if (backend == Backend.DEX) {
-      result = runOnArt(app, mainClass);
-    } else {
-      assert backend == Backend.CF;
-      result = runOnJava(app, mainClass);
-    }
-    Assert.assertEquals(resultFromJava, result);
+  void run(R8FullTestBuilder testBuilder, Class<?> mainClass) throws Exception {
+    testBuilder
+        .addKeepRuleFiles()
+        .allowAccessModification()
+        .noMinification()
+        .setMinApi(parameters.getApiLevel())
+        .compile()
+        .run(parameters.getRuntime(), mainClass)
+        .assertSuccessWithOutput(runOnJava(mainClass));
   }
 
   @Test
   public void test() throws Exception {
-    Class mainClass = TestClass.class;
-    AndroidApp app = readClasses(
-        TestClass.Top.class, TestClass.Left.class, TestClass.Right.class, TestClass.Bottom.class,
-        TestClass.X1.class, TestClass.X2.class, TestClass.X3.class, TestClass.X4.class, TestClass.X5.class,
+    Class<?> mainClass = TestClass.class;
+    List<Class<?>> app =
+        ImmutableList.of(
+            TestClass.Top.class,
+            TestClass.Left.class,
+            TestClass.Right.class,
+            TestClass.Bottom.class,
+            TestClass.X1.class,
+            TestClass.X2.class,
+            TestClass.X3.class,
+            TestClass.X4.class,
+            TestClass.X5.class,
+            mainClass);
+    run(
+        testForR8(parameters.getBackend())
+            .addProgramClasses(app)
+            .addKeepMainRule(mainClass)
+            .enableNoHorizontalClassMergingAnnotations(),
         mainClass);
-    run(app, mainClass);
   }
 
   @Test
   public void test2() throws Exception {
-    Class mainClass = TestFromBug.class;
-    AndroidApp app = readClasses(
-        TestFromBug.Map.class, TestFromBug.AbstractMap.class,
-        TestFromBug.ConcurrentMap.class, TestFromBug.ConcurrentHashMap.class,
+    Class<?> mainClass = TestFromBug.class;
+    List<Class<?>> app =
+        ImmutableList.of(
+            TestFromBug.Map.class,
+            TestFromBug.AbstractMap.class,
+            TestFromBug.ConcurrentMap.class,
+            TestFromBug.ConcurrentHashMap.class,
+            mainClass);
+    run(
+        testForR8(parameters.getBackend()).addProgramClasses(app).addKeepMainRule(mainClass),
         mainClass);
-    run(app, mainClass);
   }
 }
diff --git a/src/test/java/com/android/tools/r8/regress/b63935662/TestClass.java b/src/test/java/com/android/tools/r8/regress/b63935662/TestClass.java
index 878fcff..6597695 100644
--- a/src/test/java/com/android/tools/r8/regress/b63935662/TestClass.java
+++ b/src/test/java/com/android/tools/r8/regress/b63935662/TestClass.java
@@ -4,6 +4,8 @@
 
 package com.android.tools.r8.regress.b63935662;
 
+import com.android.tools.r8.NoHorizontalClassMerging;
+
 public class TestClass {
 
   interface Top {
@@ -20,31 +22,36 @@
 
   interface Bottom extends Left, Right {}
 
+  @NoHorizontalClassMerging
   static class X1 implements Bottom {
     void test() {
       System.out.println(name());
     }
   }
 
-  static class X2 implements Left, Right  {
+  @NoHorizontalClassMerging
+  static class X2 implements Left, Right {
     void test() {
       System.out.println(name());
     }
   }
 
-  static class X3 implements Right, Left   {
+  @NoHorizontalClassMerging
+  static class X3 implements Right, Left {
     void test() {
       System.out.println(name());
     }
   }
 
-  static class X4 implements Left, Right, Top  {
+  @NoHorizontalClassMerging
+  static class X4 implements Left, Right, Top {
     void test() {
       System.out.println(name());
     }
   }
 
-  static class X5 implements Right, Left, Top   {
+  @NoHorizontalClassMerging
+  static class X5 implements Right, Left, Top {
     void test() {
       System.out.println(name());
     }
diff --git a/src/test/java/com/android/tools/r8/resolution/interfacetargets/InvokeInterfaceClInitTest.java b/src/test/java/com/android/tools/r8/resolution/interfacetargets/InvokeInterfaceClInitTest.java
index e29f3fc..3d20751 100644
--- a/src/test/java/com/android/tools/r8/resolution/interfacetargets/InvokeInterfaceClInitTest.java
+++ b/src/test/java/com/android/tools/r8/resolution/interfacetargets/InvokeInterfaceClInitTest.java
@@ -14,12 +14,12 @@
 import com.android.tools.r8.TestRuntime.CfVm;
 import com.android.tools.r8.TestRuntime.DexRuntime;
 import com.android.tools.r8.ToolHelper.DexVm;
+import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.transformers.ClassTransformer;
-import com.android.tools.r8.utils.AndroidApiLevel;
 import java.io.IOException;
 import java.util.concurrent.ExecutionException;
 import org.hamcrest.CoreMatchers;
@@ -36,9 +36,6 @@
 
   private final TestParameters parameters;
 
-  static {
-  }
-
   @Parameters(name = "{0}")
   public static TestParametersCollection data() {
     return getTestParameters().withAllRuntimesAndApiLevels().build();
@@ -83,9 +80,6 @@
     if (dexRuntime.getVm().isOlderThanOrEqual(DexVm.ART_4_4_4_TARGET)) {
       return containsString("NoSuchMethodError");
     }
-    if (parameters.getApiLevel().isGreaterThanOrEqualTo(AndroidApiLevel.N)) {
-      return containsString("java.lang.ClassNotFoundException");
-    }
     return containsString("java.lang.VerifyError");
   }
 
@@ -121,7 +115,8 @@
                   String descriptor,
                   String signature,
                   String[] exceptions) {
-                return super.visitMethod(access, "<clinit>", descriptor, signature, exceptions);
+                return super.visitMethod(
+                    access | Constants.ACC_STATIC, "<clinit>", descriptor, signature, exceptions);
               }
             })
         .transform();
diff --git a/src/test/java/com/android/tools/r8/shaking/UninitializedInstantiatedTypeShakingTest.java b/src/test/java/com/android/tools/r8/shaking/UninitializedInstantiatedTypeShakingTest.java
index 7a9be4a..3cf998b 100644
--- a/src/test/java/com/android/tools/r8/shaking/UninitializedInstantiatedTypeShakingTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/UninitializedInstantiatedTypeShakingTest.java
@@ -8,6 +8,7 @@
 import static org.hamcrest.CoreMatchers.not;
 import static org.hamcrest.MatcherAssert.assertThat;
 
+import com.android.tools.r8.NoHorizontalClassMerging;
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestParametersCollection;
@@ -37,6 +38,7 @@
     testForR8(parameters.getBackend())
         .addInnerClasses(UninitializedInstantiatedTypeShakingTest.class)
         .addKeepMainRule(TestClass.class)
+        .enableNoHorizontalClassMergingAnnotations()
         .setMinApi(parameters.getRuntime())
         .compile()
         .inspect(UninitializedInstantiatedTypeShakingTest::verifyOutput)
@@ -83,6 +85,7 @@
     }
   }
 
+  @NoHorizontalClassMerging
   static class B implements I {
 
     @Override
@@ -91,6 +94,7 @@
     }
   }
 
+  @NoHorizontalClassMerging
   static class C implements I {
 
     @Override
diff --git a/src/test/java/com/android/tools/r8/shaking/assumenosideeffects/AssumenosideeffectsPropagationWithoutMatchingDefinitionTest.java b/src/test/java/com/android/tools/r8/shaking/assumenosideeffects/AssumenosideeffectsPropagationWithoutMatchingDefinitionTest.java
index 8462593..e4edf08 100644
--- a/src/test/java/com/android/tools/r8/shaking/assumenosideeffects/AssumenosideeffectsPropagationWithoutMatchingDefinitionTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/assumenosideeffects/AssumenosideeffectsPropagationWithoutMatchingDefinitionTest.java
@@ -9,6 +9,7 @@
 import static org.junit.Assert.assertTrue;
 
 import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.NoHorizontalClassMerging;
 import com.android.tools.r8.NoVerticalClassMerging;
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.TestParameters;
@@ -44,6 +45,7 @@
     testForR8(parameters.getBackend())
         .addInnerClasses(AssumenosideeffectsPropagationWithoutMatchingDefinitionTest.class)
         .enableNoVerticalClassMergingAnnotations()
+        .enableNoHorizontalClassMergingAnnotations()
         .enableInliningAnnotations()
         .addKeepMainRule(MAIN)
         .addKeepRules(
@@ -99,6 +101,7 @@
   }
 
   // To bother single target resolution. In fact, not used at all.
+  @NoHorizontalClassMerging
   static class AnotherLogger implements LoggerInterface {
     @Override
     public void debug(String message) {
diff --git a/src/test/java/com/android/tools/r8/shaking/clinit/ClassInitializationTriggersIndirectInterfaceInitializationTest.java b/src/test/java/com/android/tools/r8/shaking/clinit/ClassInitializationTriggersIndirectInterfaceInitializationTest.java
new file mode 100644
index 0000000..c6e5eff
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/clinit/ClassInitializationTriggersIndirectInterfaceInitializationTest.java
@@ -0,0 +1,110 @@
+// Copyright (c) 2020, 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.clinit;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static com.android.tools.r8.utils.codeinspector.Matchers.onlyIf;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+
+import com.android.tools.r8.NeverClassInline;
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.NoUnusedInterfaceRemoval;
+import com.android.tools.r8.NoVerticalClassMerging;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class ClassInitializationTriggersIndirectInterfaceInitializationTest extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  public ClassInitializationTriggersIndirectInterfaceInitializationTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void test() throws Exception {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(getClass())
+        .addKeepMainRule(Main.class)
+        .enableInliningAnnotations()
+        .enableNeverClassInliningAnnotations()
+        .enableNoUnusedInterfaceRemovalAnnotations()
+        .enableNoVerticalClassMergingAnnotations()
+        .setMinApi(parameters.getApiLevel())
+        .compile()
+        .inspect(
+            inspector -> {
+              // Verify that I's class initializer is still present.
+              ClassSubject iClassSubject = inspector.clazz(I.class);
+              assertThat(iClassSubject, isPresent());
+              assertThat(
+                  iClassSubject.clinit(),
+                  onlyIf(hasDefaultInterfaceMethodsSupport(parameters), isPresent()));
+
+              // Verify that J is still there.
+              ClassSubject jClassSubject = inspector.clazz(J.class);
+              assertThat(jClassSubject, isPresent());
+
+              // Verify that A still implements J.
+              ClassSubject aClassSubject = inspector.clazz(A.class);
+              assertThat(aClassSubject, isPresent());
+              assertEquals(1, aClassSubject.getDexProgramClass().getInterfaces().size());
+              assertTrue(aClassSubject.isImplementing(jClassSubject));
+            })
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLinesIf(
+            hasDefaultInterfaceMethodsSupport(parameters), "I.<clinit>()", "I.m()")
+        .assertSuccessWithOutputLinesIf(!hasDefaultInterfaceMethodsSupport(parameters), "I.m()");
+  }
+
+  static class Main {
+
+    public static void main(String[] args) {
+      new A().m();
+    }
+  }
+
+  @NoUnusedInterfaceRemoval
+  @NoVerticalClassMerging
+  interface I {
+
+    Greeter greeter = new Greeter("I.<clinit>()");
+
+    // TODO(b/144266257): This should not require a @NeverInline annotation, since tree shaking
+    //  should not be allowed to remove the default interface method if that could change interface
+    //  initialization side effects.
+    @NeverInline
+    default void m() {
+      System.out.println("I.m()");
+    }
+  }
+
+  @NoUnusedInterfaceRemoval
+  @NoVerticalClassMerging
+  interface J extends I {}
+
+  @NeverClassInline
+  static class A implements J {}
+
+  static class Greeter {
+
+    Greeter(String greeting) {
+      System.out.println(greeting);
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/shaking/clinit/InterfaceInitializedByInvokeStaticOnSubInterfaceTest.java b/src/test/java/com/android/tools/r8/shaking/clinit/InterfaceInitializedByInvokeStaticOnSubInterfaceTest.java
index 2e0f754..943e680 100644
--- a/src/test/java/com/android/tools/r8/shaking/clinit/InterfaceInitializedByInvokeStaticOnSubInterfaceTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/clinit/InterfaceInitializedByInvokeStaticOnSubInterfaceTest.java
@@ -6,7 +6,6 @@
 
 import static org.junit.Assume.assumeTrue;
 
-import com.android.tools.r8.DesugarTestConfiguration;
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestParametersCollection;
 import com.android.tools.r8.graph.AppView;
@@ -35,22 +34,7 @@
     testForDesugaring(parameters)
         .addInnerClasses(getClass())
         .run(parameters.getRuntime(), TestClass.class)
-        .applyIf(
-            DesugarTestConfiguration::isJavac,
-            runResult -> runResult.assertSuccessWithOutputLines("J"))
-        .applyIf(
-            DesugarTestConfiguration::isNotJavac,
-            runResult -> {
-              if (parameters
-                  .getApiLevel()
-                  .isGreaterThanOrEqualTo(apiLevelWithStaticInterfaceMethodsSupport())) {
-                runResult.assertSuccessWithOutputLines("J");
-              } else {
-                // TODO(b/172050082): Calling greet() on the companion class of J should trigger J's
-                //  class initializer.
-                runResult.assertSuccessWithEmptyOutput();
-              }
-            });
+        .assertSuccessWithOutputLines("J");
   }
 
   @Test
diff --git a/src/test/java/com/android/tools/r8/shaking/clinit/InterfaceInitializedByInvokeStaticTest.java b/src/test/java/com/android/tools/r8/shaking/clinit/InterfaceInitializedByInvokeStaticTest.java
index 4f2eb00..a052428 100644
--- a/src/test/java/com/android/tools/r8/shaking/clinit/InterfaceInitializedByInvokeStaticTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/clinit/InterfaceInitializedByInvokeStaticTest.java
@@ -6,7 +6,6 @@
 
 import static org.junit.Assume.assumeTrue;
 
-import com.android.tools.r8.DesugarTestConfiguration;
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestParametersCollection;
 import com.android.tools.r8.graph.AppView;
@@ -35,22 +34,7 @@
     testForDesugaring(parameters)
         .addInnerClasses(getClass())
         .run(parameters.getRuntime(), TestClass.class)
-        .applyIf(
-            DesugarTestConfiguration::isJavac,
-            runResult -> runResult.assertSuccessWithOutputLines("I"))
-        .applyIf(
-            DesugarTestConfiguration::isNotJavac,
-            runResult -> {
-              if (parameters
-                  .getApiLevel()
-                  .isGreaterThanOrEqualTo(apiLevelWithStaticInterfaceMethodsSupport())) {
-                runResult.assertSuccessWithOutputLines("I");
-              } else {
-                // TODO(b/172050082): Calling greet() on the companion class of I should trigger I's
-                //  class initializer.
-                runResult.assertSuccessWithEmptyOutput();
-              }
-            });
+        .assertSuccessWithOutputLines("I");
   }
 
   @Test
diff --git a/src/test/java/com/android/tools/r8/shaking/clinit/InterfaceNotInitializedByInvokeStaticOnSubClassTest.java b/src/test/java/com/android/tools/r8/shaking/clinit/InterfaceNotInitializedByInvokeStaticOnSubClassTest.java
index 88c1089..385b549 100644
--- a/src/test/java/com/android/tools/r8/shaking/clinit/InterfaceNotInitializedByInvokeStaticOnSubClassTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/clinit/InterfaceNotInitializedByInvokeStaticOnSubClassTest.java
@@ -4,6 +4,7 @@
 
 package com.android.tools.r8.shaking.clinit;
 
+import static org.junit.Assert.assertEquals;
 import static org.junit.Assume.assumeTrue;
 
 import com.android.tools.r8.TestParameters;
@@ -48,6 +49,7 @@
         .allowStdoutMessages()
         .setMinApi(parameters.getApiLevel())
         .compile()
+        .inspect(inspector -> assertEquals(1, inspector.allClasses().size()))
         .run(parameters.getRuntime(), TestClass.class)
         .assertSuccessWithEmptyOutput();
   }
diff --git a/src/test/java/com/android/tools/r8/shaking/clinit/InterfaceWithDefaultMethodNotInitializedByInvokeStaticOnSubInterfaceTest.java b/src/test/java/com/android/tools/r8/shaking/clinit/InterfaceWithDefaultMethodNotInitializedByInvokeStaticOnSubInterfaceTest.java
index 115d6e8..3d88fe8 100644
--- a/src/test/java/com/android/tools/r8/shaking/clinit/InterfaceWithDefaultMethodNotInitializedByInvokeStaticOnSubInterfaceTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/clinit/InterfaceWithDefaultMethodNotInitializedByInvokeStaticOnSubInterfaceTest.java
@@ -4,6 +4,7 @@
 
 package com.android.tools.r8.shaking.clinit;
 
+import static org.junit.Assert.assertEquals;
 import static org.junit.Assume.assumeTrue;
 
 import com.android.tools.r8.TestParameters;
@@ -49,6 +50,7 @@
         .allowStdoutMessages()
         .setMinApi(parameters.getApiLevel())
         .compile()
+        .inspect(inspector -> assertEquals(1, inspector.allClasses().size()))
         .run(parameters.getRuntime(), TestClass.class)
         .assertSuccessWithEmptyOutput();
   }
diff --git a/src/test/java/com/android/tools/r8/shaking/keepclassmembers/KeepInterfaceMethodTest.java b/src/test/java/com/android/tools/r8/shaking/keepclassmembers/KeepInterfaceMethodTest.java
index 93309e8..e42dfe3 100644
--- a/src/test/java/com/android/tools/r8/shaking/keepclassmembers/KeepInterfaceMethodTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/keepclassmembers/KeepInterfaceMethodTest.java
@@ -10,6 +10,7 @@
 import static org.junit.Assume.assumeTrue;
 
 import com.android.tools.r8.CompilationFailedException;
+import com.android.tools.r8.NoHorizontalClassMerging;
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.TestParametersCollection;
@@ -82,6 +83,7 @@
         .addProgramClasses(I.class, A.class, B.class, Main.class)
         .addKeepRules("-keepclassmembers class " + I.class.getTypeName() + " { void foo(); }")
         .addKeepMainRule(Main.class)
+        .enableNoHorizontalClassMergingAnnotations()
         .setMinApi(parameters.getApiLevel())
         .run(parameters.getRuntime(), Main.class)
         .assertSuccessWithOutputLines("A.foo")
@@ -110,6 +112,7 @@
     }
   }
 
+  @NoHorizontalClassMerging
   public static class B implements I {
 
     @Override
diff --git a/src/test/java/com/android/tools/r8/utils/codeinspector/AbsentClassSubject.java b/src/test/java/com/android/tools/r8/utils/codeinspector/AbsentClassSubject.java
index ee4fe7b..28f419f 100644
--- a/src/test/java/com/android/tools/r8/utils/codeinspector/AbsentClassSubject.java
+++ b/src/test/java/com/android/tools/r8/utils/codeinspector/AbsentClassSubject.java
@@ -96,6 +96,11 @@
   }
 
   @Override
+  public boolean isImplementing(ClassSubject subject) {
+    throw new Unreachable("Cannot determine if an absent class is implementing a given interface");
+  }
+
+  @Override
   public DexProgramClass getDexProgramClass() {
     return null;
   }
diff --git a/src/test/java/com/android/tools/r8/utils/codeinspector/ClassSubject.java b/src/test/java/com/android/tools/r8/utils/codeinspector/ClassSubject.java
index 54e3d63..ff544ab 100644
--- a/src/test/java/com/android/tools/r8/utils/codeinspector/ClassSubject.java
+++ b/src/test/java/com/android/tools/r8/utils/codeinspector/ClassSubject.java
@@ -167,6 +167,8 @@
 
   public abstract boolean isPublic();
 
+  public abstract boolean isImplementing(ClassSubject subject);
+
   public String dumpMethods() {
     StringBuilder dump = new StringBuilder();
     forAllMethods(
diff --git a/src/test/java/com/android/tools/r8/utils/codeinspector/FoundClassSubject.java b/src/test/java/com/android/tools/r8/utils/codeinspector/FoundClassSubject.java
index d8aa792..eafb952 100644
--- a/src/test/java/com/android/tools/r8/utils/codeinspector/FoundClassSubject.java
+++ b/src/test/java/com/android/tools/r8/utils/codeinspector/FoundClassSubject.java
@@ -300,6 +300,17 @@
   }
 
   @Override
+  public boolean isImplementing(ClassSubject subject) {
+    assertTrue(subject.isPresent());
+    for (DexType itf : getDexProgramClass().interfaces) {
+      if (itf.toSourceString().equals(subject.getFinalName())) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  @Override
   public boolean isAnnotation() {
     return dexClass.accessFlags.isAnnotation();
   }
diff --git a/third_party/opensource-apps/chanu.tar.gz.sha1 b/third_party/opensource-apps/chanu.tar.gz.sha1
new file mode 100644
index 0000000..f7f0433
--- /dev/null
+++ b/third_party/opensource-apps/chanu.tar.gz.sha1
@@ -0,0 +1 @@
+af80654ff4a0f399e55e4dafdc32a3f4b28145b7
\ No newline at end of file
diff --git a/third_party/opensource-apps/friendlyeats.tar.gz.sha1 b/third_party/opensource-apps/friendlyeats.tar.gz.sha1
new file mode 100644
index 0000000..952e2a8
--- /dev/null
+++ b/third_party/opensource-apps/friendlyeats.tar.gz.sha1
@@ -0,0 +1 @@
+f4ba305339e9285e8e865c526c737d385528e1c4
\ No newline at end of file
diff --git a/third_party/opensource-apps/iosched.tar.gz.sha1 b/third_party/opensource-apps/iosched.tar.gz.sha1
new file mode 100644
index 0000000..c99709c
--- /dev/null
+++ b/third_party/opensource-apps/iosched.tar.gz.sha1
@@ -0,0 +1 @@
+f3f855e6b3d773093c032c36c54c920d5ff018ec
\ No newline at end of file
diff --git a/third_party/opensource-apps/sunflower.tar.gz.sha1 b/third_party/opensource-apps/sunflower.tar.gz.sha1
new file mode 100644
index 0000000..06aec6d
--- /dev/null
+++ b/third_party/opensource-apps/sunflower.tar.gz.sha1
@@ -0,0 +1 @@
+52fe1160095f2f46d13782dc19d5201792ac2ec1
\ No newline at end of file
diff --git a/third_party/opensource-apps/wikipedia.tar.gz.sha1 b/third_party/opensource-apps/wikipedia.tar.gz.sha1
new file mode 100644
index 0000000..bfb14cb
--- /dev/null
+++ b/third_party/opensource-apps/wikipedia.tar.gz.sha1
@@ -0,0 +1 @@
+0e7d8398779c2dfa449c598556f4e57a860aa9e4
\ No newline at end of file
diff --git a/tools/git_sync_cl_chain.py b/tools/git_sync_cl_chain.py
index ef10a73..5a229bd 100755
--- a/tools/git_sync_cl_chain.py
+++ b/tools/git_sync_cl_chain.py
@@ -40,21 +40,35 @@
 
 def ParseOptions(argv):
   result = optparse.OptionParser()
-  result.add_option('--message', '-m', help='Message for patchset')
+  result.add_option('--delete', '-d',
+                    help='Delete closed branches',
+                    choices=['y', 'n', 'ask'],
+                    default='ask')
+  result.add_option('--leave_upstream', '--leave-upstream',
+                    help='To not update the upstream of the first open branch',
+                    action='store_true')
+  result.add_option('--message', '-m',
+                    help='Message for patchset', default='Sync')
   result.add_option('--rebase',
                     help='To use `git pull --rebase` instead of `git pull`',
                     action='store_true')
   result.add_option('--no_upload', '--no-upload',
                     help='Disable uploading to Gerrit', action='store_true')
+  result.add_option('--skip_master', '--skip-master',
+                    help='Disable syncing for master',
+                    action='store_true')
   (options, args) = result.parse_args(argv)
   options.upload = not options.no_upload
+  assert options.delete != 'y' or not options.leave_upstream, (
+      'Inconsistent options: cannot leave the upstream of the first open ' +
+      'branch (--leave_upstream) and delete the closed branches at the same ' +
+      'time (--delete).')
   assert options.message, 'A message for the patchset is required.'
   assert len(args) == 0
   return options
 
 def main(argv):
   options = ParseOptions(argv)
-  rebase_args = ['--rebase'] if options.rebase else []
   with utils.ChangedWorkingDirectory(REPO_ROOT, quiet=True):
     branches = [
         parse(line)
@@ -74,26 +88,95 @@
     stack = []
     while current_branch:
       stack.append(current_branch)
-      if current_branch.upstream is None or current_branch.upstream == 'master':
+      if current_branch.upstream is None:
         break
       current_branch = get_branch_with_name(current_branch.upstream, branches)
 
+    closed_branches = []
+    has_seen_local_branch = False # A branch that is not uploaded.
+    has_seen_open_branch = False # A branch that is not closed.
     while len(stack) > 0:
       branch = stack.pop()
-      print('Syncing ' + branch.name)
+
       utils.RunCmd(['git', 'checkout', branch.name], quiet=True)
-      utils.RunCmd(['git', 'pull'] + rebase_args, quiet=True)
+
+      status = get_status_for_current_branch()
+      print('Syncing %s (status: %s)' % (branch.name, status))
+
+      pull_for_current_branch(branch, options)
+
+      if branch.name == 'master':
+        continue
+
+      if status == 'closed':
+        assert not has_seen_local_branch, (
+            'Unexpected closed branch %s after new branch' % branch.name)
+        assert not has_seen_open_branch, (
+            'Unexpected closed branch %s after open branch' % branch.name)
+        closed_branches.append(branch.name)
+        continue
+
+      if not options.leave_upstream:
+        if not has_seen_open_branch and len(closed_branches) > 0:
+          print(
+              'Setting upstream for first open branch %s to master'
+                  % branch.name)
+          set_upstream_for_current_branch_to_master()
+
+      has_seen_open_branch = True
+      has_seen_local_branch = has_seen_local_branch or (status == 'None')
+
       if options.upload:
-        utils.RunCmd(['git', 'cl', 'upload', '-m', options.message], quiet=True)
+        if has_seen_local_branch:
+          print(
+              'Cannot upload branch %s since it comes after a local branch'
+                  % branch.name)
+        else:
+          utils.RunCmd(
+              ['git', 'cl', 'upload', '-m', options.message], quiet=True)
+
+    if get_delete_branches_option(closed_branches, options):
+      delete_branches(closed_branches)
 
     utils.RunCmd(['git', 'cl', 'issue'])
 
+def delete_branches(branches):
+  assert len(branches) > 0
+  utils.RunCmd(['git', 'branch', '-D'].extend(branches), quiet=True)
+
 def get_branch_with_name(name, branches):
   for branch in branches:
     if branch.name == name:
       return branch
   return None
 
+def get_delete_branches_option(closed_branches, options):
+  if len(closed_branches) == 0:
+    return False
+  if options.leave_upstream:
+    return False
+  if options.delete == 'y':
+    return True
+  if options.delete == 'n':
+    return False
+  assert options.delete == 'ask'
+  print('Delete closed branches: %s (Y/N)?' % ", ".join(closed_branches))
+  answer = sys.stdin.read(1)
+  return answer.lower() == 'y'
+
+def get_status_for_current_branch():
+  return utils.RunCmd(['git', 'cl', 'status', '--field', 'status'], quiet=True)[0].strip()
+
+def pull_for_current_branch(branch, options):
+  if branch.name == 'master' and options.skip_master:
+    return
+  rebase_args = ['--rebase'] if options.rebase else []
+  utils.RunCmd(['git', 'pull'] + rebase_args, quiet=True)
+
+
+def set_upstream_for_current_branch_to_master():
+  utils.RunCmd(['git', 'cl', 'upstream', 'master'], quiet=True)
+
 # Parses a line from the output of `git branch -vv`.
 #
 # Example output ('*' denotes the current branch):
diff --git a/tools/r8_release.py b/tools/r8_release.py
index 3e743b3..c3aff38 100755
--- a/tools/r8_release.py
+++ b/tools/r8_release.py
@@ -362,15 +362,12 @@
       g4_open('src.jar')
       g4_open('lib.jar')
       g4_open('lib.jar.map')
-      g4_open('desugar_jdk_libs.json')
       g4_open('desugar_jdk_libs_configuration.jar')
       download_file(options.version, 'r8-full-exclude-deps.jar', 'full.jar')
       download_file(options.version, 'r8-src.jar', 'src.jar')
       download_file(options.version, 'r8lib-exclude-deps.jar', 'lib.jar')
       download_file(
           options.version, 'r8lib-exclude-deps.jar.map', 'lib.jar.map')
-      download_file(options.version, 'desugar_jdk_libs.json',
-                    'desugar_jdk_libs.json')
       download_file(options.version, 'desugar_jdk_libs_configuration.jar',
                     'desugar_jdk_libs_configuration.jar')
       g4_open('METADATA')
diff --git a/tools/run_on_app_dump.py b/tools/run_on_app_dump.py
index af6d337..bf5d4c7 100755
--- a/tools/run_on_app_dump.py
+++ b/tools/run_on_app_dump.py
@@ -1,7 +1,7 @@
 #!/usr/bin/env python
-#  Copyright (c) 2020, 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.
+# Copyright (c) 2020, 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.
 
 import adb
 import apk_masseur
@@ -103,7 +103,62 @@
     'url': 'https://github.com/mkj-gram/applymapping',
     'revision': 'e3ae14b8c16fa4718e5dea8f7ad00937701b3c48',
     'folder': 'applymapping',
-  })
+  }),
+  App({
+    'id': 'com.chanapps.four.activity',
+    'name': 'chanu',
+    'dump_app': 'dump_app.zip',
+    'apk_app': 'app-release.apk',
+    'url': 'https://github.com/mkj-gram/chanu.git',
+    'revision': '6e53458f167b6d78398da60c20fd0da01a232617',
+    'folder': 'chanu',
+    # TODO(b/172535996): Fix recompilation
+    'skip_recompilation': True
+  }),
+  # TODO(b/172539375): Monkey runner fails on recompilation.
+  App({
+    'id': 'com.google.firebase.example.fireeats',
+    'name': 'FriendlyEats',
+    'dump_app': 'dump_app.zip',
+    'apk_app': 'app-release-unsigned.apk',
+    'url': 'https://github.com/firebase/friendlyeats-android',
+    'revision': '7c6dd016fc31ea5ecb948d5166b8479efc3775cc',
+    'folder': 'friendlyeats',
+  }),
+  App({
+    'id': 'com.google.samples.apps.sunflower',
+    'name': 'Sunflower',
+    'dump_app': 'dump_app.zip',
+    'apk_app': 'app-debug.apk',
+    # TODO(b/172549283): Compiling tests fails
+    'id_test': 'com.example.applymapping.test',
+    'dump_test': 'dump_test.zip',
+    'apk_test': 'app-debug-androidTest.apk',
+    'url': 'https://github.com/android/sunflower',
+    'revision': '0c4c88fdad2a74791199dffd1a6559559b1dbd4a',
+    'folder': 'sunflower',
+    # TODO(b/172548728): Fix recompilation
+    'skip_recompilation': True
+  }),
+  # TODO(b/172565385): Monkey runner fails on recompilation
+  App({
+    'id': 'com.google.samples.apps.iosched',
+    'name': 'iosched',
+    'dump_app': 'dump_app.zip',
+    'apk_app': 'mobile-release.apk',
+    'url': 'https://github.com/christofferqa/iosched.git',
+    'revision': '581cbbe2253711775dbccb753cdb53e7e506cb02',
+    'folder': 'iosched',
+  }),
+  App({
+    'id': 'org.wikipedia',
+    'name': 'Wikipedia',
+    'dump_app': 'dump_app.zip',
+    'apk_app': 'app-prod-release.apk',
+    'url': 'https://github.com/wikimedia/apps-android-wikipedia',
+    'revision': '0fa7cad843c66313be8e25790ef084cf1a1fa67e',
+    'folder': 'wikipedia',
+  }),
 ]
 
 
@@ -232,7 +287,6 @@
           and not is_last_build(compilation_step, compilation_steps)):
         result['recompilation_status'] = 'failed'
         warn('Failed to build {} with {}'.format(app.name, shrinker))
-        break
       recomp_jar = new_recomp_jar
     except Exception as e:
       warn('Failed to build {} with {}'.format(app.name, shrinker))
@@ -270,18 +324,21 @@
       test_jar = build_test_with_shrinker(
         app, options, temp_dir, app_dir,shrinker, compilation_step,
         result['output_mapping'])
-      original_test_apk = os.path.join(app_dir, app.apk_test)
-      test_apk_destination = os.path.join(
-        temp_dir,"{}_{}.test.apk".format(app.id_test, compilation_step))
-      apk_masseur.masseur(
-        original_test_apk, dex=test_jar, resources='META-INF/services/*',
-        out=test_apk_destination,
-        quiet=options.quiet, logging=is_logging_enabled_for(app, options),
-        keystore=options.keystore)
-      result['instrumentation_test_status'] = 'success' if adb.run_instrumented(
-        app.id, app.id_test, options.emulator_id, app_apk_destination,
-        test_apk_destination, options.quiet,
-        is_logging_enabled_for(app, options)) else 'failed'
+      if not test_jar:
+        result['instrumentation_test_status'] = 'compilation_failed'
+      else:
+        original_test_apk = os.path.join(app_dir, app.apk_test)
+        test_apk_destination = os.path.join(
+          temp_dir,"{}_{}.test.apk".format(app.id_test, compilation_step))
+        apk_masseur.masseur(
+          original_test_apk, dex=test_jar, resources='META-INF/services/*',
+          out=test_apk_destination,
+          quiet=options.quiet, logging=is_logging_enabled_for(app, options),
+          keystore=options.keystore)
+        result['instrumentation_test_status'] = 'success' if adb.run_instrumented(
+          app.id, app.id_test, options.emulator_id, app_apk_destination,
+          test_apk_destination, options.quiet,
+          is_logging_enabled_for(app, options)) else 'failed'
 
     results.append(result)
     if result.get('recompilation_status') != 'success':
@@ -335,6 +392,7 @@
 
   return (app_jar, app_mapping, recomp_jar)
 
+
 def build_test_with_shrinker(app, options, temp_dir, app_dir, shrinker,
                              compilation_step_index, mapping):
   r8jar = os.path.join(
@@ -371,7 +429,8 @@
       app.name, shrinker, compilation_step_index))
 
   if compile_result != 0 or not os.path.isfile(out_jar):
-    assert False, "Compilation of test_jar failed"
+    return None
+
   shutil.move(out_jar, test_jar)
 
   return test_jar