Implement simple class merger.

BUG=

Change-Id: Ib22cf7a7d10797b0ba7ed6ef8fb5aa5fda9aaa60

diff --git a/src/main/java/com/android/tools/r8/R8.java b/src/main/java/com/android/tools/r8/R8.java
index 44a687c..a4cd4db 100644
--- a/src/main/java/com/android/tools/r8/R8.java
+++ b/src/main/java/com/android/tools/r8/R8.java
@@ -31,6 +31,7 @@
 import com.android.tools.r8.shaking.ReasonPrinter;
 import com.android.tools.r8.shaking.RootSetBuilder;
 import com.android.tools.r8.shaking.RootSetBuilder.RootSet;
+import com.android.tools.r8.shaking.SimpleClassMerger;
 import com.android.tools.r8.shaking.TreePruner;
 import com.android.tools.r8.utils.AndroidApp;
 import com.android.tools.r8.utils.CfgPrinter;
@@ -245,8 +246,16 @@
 
       if (appInfo.withLiveness() != null) {
         // No-op until class merger is added.
-        appInfo = appInfo.withLiveness().rewrittenWithLense(graphLense);
         graphLense = new MemberRebindingAnalysis(appInfo.withLiveness(), graphLense).run();
+        // Class merging requires inlining.
+        if (options.inlineAccessors) {
+          timing.begin("ClassMerger");
+          graphLense = new SimpleClassMerger(application, appInfo.withLiveness(), graphLense,
+              timing).run();
+          timing.end();
+        }
+        appInfo = appInfo.withLiveness().prunedCopyFrom(application);
+        appInfo = appInfo.withLiveness().rewrittenWithLense(graphLense);
       }
 
       graphLense = new BridgeMethodAnalysis(graphLense, appInfo.withSubtyping()).run();
diff --git a/src/main/java/com/android/tools/r8/graph/AppInfo.java b/src/main/java/com/android/tools/r8/graph/AppInfo.java
index f5f22e7..63185d1 100644
--- a/src/main/java/com/android/tools/r8/graph/AppInfo.java
+++ b/src/main/java/com/android/tools/r8/graph/AppInfo.java
@@ -334,4 +334,17 @@
   public AppInfoWithLiveness withLiveness() {
     return null;
   }
+
+  public List<DexClass> getSuperTypeClasses(DexType type) {
+    List<DexClass> result = new ArrayList<>();
+    do {
+      DexClass clazz = definitionFor(type);
+      if (clazz == null) {
+        break;
+      }
+      result.add(clazz);
+      type = clazz.superType;
+    } while (type != null);
+    return result;
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/graph/DexAccessFlags.java b/src/main/java/com/android/tools/r8/graph/DexAccessFlags.java
index e145158..f409c4a 100644
--- a/src/main/java/com/android/tools/r8/graph/DexAccessFlags.java
+++ b/src/main/java/com/android/tools/r8/graph/DexAccessFlags.java
@@ -79,6 +79,10 @@
     set(Constants.ACC_PUBLIC);
   }
 
+  public void unsetPublic() {
+    unset(Constants.ACC_PUBLIC);
+  }
+
   public boolean isPrivate() {
     return isSet(Constants.ACC_PRIVATE);
   }
@@ -99,6 +103,10 @@
     set(Constants.ACC_PROTECTED);
   }
 
+  public void unsetProtected() {
+    unset(Constants.ACC_PROTECTED);
+  }
+
   public boolean isStatic() {
     return isSet(Constants.ACC_STATIC);
   }
@@ -115,6 +123,10 @@
     set(Constants.ACC_FINAL);
   }
 
+  public void unsetFinal() {
+    unset(Constants.ACC_FINAL);
+  }
+
   public boolean isSynchronized() {
     return isSet(Constants.ACC_SYNCHRONIZED);
   }
@@ -239,6 +251,10 @@
     set(Constants.ACC_CONSTRUCTOR);
   }
 
+  public void unsetConstructor() {
+    unset(Constants.ACC_CONSTRUCTOR);
+  }
+
   public boolean isDeclaredSynchronized() {
     return isSet(Constants.ACC_DECLARED_SYNCHRONIZED);
   }
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 232019c..90828b7 100644
--- a/src/main/java/com/android/tools/r8/graph/DexClass.java
+++ b/src/main/java/com/android/tools/r8/graph/DexClass.java
@@ -11,7 +11,9 @@
 import com.google.common.base.MoreObjects;
 
 public abstract class DexClass extends DexItem implements DexClassPromise {
+
   public interface Factory {
+
     DexClass create(DexType type, Origin origin, DexAccessFlags accessFlags, DexType superType,
         DexTypeList interfaces, DexString sourceFile, DexAnnotationSet annotations,
         DexEncodedField[] staticFields, DexEncodedField[] instanceFields,
@@ -28,8 +30,8 @@
   public final Origin origin;
   public final DexType type;
   public final DexAccessFlags accessFlags;
-  public final DexType superType;
-  public final DexTypeList interfaces;
+  public DexType superType;
+  public DexTypeList interfaces;
   public final DexString sourceFile;
   public DexEncodedField[] staticFields;
   public DexEncodedField[] instanceFields;
@@ -156,9 +158,9 @@
     return null;
   }
 
-  public DexEncodedMethod getClassInitializer(DexItemFactory factory) {
+  public DexEncodedMethod getClassInitializer() {
     for (DexEncodedMethod method : directMethods()) {
-      if (factory.isClassConstructor(method.method)) {
+      if (method.accessFlags.isConstructor() && method.accessFlags.isStatic()) {
         return method;
       }
     }
@@ -192,4 +194,8 @@
     }
     throw new Unreachable();
   }
+
+  public boolean hasClassInitializer() {
+    return getClassInitializer() != null;
+  }
 }
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 06add73..c94fc3c 100644
--- a/src/main/java/com/android/tools/r8/graph/DexEncodedField.java
+++ b/src/main/java/com/android/tools/r8/graph/DexEncodedField.java
@@ -71,9 +71,20 @@
     if (accessFlags.isStatic() && accessFlags.isPublic() && accessFlags.isFinal()) {
       DexClass clazz = appInfo.definitionFor(field.getHolder());
       assert clazz != null : "Class for the field must be present";
-      return staticValue.asConstInstruction(
-          clazz.getClassInitializer(appInfo.dexItemFactory) != null, dest);
+      return staticValue.asConstInstruction(clazz.hasClassInitializer(), dest);
     }
     return null;
   }
+
+  public DexEncodedField toRenamedField(DexString name, DexItemFactory dexItemFactory) {
+    return new DexEncodedField(dexItemFactory.createField(field.clazz, field.type, name),
+        accessFlags, annotations, staticValue);
+  }
+
+  public DexEncodedField toTypeSubstitutedField(DexField field) {
+    if (this.field == field) {
+      return this;
+    }
+    return new DexEncodedField(field, accessFlags, annotations, staticValue);
+  }
 }
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 9244be5..5ea8edd 100644
--- a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
+++ b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
@@ -26,7 +26,9 @@
 
 public class DexEncodedMethod extends KeyedDexItem<DexMethod> {
 
-  public enum CompilationState {
+  public enum CompilationState
+
+  {
     NOT_PROCESSED,
     PROCESSED_NOT_INLINING_CANDIDATE,
     // Code only contains instructions that access public entities.
@@ -56,6 +58,7 @@
     this.annotations = annotations;
     this.parameterAnnotations = parameterAnnotations;
     this.code = code;
+    assert code == null || !accessFlags.isAbstract();
   }
 
   public boolean isProcessed() {
@@ -67,10 +70,10 @@
       // This will probably never happen but never inline a class initializer.
       return false;
     }
-    if (alwaysInline && (compilationState != CompilationState.NOT_PROCESSED)) {
+    if (alwaysInline) {
       // Only inline constructor iff holder classes are equal.
       if (!accessFlags.isStatic() && accessFlags.isConstructor()) {
-         return container.method.getHolder() == method.getHolder();
+        return container.method.getHolder() == method.getHolder();
       }
       return true;
     }
@@ -78,7 +81,7 @@
       case PROCESSED_INLINING_CANDIDATE_PUBLIC:
         return true;
       case PROCESSED_INLINING_CANDIDATE_PACKAGE_PRIVATE:
-         return container.method.getHolder().isSamePackage(method.getHolder());
+        return container.method.getHolder().isSamePackage(method.getHolder());
       // TODO(bak): Expand check for package private access:
       case PROCESSED_INLINING_CANDIDATE_PRIVATE:
         return container.method.getHolder() == method.getHolder();
@@ -232,12 +235,15 @@
 
   public DexEncodedMethod toEmptyThrowingMethod() {
     Instruction insn[] = {new Const(0, 0), new Throw(0)};
-    code = generateCodeFromTemplate(1, 0, insn);
-    return this;
+    DexCode code = generateCodeFromTemplate(1, 0, insn);
+    assert !accessFlags.isAbstract();
+    Builder builder = builder(this);
+    builder.setCode(code);
+    return builder.build();
   }
 
   public DexEncodedMethod toMethodThatLogsError(DexItemFactory itemFactory) {
-    Signature signature = MethodSignature.fromDexMethod(this.method);
+    Signature signature = MethodSignature.fromDexMethod(method);
     // TODO(herhut): Construct this out of parts to enable reuse, maybe even using descriptors.
     DexString message = itemFactory.createString(
         "Shaking error: Missing method in " + method.holder.toSourceString() + ": "
@@ -263,8 +269,29 @@
         new InvokeStatic(2, initMethod, 0, 1, 0, 0, 0),
         new Throw(0)
     };
-    code = generateCodeFromTemplate(2, 2, insn);
-    return this;
+    DexCode code = generateCodeFromTemplate(2, 2, insn);
+    Builder builder = builder(this);
+    builder.setCode(code);
+    return builder.build();
+  }
+
+  public DexEncodedMethod toTypeSubstitutedMethod(DexMethod method) {
+    if (this.method == method) {
+      return this;
+    }
+    Builder builder = builder(this);
+    builder.setMethod(method);
+    return builder.build();
+  }
+
+  public DexEncodedMethod toRenamedMethod(DexString name, DexItemFactory factory) {
+    if (method.name == name) {
+      return this;
+    }
+    DexMethod newMethod = factory.createMethod(method.holder, method.proto, name);
+    Builder builder = builder(this);
+    builder.setMethod(newMethod);
+    return builder.build();
   }
 
   public String codeToString() {
@@ -290,6 +317,7 @@
   }
 
   public static class OptimizationInfo {
+
     private int returnedArgument = -1;
     private boolean neverReturnsNull = false;
     private boolean returnsConstant = false;
@@ -300,6 +328,14 @@
       // Intentionally left empty.
     }
 
+    private OptimizationInfo(OptimizationInfo template) {
+      returnedArgument = template.returnedArgument;
+      neverReturnsNull = template.neverReturnsNull;
+      returnsConstant = template.returnsConstant;
+      returnedConstant = template.returnedConstant;
+      forceInline = template.forceInline;
+    }
+
     public boolean returnsArgument() {
       return returnedArgument != -1;
     }
@@ -345,12 +381,23 @@
     private void markForceInline() {
       forceInline = true;
     }
+
+    public OptimizationInfo copy() {
+      return new OptimizationInfo(this);
+    }
   }
 
   private static class DefaultOptimizationInfo extends OptimizationInfo {
-    public static final OptimizationInfo DEFAULT = new DefaultOptimizationInfo();
 
-    private DefaultOptimizationInfo() {}
+    static final OptimizationInfo DEFAULT = new DefaultOptimizationInfo();
+
+    private DefaultOptimizationInfo() {
+    }
+
+    @Override
+    public OptimizationInfo copy() {
+      return this;
+    }
   }
 
   synchronized private OptimizationInfo ensureMutableOI() {
@@ -379,4 +426,62 @@
   public OptimizationInfo getOptimizationInfo() {
     return optimizationInfo;
   }
+
+  private static Builder builder(DexEncodedMethod from) {
+    return new Builder(from);
+  }
+
+  private static class Builder {
+
+    private DexMethod method;
+    private DexAccessFlags accessFlags;
+    private DexAnnotationSet annotations;
+    private DexAnnotationSetRefList parameterAnnotations;
+    private Code code;
+    private CompilationState compilationState = CompilationState.NOT_PROCESSED;
+    private OptimizationInfo optimizationInfo = DefaultOptimizationInfo.DEFAULT;
+
+    private Builder(DexEncodedMethod from) {
+      // Copy all the mutable state of a DexEncodedMethod here.
+      method = from.method;
+      accessFlags = new DexAccessFlags(from.accessFlags.get());
+      annotations = from.annotations;
+      parameterAnnotations = from.parameterAnnotations;
+      code = from.code;
+      compilationState = from.compilationState;
+      optimizationInfo = from.optimizationInfo.copy();
+    }
+
+    public void setMethod(DexMethod method) {
+      this.method = method;
+    }
+
+    public void setAccessFlags(DexAccessFlags accessFlags) {
+      this.accessFlags = accessFlags;
+    }
+
+    public void setAnnotations(DexAnnotationSet annotations) {
+      this.annotations = annotations;
+    }
+
+    public void setParameterAnnotations(DexAnnotationSetRefList parameterAnnotations) {
+      this.parameterAnnotations = parameterAnnotations;
+    }
+
+    public void setCode(Code code) {
+      this.code = code;
+    }
+
+    public DexEncodedMethod build() {
+      assert method != null;
+      assert accessFlags != null;
+      assert annotations != null;
+      assert parameterAnnotations != null;
+      DexEncodedMethod result =
+          new DexEncodedMethod(method, accessFlags, annotations, parameterAnnotations, code);
+      result.compilationState = compilationState;
+      result.optimizationInfo = optimizationInfo;
+      return result;
+    }
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/graph/DexLibraryClass.java b/src/main/java/com/android/tools/r8/graph/DexLibraryClass.java
index f0ca9b5..c4ed702 100644
--- a/src/main/java/com/android/tools/r8/graph/DexLibraryClass.java
+++ b/src/main/java/com/android/tools/r8/graph/DexLibraryClass.java
@@ -28,6 +28,11 @@
   }
 
   @Override
+  public String toSourceString() {
+    return type.toSourceString() + "(library class)";
+  }
+
+  @Override
   public void addDependencies(MixedSectionCollection collector) {
     // Should never happen but does not harm.
     assert false;
diff --git a/src/main/java/com/android/tools/r8/graph/DexProgramClass.java b/src/main/java/com/android/tools/r8/graph/DexProgramClass.java
index 2fc73bc..368cb22 100644
--- a/src/main/java/com/android/tools/r8/graph/DexProgramClass.java
+++ b/src/main/java/com/android/tools/r8/graph/DexProgramClass.java
@@ -76,6 +76,11 @@
   }
 
   @Override
+  public String toSourceString() {
+    return type.toSourceString();
+  }
+
+  @Override
   public boolean isProgramClass() {
     return true;
   }
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 1b70497..234773f 100644
--- a/src/main/java/com/android/tools/r8/graph/DexType.java
+++ b/src/main/java/com/android/tools/r8/graph/DexType.java
@@ -8,6 +8,7 @@
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.utils.DescriptorUtils;
 import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Iterables;
 import com.google.common.collect.Sets;
 import java.util.ArrayDeque;
 import java.util.Arrays;
@@ -29,7 +30,6 @@
   public final DexString descriptor;
   private String toStringCache = null;
   private int hierarchyLevel = UNKNOWN_LEVEL;
-
   private Set<DexType> directSubtypes = NO_DIRECT_SUBTYPE;
 
   DexType(DexString descriptor) {
@@ -340,11 +340,16 @@
     }
   }
 
-  public DexType toBaseType(DexItemFactory dexItemFactory) {
+  private int getNumberOfLeadingSquareBrackets() {
     int leadingSquareBrackets = 0;
     while (descriptor.content[leadingSquareBrackets] == '[') {
       leadingSquareBrackets++;
     }
+    return leadingSquareBrackets;
+  }
+
+  public DexType toBaseType(DexItemFactory dexItemFactory) {
+    int leadingSquareBrackets = getNumberOfLeadingSquareBrackets();
     if (leadingSquareBrackets == 0) {
       return this;
     }
@@ -353,6 +358,20 @@
     return dexItemFactory.createType(newDesc);
   }
 
+  public DexType replaceBaseType(DexType newBase, DexItemFactory dexItemFactory) {
+    assert this.isArrayType();
+    assert !newBase.isArrayType();
+    int leadingSquareBrackets = getNumberOfLeadingSquareBrackets();
+    byte[] content = new byte[newBase.descriptor.content.length + leadingSquareBrackets];
+    Arrays.fill(content, 0, leadingSquareBrackets, (byte) '[');
+    for (int i = 0; i < newBase.descriptor.content.length; i++) {
+      content[leadingSquareBrackets + i] = newBase.descriptor.content[i];
+    }
+    DexString newDesc = dexItemFactory
+        .createString(newBase.descriptor.size + leadingSquareBrackets, content);
+    return dexItemFactory.createType(newDesc);
+  }
+
   public DexType toArrayElementType(DexItemFactory dexItemFactory) {
     assert this.isArrayType();
     DexString newDesc = dexItemFactory.createString(descriptor.size - 1,
@@ -411,6 +430,15 @@
     }
   }
 
+  public DexType getSingleSubtype() {
+    assert hierarchyLevel != UNKNOWN_LEVEL;
+    if (directSubtypes.size() == 1) {
+      return Iterables.getFirst(directSubtypes, null);
+    } else {
+      return null;
+    }
+  }
+
   public String getPackageDescriptor() {
     return getPackageOrName(true);
   }
diff --git a/src/main/java/com/android/tools/r8/graph/GraphLense.java b/src/main/java/com/android/tools/r8/graph/GraphLense.java
index 42f7c6e..e6c2d00 100644
--- a/src/main/java/com/android/tools/r8/graph/GraphLense.java
+++ b/src/main/java/com/android/tools/r8/graph/GraphLense.java
@@ -10,6 +10,10 @@
 
   public static class Builder {
 
+    private Builder() {
+
+    }
+
     private final Map<DexType, DexType> typeMap = new IdentityHashMap<>();
     private final Map<DexMethod, DexMethod> methodMap = new IdentityHashMap<>();
     private final Map<DexField, DexField> fieldMap = new IdentityHashMap<>();
@@ -26,16 +30,20 @@
       fieldMap.put(from, to);
     }
 
-    public GraphLense build() {
-      return build(new IdentityGraphLense());
+    public GraphLense build(DexItemFactory dexItemFactory) {
+      return build(new IdentityGraphLense(), dexItemFactory);
     }
 
-    public GraphLense build(GraphLense previousLense) {
-      return new NestedGraphLense(typeMap, methodMap, fieldMap, previousLense);
+    public GraphLense build(GraphLense previousLense, DexItemFactory dexItemFactory) {
+      return new NestedGraphLense(typeMap, methodMap, fieldMap, previousLense, dexItemFactory);
     }
 
   }
 
+  public static Builder builder() {
+    return new Builder();
+  }
+
   public abstract DexType lookupType(DexType type, DexEncodedMethod context);
 
   public abstract DexMethod lookupMethod(DexMethod method, DexEncodedMethod context);
@@ -78,21 +86,38 @@
   private static class NestedGraphLense extends GraphLense {
 
     private final GraphLense previousLense;
+    private final DexItemFactory dexItemFactory;
 
     private final Map<DexType, DexType> typeMap;
+    private final Map<DexType, DexType> arrayTypeCache = new IdentityHashMap<>();
     private final Map<DexMethod, DexMethod> methodMap;
     private final Map<DexField, DexField> fieldMap;
 
     private NestedGraphLense(Map<DexType, DexType> typeMap, Map<DexMethod, DexMethod> methodMap,
-        Map<DexField, DexField> fieldMap, GraphLense previousLense) {
+        Map<DexField, DexField> fieldMap, GraphLense previousLense, DexItemFactory dexItemFactory) {
       this.typeMap = typeMap;
       this.methodMap = methodMap;
       this.fieldMap = fieldMap;
       this.previousLense = previousLense;
+      this.dexItemFactory = dexItemFactory;
     }
 
     @Override
     public DexType lookupType(DexType type, DexEncodedMethod context) {
+      if (type.isArrayType()) {
+        DexType result = arrayTypeCache.get(type);
+        if (result == null) {
+          DexType baseType = type.toBaseType(dexItemFactory);
+          DexType newType = lookupType(baseType, context);
+          if (baseType == newType) {
+            result = type;
+          } else {
+            result = type.replaceBaseType(newType, dexItemFactory);
+          }
+          arrayTypeCache.put(type, result);
+        }
+        return result;
+      }
       DexType previous = previousLense.lookupType(type, context);
       return typeMap.getOrDefault(previous, previous);
     }
diff --git a/src/main/java/com/android/tools/r8/graph/JarCode.java b/src/main/java/com/android/tools/r8/graph/JarCode.java
index b40f6ef..2766684 100644
--- a/src/main/java/com/android/tools/r8/graph/JarCode.java
+++ b/src/main/java/com/android/tools/r8/graph/JarCode.java
@@ -4,6 +4,7 @@
 package com.android.tools.r8.graph;
 
 import com.android.tools.r8.ir.code.IRCode;
+import com.android.tools.r8.ir.code.ValueNumberGenerator;
 import com.android.tools.r8.ir.conversion.IRBuilder;
 import com.android.tools.r8.ir.conversion.JarSourceCode;
 import com.android.tools.r8.jar.JarRegisterEffectsVisitor;
@@ -79,13 +80,21 @@
 
   @Override
   public IRCode buildIR(DexEncodedMethod encodedMethod, InternalOptions options) {
-    assert clazz == encodedMethod.method.getHolder();
     triggerDelayedParsingIfNeccessary();
     JarSourceCode source = new JarSourceCode(clazz, node, application);
     IRBuilder builder = new IRBuilder(encodedMethod, source, options);
     return builder.build();
   }
 
+  public IRCode buildIR(DexEncodedMethod encodedMethod, ValueNumberGenerator generator,
+      InternalOptions options) {
+    triggerDelayedParsingIfNeccessary();
+    JarSourceCode source = new JarSourceCode(clazz, node, application);
+    IRBuilder builder = new IRBuilder(encodedMethod, source, generator, options);
+    return builder.build();
+  }
+
+
   @Override
   public void registerReachableDefinitions(UseRegistry registry) {
     triggerDelayedParsingIfNeccessary();
diff --git a/src/main/java/com/android/tools/r8/ir/code/CheckCast.java b/src/main/java/com/android/tools/r8/ir/code/CheckCast.java
index 7963357..573db67 100644
--- a/src/main/java/com/android/tools/r8/ir/code/CheckCast.java
+++ b/src/main/java/com/android/tools/r8/ir/code/CheckCast.java
@@ -26,6 +26,14 @@
     this.type = type;
   }
 
+  public DexType getType() {
+    return type;
+  }
+
+  public Value object() {
+    return inValues().get(0);
+  }
+
   @Override
   public void buildDex(DexBuilder builder) {
     // The check cast instruction in dex doesn't write a new register. Therefore,
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java b/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java
index 1576190..12f0aa2 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java
@@ -219,7 +219,6 @@
     this.options = options;
   }
 
-
   private void addToWorklist(BasicBlock block, int firstInstructionIndex) {
     // TODO(ager): Filter out the ones that are already in the worklist, mark bit in block?
     if (!block.isFilled()) {
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 b01fad8..d4b03e3 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
@@ -114,7 +114,7 @@
     this.codeRewriter = new CodeRewriter(appInfo);
     this.outliner = new Outliner(appInfo, options);
     this.memberValuePropagation = new MemberValuePropagation(appInfo);
-    this.inliner = new Inliner(appInfo, options);
+    this.inliner = new Inliner(appInfo, graphLense, options);
     this.lambdaRewriter = new LambdaRewriter(this);
     this.interfaceMethodRewriter = enableInterfaceMethodDesugaring()
         ? new InterfaceMethodRewriter(this) : null;
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/LensCodeRewriter.java b/src/main/java/com/android/tools/r8/ir/conversion/LensCodeRewriter.java
index 13507ab..2d5d803 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/LensCodeRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/LensCodeRewriter.java
@@ -17,8 +17,10 @@
 import com.android.tools.r8.graph.GraphLense;
 import com.android.tools.r8.ir.code.BasicBlock;
 import com.android.tools.r8.ir.code.CheckCast;
+import com.android.tools.r8.ir.code.ConstClass;
 import com.android.tools.r8.ir.code.IRCode;
 import com.android.tools.r8.ir.code.InstanceGet;
+import com.android.tools.r8.ir.code.InstanceOf;
 import com.android.tools.r8.ir.code.InstancePut;
 import com.android.tools.r8.ir.code.Instruction;
 import com.android.tools.r8.ir.code.InstructionListIterator;
@@ -26,6 +28,8 @@
 import com.android.tools.r8.ir.code.Invoke.Type;
 import com.android.tools.r8.ir.code.InvokeCustom;
 import com.android.tools.r8.ir.code.InvokeMethod;
+import com.android.tools.r8.ir.code.InvokeNewArray;
+import com.android.tools.r8.ir.code.NewArrayEmpty;
 import com.android.tools.r8.ir.code.StaticGet;
 import com.android.tools.r8.ir.code.StaticPut;
 import com.android.tools.r8.ir.code.Value;
@@ -43,6 +47,14 @@
     this.appInfo = appInfo;
   }
 
+  private Value makeOutValue(Instruction insn, IRCode code) {
+    if (insn.outValue() == null) {
+      return null;
+    } else {
+      return new Value(code.valueNumberGenerator.next(), -1, insn.outType(), insn.getDebugInfo());
+    }
+  }
+
   /**
    * Replace invoke targets and field accesses with actual definitions.
    */
@@ -84,9 +96,10 @@
             continue;
           }
           DexMethod actualTarget = graphLense.lookupMethod(invokedMethod, method);
-          if (actualTarget != invokedMethod) {
+          Invoke.Type invokeType = getInvokeType(invoke, actualTarget);
+          if (actualTarget != invokedMethod || invoke.getType() != invokeType) {
             Invoke newInvoke = Invoke
-                .create(getInvokeType(invoke, actualTarget), actualTarget, null,
+                .create(invokeType, actualTarget, null,
                     invoke.outValue(), invoke.inValues());
             iterator.replaceCurrentInstruction(newInvoke);
             // Fix up the return type if needed.
@@ -98,7 +111,7 @@
               CheckCast cast = new CheckCast(
                   newValue,
                   newInvoke.outValue(),
-                  invokedMethod.proto.returnType);
+                  graphLense.lookupType(invokedMethod.proto.returnType, method));
               iterator.add(cast);
               // If the current block has catch handlers split the check cast into its own block.
               if (newInvoke.getBlock().hasCatchHandlers()) {
@@ -144,6 +157,45 @@
                 new StaticPut(staticPut.getType(), staticPut.inValue(), actualField);
             iterator.replaceCurrentInstruction(newStaticPut);
           }
+        } else if (current.isCheckCast()) {
+          CheckCast checkCast = current.asCheckCast();
+          DexType newType = graphLense.lookupType(checkCast.getType(), method);
+          if (newType != checkCast.getType()) {
+            CheckCast newCheckCast =
+                new CheckCast(makeOutValue(checkCast, code), checkCast.object(), newType);
+            iterator.replaceCurrentInstruction(newCheckCast);
+          }
+        } else if (current.isConstClass()) {
+          ConstClass constClass = current.asConstClass();
+          DexType newType = graphLense.lookupType(constClass.getValue(), method);
+          if (newType != constClass.getValue()) {
+            ConstClass newConstClass = new ConstClass(makeOutValue(constClass, code), newType);
+            iterator.replaceCurrentInstruction(newConstClass);
+          }
+        } else if (current.isInstanceOf()) {
+          InstanceOf instanceOf = current.asInstanceOf();
+          DexType newType = graphLense.lookupType(instanceOf.type(), method);
+          if (newType != instanceOf.type()) {
+            InstanceOf newInstanceOf = new InstanceOf(makeOutValue(instanceOf, code),
+                instanceOf.value(), newType);
+            iterator.replaceCurrentInstruction(newInstanceOf);
+          }
+        } else if (current.isInvokeNewArray()) {
+          InvokeNewArray newArray = current.asInvokeNewArray();
+          DexType newType = graphLense.lookupType(newArray.getArrayType(), method);
+          if (newType != newArray.getArrayType()) {
+            InvokeNewArray newNewArray = new InvokeNewArray(newType, makeOutValue(newArray, code),
+                newArray.inValues());
+            iterator.replaceCurrentInstruction(newNewArray);
+          }
+        } else if (current.isNewArrayEmpty()) {
+          NewArrayEmpty newArrayEmpty = current.asNewArrayEmpty();
+          DexType newType = graphLense.lookupType(newArrayEmpty.type, method);
+          if (newType != newArrayEmpty.type) {
+            NewArrayEmpty newNewArray = new NewArrayEmpty(makeOutValue(newArrayEmpty, code),
+                newArrayEmpty.size(), newType);
+            iterator.replaceCurrentInstruction(newNewArray);
+          }
         }
       }
     }
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 ef7fe72..dc2ed67 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
@@ -7,6 +7,7 @@
 import com.android.tools.r8.graph.DexCode;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.GraphLense;
 import com.android.tools.r8.ir.code.BasicBlock;
 import com.android.tools.r8.ir.code.DominatorTree;
 import com.android.tools.r8.ir.code.IRCode;
@@ -18,6 +19,8 @@
 import com.android.tools.r8.ir.code.Value;
 import com.android.tools.r8.ir.code.ValueNumberGenerator;
 import com.android.tools.r8.ir.conversion.CallGraph;
+import com.android.tools.r8.ir.conversion.LensCodeRewriter;
+import com.android.tools.r8.logging.Log;
 import com.android.tools.r8.utils.InternalOptions;
 import com.google.common.collect.Sets;
 import java.util.ArrayList;
@@ -32,6 +35,7 @@
   private static final int INLINING_INSTRUCTION_LIMIT = 5;
 
   protected final AppInfoWithSubtyping appInfo;
+  private final GraphLense graphLense;
   private final InternalOptions options;
 
   // State for inlining methods which are known to be called twice.
@@ -40,9 +44,9 @@
   public final Set<DexEncodedMethod> doubleInlineSelectedTargets = Sets.newIdentityHashSet();
   public final Map<DexEncodedMethod, DexEncodedMethod> doubleInlineeCandidates = new HashMap<>();
 
-  public Inliner(
-      AppInfoWithSubtyping appInfo, InternalOptions options) {
+  public Inliner(AppInfoWithSubtyping appInfo, GraphLense graphLense, InternalOptions options) {
     this.appInfo = appInfo;
+    this.graphLense = graphLense;
     this.options = options;
   }
 
@@ -110,6 +114,7 @@
   }
 
   static public class InlineAction {
+
     public final DexEncodedMethod target;
     public final Invoke invoke;
     public final boolean forceInline;
@@ -127,14 +132,21 @@
       this.forceInline = target.getOptimizationInfo().forceInline();
     }
 
-    public IRCode buildIR(ValueNumberGenerator generator, InternalOptions options) {
-      assert target.isProcessed();
-      assert target.getCode().isDexCode();
-      return target.buildIR(generator, options);
+    public IRCode buildIR(ValueNumberGenerator generator, AppInfoWithSubtyping appInfo,
+        GraphLense graphLense, InternalOptions options) {
+      if (target.isProcessed()) {
+        assert target.getCode().isDexCode();
+        return target.buildIR(generator, options);
+      } else {
+        assert target.getCode().isJarCode();
+        IRCode code = target.getCode().asJarCode().buildIR(target, generator, options);
+        new LensCodeRewriter(graphLense, appInfo).rewrite(code, target);
+        return code;
+      }
     }
   }
 
- private int numberOfInstructions(IRCode code) {
+  private int numberOfInstructions(IRCode code) {
     int numOfInstructions = 0;
     for (BasicBlock block : code.blocks) {
       numOfInstructions += block.getInstructions().size();
@@ -167,7 +179,9 @@
     while (iterator.hasNext()) {
       instruction = iterator.next();
       if (instruction.inValues().contains(unInitializedObject)) {
-        return instruction.isInvokeDirect();
+        return instruction.isInvokeDirect()
+            && appInfo.dexItemFactory
+            .isConstructor(instruction.asInvokeDirect().getInvokedMethod());
       }
     }
     assert false : "Execution should never reach this point";
@@ -208,14 +222,30 @@
           InvokeMethod invoke = current.asInvokeMethod();
           InlineAction result = invoke.computeInlining(oracle);
           if (result != null) {
-            IRCode inlinee = result.buildIR(code.valueNumberGenerator, options);
+            DexEncodedMethod target = appInfo.lookup(invoke.getType(), invoke.getInvokedMethod());
+            assert target != null;
+            boolean forceInline = target.getOptimizationInfo().forceInline();
+            if (!target.isProcessed() && !forceInline) {
+              // Do not inline code that was not processed unless we have to force inline.
+              continue;
+            }
+            IRCode inlinee = result
+                .buildIR(code.valueNumberGenerator, appInfo, graphLense, options);
             if (inlinee != null) {
               // TODO(sgjesse): Get rid of this additional check by improved inlining.
               if (block.hasCatchHandlers() && inlinee.getNormalExitBlock() == null) {
                 continue;
               }
+              // If this code did not go through the full pipeline, apply inlining to make sure
+              // that force inline targets get processed.
+              if (!target.isProcessed()) {
+                assert forceInline;
+                if (Log.ENABLED) {
+                  Log.verbose(getClass(), "Forcing extra inline on " + target.toSourceString());
+                }
+                performInlining(target, inlinee, callGraph);
+              }
               // Make sure constructor inlining is legal.
-              DexEncodedMethod target = appInfo.lookup(invoke.getType(), invoke.getInvokedMethod());
               if (target.accessFlags.isConstructor() && !legalConstructorInline(method, inlinee)) {
                 continue;
               }
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/InliningOracle.java b/src/main/java/com/android/tools/r8/ir/optimize/InliningOracle.java
index fa55f1c..954f11c 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/InliningOracle.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/InliningOracle.java
@@ -20,10 +20,11 @@
 import com.android.tools.r8.logging.Log;
 
 /**
- *  The InliningOracle contains information needed for when inlining
- *  other methods into @method.
+ * The InliningOracle contains information needed for when inlining
+ * other methods into @method.
  */
 public class InliningOracle {
+
   final Inliner inliner;
   final DexEncodedMethod method;
   final Value receiver;
@@ -208,7 +209,7 @@
       return true;
     }
     DexClass clazz = inliner.appInfo.definitionFor(targetHolder);
-    return (clazz != null) && (clazz.getClassInitializer(inliner.appInfo.dexItemFactory) == null);
+    return (clazz != null) && (!clazz.hasClassInitializer());
   }
 
   private boolean isDoubleInliningTarget(DexEncodedMethod candidate) {
diff --git a/src/main/java/com/android/tools/r8/naming/Minifier.java b/src/main/java/com/android/tools/r8/naming/Minifier.java
index 18099fb..9e81102 100644
--- a/src/main/java/com/android/tools/r8/naming/Minifier.java
+++ b/src/main/java/com/android/tools/r8/naming/Minifier.java
@@ -42,7 +42,7 @@
     timing.begin("MinifyClasses");
     Map<DexType, DexString> classRenaming =
         new ClassNameMinifier(
-                appInfo, rootSet, options.packagePrefix, options.classObfuscationDictionary)
+            appInfo, rootSet, options.packagePrefix, options.classObfuscationDictionary)
             .computeRenaming();
     timing.end();
     timing.begin("MinifyMethods");
diff --git a/src/main/java/com/android/tools/r8/optimize/InvokeSingleTargetExtractor.java b/src/main/java/com/android/tools/r8/optimize/InvokeSingleTargetExtractor.java
index 61b270d..8dc8a73 100644
--- a/src/main/java/com/android/tools/r8/optimize/InvokeSingleTargetExtractor.java
+++ b/src/main/java/com/android/tools/r8/optimize/InvokeSingleTargetExtractor.java
@@ -8,11 +8,11 @@
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.UseRegistry;
 
-class InvokeSingleTargetExtractor extends UseRegistry {
+public class InvokeSingleTargetExtractor extends UseRegistry {
   private InvokeKind kind = InvokeKind.NONE;
   private DexMethod target;
 
-  InvokeSingleTargetExtractor() {
+  public InvokeSingleTargetExtractor() {
   }
 
   private boolean setTarget(DexMethod target, InvokeKind kind) {
diff --git a/src/main/java/com/android/tools/r8/optimize/MemberRebindingAnalysis.java b/src/main/java/com/android/tools/r8/optimize/MemberRebindingAnalysis.java
index 1e4c51b..4e68d0f 100644
--- a/src/main/java/com/android/tools/r8/optimize/MemberRebindingAnalysis.java
+++ b/src/main/java/com/android/tools/r8/optimize/MemberRebindingAnalysis.java
@@ -20,7 +20,7 @@
 public class MemberRebindingAnalysis {
   private final AppInfoWithLiveness appInfo;
   private final GraphLense lense;
-  private final GraphLense.Builder builder = new GraphLense.Builder();
+  private final GraphLense.Builder builder = GraphLense.builder();
 
   public MemberRebindingAnalysis(AppInfoWithLiveness appInfo, GraphLense lense) {
     assert lense.isContextFree();
@@ -150,6 +150,6 @@
         appInfo::lookupStaticTarget, DexClass::findStaticTarget);
     computeFieldRebinding(Sets.union(appInfo.instanceFieldsRead, appInfo.instanceFieldsWritten),
         appInfo::lookupInstanceTarget, DexClass::findInstanceTarget);
-    return builder.build(lense);
+    return builder.build(lense, appInfo.dexItemFactory);
   }
 }
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 07e641a..6fb9d2e 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -349,7 +349,7 @@
       }
       // We also need to add the corresponding <clinit> to the set of live methods, as otherwise
       // static field initialization (and other class-load-time sideeffects) will not happen.
-      DexEncodedMethod clinit = holder.getClassInitializer(appInfo.dexItemFactory);
+      DexEncodedMethod clinit = holder.getClassInitializer();
       if (clinit != null) {
         markDirectStaticOrConstructorMethodAsLive(clinit, KeepReason.reachableFromLiveType(type));
       }
diff --git a/src/main/java/com/android/tools/r8/shaking/SimpleClassMerger.java b/src/main/java/com/android/tools/r8/shaking/SimpleClassMerger.java
new file mode 100644
index 0000000..bc43ae8
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/shaking/SimpleClassMerger.java
@@ -0,0 +1,624 @@
+// Copyright (c) 2017, 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;
+
+import com.android.tools.r8.errors.CompilationError;
+import com.android.tools.r8.graph.DexApplication;
+import com.android.tools.r8.graph.DexClass;
+import com.android.tools.r8.graph.DexEncodedField;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexField;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.graph.DexProto;
+import com.android.tools.r8.graph.DexString;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.DexTypeList;
+import com.android.tools.r8.graph.GraphLense;
+import com.android.tools.r8.graph.GraphLense.Builder;
+import com.android.tools.r8.graph.KeyedDexItem;
+import com.android.tools.r8.graph.PresortedComparable;
+import com.android.tools.r8.logging.Log;
+import com.android.tools.r8.optimize.InvokeSingleTargetExtractor;
+import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
+import com.android.tools.r8.utils.FieldSignatureEquivalence;
+import com.android.tools.r8.utils.HashMapInt;
+import com.android.tools.r8.utils.IdentityHashMapInt;
+import com.android.tools.r8.utils.IntIntHashMap;
+import com.android.tools.r8.utils.MethodSignatureEquivalence;
+import com.android.tools.r8.utils.Timing;
+import com.google.common.base.Equivalence;
+import com.google.common.base.Equivalence.Wrapper;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Iterators;
+import com.google.common.collect.Sets;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.IdentityHashMap;
+import java.util.Iterator;
+import java.util.LinkedHashSet;
+import java.util.Map;
+import java.util.Set;
+import java.util.function.BiFunction;
+
+/**
+ * Merges Supertypes with a single implementation into their single subtype.
+ * <p>
+ * A common use-case for this is to merge an interface into its single implementation.
+ * <p>
+ * The class merger only fixes the structure of the graph but leaves the actual instructions
+ * untouched. Fixup of instructions is deferred via a {@link GraphLense} to the Ir building phase.
+ */
+public class SimpleClassMerger {
+
+  private final DexApplication application;
+  private final AppInfoWithLiveness appInfo;
+  private final GraphLense graphLense;
+  private final GraphLense.Builder renamedMembersLense = GraphLense.builder();
+  private final Map<DexType, DexType> mergedClasses = new IdentityHashMap<>();
+  private final Timing timing;
+  private Set<DexMethod> invokes;
+  private int numberOfMerges = 0;
+
+  public SimpleClassMerger(DexApplication application, AppInfoWithLiveness appInfo,
+      GraphLense graphLense, Timing timing) {
+    this.application = application;
+    this.appInfo = appInfo;
+    this.graphLense = graphLense;
+    this.timing = timing;
+  }
+
+  private boolean isMergeCandidate(DexProgramClass clazz) {
+    // We can merge program classes if they are not instantiated, have a single subtype
+    // and we do not have to keep them.
+    return !clazz.isLibraryClass()
+        && !appInfo.instantiatedTypes.contains(clazz.type)
+        && !appInfo.pinnedItems.contains(clazz)
+        && clazz.type.getSingleSubtype() != null;
+  }
+
+  private Set<DexMethod> getInvokes() {
+    if (invokes == null) {
+
+      // TODO(herhut): Ignore invokes into the library, as those can only reference library types.
+      invokes = Sets.newIdentityHashSet();
+      invokes.addAll(appInfo.directInvokes);
+      invokes.addAll(appInfo.staticInvokes);
+      invokes.addAll(appInfo.superInvokes);
+      invokes.addAll(appInfo.virtualInvokes);
+      invokes.addAll(appInfo.targetedMethods);
+      invokes.addAll(appInfo.liveMethods);
+      for (DexEncodedMethod method : Iterables
+          .filter(appInfo.pinnedItems, DexEncodedMethod.class)) {
+        invokes.add(method.method);
+      }
+    }
+    return invokes;
+  }
+
+  public GraphLense run() {
+    timing.begin("merge");
+    GraphLense mergingGraphLense = mergeClasses(graphLense);
+    timing.end();
+    timing.begin("fixup");
+    GraphLense result = new TreeFixer().fixupTypeReferences(mergingGraphLense);
+    timing.end();
+    return result;
+  }
+
+  private GraphLense mergeClasses(GraphLense graphLense) {
+    for (DexProgramClass clazz : application.classes()) {
+      if (isMergeCandidate(clazz)) {
+        DexClass targetClass = appInfo.definitionFor(clazz.type.getSingleSubtype());
+        if (appInfo.pinnedItems.contains(targetClass)) {
+          // We have to keep the target class intact, so we cannot merge it.
+          continue;
+        }
+        if (mergedClasses.containsKey(targetClass.type)) {
+          // TODO(herhut): Traverse top-down.
+          continue;
+        }
+        if (clazz.hasClassInitializer() && targetClass.hasClassInitializer()) {
+          // TODO(herhut): Handle class initializers.
+          if (Log.ENABLED) {
+            Log.info(getClass(), "Cannot merge %s into %s due to static initializers.",
+                clazz.toSourceString(), targetClass.toSourceString());
+          }
+          continue;
+        }
+        // Guard against the case where we have two methods that may get the same signature
+        // if we replace types. This is rare, so we approximate and err on the safe side here.
+        if (new CollisionDetector(clazz.type, targetClass.type, getInvokes(), mergedClasses)
+            .mayCollide()) {
+          if (Log.ENABLED) {
+            Log.info(getClass(), "Cannot merge %s into %s due to conflict.", clazz.toSourceString(),
+                targetClass.toSourceString());
+          }
+          continue;
+        }
+        boolean merged = new ClassMerger(clazz, targetClass).merge();
+        if (Log.ENABLED) {
+          if (merged) {
+            numberOfMerges++;
+            Log.info(getClass(), "Merged class %s into %s.", clazz.toSourceString(),
+                targetClass.toSourceString());
+          } else {
+            Log.info(getClass(), "Aborted merge for class %s into %s.",
+                clazz.toSourceString(), targetClass.toSourceString());
+          }
+        }
+      }
+    }
+    if (Log.ENABLED) {
+      Log.debug(getClass(), "Merged %d classes.", numberOfMerges);
+    }
+    return renamedMembersLense.build(graphLense, application.dexItemFactory);
+  }
+
+  private class ClassMerger {
+
+    private static final String CONSTRUCTOR_NAME = "constructor";
+
+    private final DexClass source;
+    private final DexClass target;
+    private final Map<DexEncodedMethod, DexEncodedMethod> deferredRenamings = new HashMap<>();
+    private boolean abortMerge = false;
+
+    private ClassMerger(DexClass source, DexClass target) {
+      this.source = source;
+      this.target = target;
+    }
+
+    public boolean merge() {
+      // Merge the class [clazz] into [targetClass] by adding all methods to
+      // targetClass that are not currently contained.
+      // Step 1: Merge methods
+      Set<Wrapper<DexMethod>> existingMethods = new HashSet<>();
+      addAll(existingMethods, target.directMethods(), MethodSignatureEquivalence.get());
+      addAll(existingMethods, target.virtualMethods(), MethodSignatureEquivalence.get());
+      Collection<DexEncodedMethod> mergedDirectMethods = mergeItems(
+          Iterators.transform(Iterators.forArray(source.directMethods()), this::renameConstructors),
+          target.directMethods(),
+          MethodSignatureEquivalence.get(),
+          existingMethods,
+          this::renameMethod
+      );
+      Iterator<DexEncodedMethod> methods = Iterators.forArray(source.virtualMethods());
+      if (source.accessFlags.isInterface()) {
+        // If merging an interface, only merge methods that are not otherwise defined in the
+        // target class.
+        methods = Iterators.transform(methods, this::filterShadowedInterfaceMethods);
+      }
+      Collection<DexEncodedMethod> mergedVirtualMethods = mergeItems(
+          methods,
+          target.virtualMethods(),
+          MethodSignatureEquivalence.get(),
+          existingMethods,
+          this::abortOnNonAbstract);
+      if (abortMerge) {
+        return false;
+      }
+      // Step 2: Merge fields
+      Set<Wrapper<DexField>> existingFields = new HashSet<>();
+      addAll(existingFields, target.instanceFields(), FieldSignatureEquivalence.get());
+      addAll(existingFields, target.staticFields(), FieldSignatureEquivalence.get());
+      Collection<DexEncodedField> mergedStaticFields = mergeItems(
+          Iterators.forArray(source.staticFields()),
+          target.staticFields(),
+          FieldSignatureEquivalence.get(),
+          existingFields,
+          this::renameField);
+      Collection<DexEncodedField> mergedInstanceFields = mergeItems(
+          Iterators.forArray(source.instanceFields()),
+          target.instanceFields(),
+          FieldSignatureEquivalence.get(),
+          existingFields,
+          this::renameField);
+      // Step 3: Merge interfaces
+      Set<DexType> interfaces = mergeArrays(target.interfaces.values, source.interfaces.values);
+      // Now destructively update the class.
+      // Step 1: Update supertype or fix interfaces.
+      if (source.isInterface()) {
+        interfaces.remove(source.type);
+      } else {
+        assert !target.isInterface();
+        target.superType = source.superType;
+      }
+      target.interfaces = interfaces.isEmpty()
+          ? DexTypeList.empty()
+          : new DexTypeList(interfaces.toArray(new DexType[interfaces.size()]));
+      // Step 2: replace fields and methods.
+      target.directMethods = mergedDirectMethods
+          .toArray(new DexEncodedMethod[mergedDirectMethods.size()]);
+      target.virtualMethods = mergedVirtualMethods
+          .toArray(new DexEncodedMethod[mergedVirtualMethods.size()]);
+      target.staticFields = mergedStaticFields
+          .toArray(new DexEncodedField[mergedStaticFields.size()]);
+      target.instanceFields = mergedInstanceFields
+          .toArray(new DexEncodedField[mergedInstanceFields.size()]);
+      // Step 3: Unlink old class to ease tree shaking.
+      source.superType = application.dexItemFactory.objectType;
+      source.directMethods = null;
+      source.virtualMethods = null;
+      source.instanceFields = null;
+      source.staticFields = null;
+      source.interfaces = DexTypeList.empty();
+      // Step 4: Record merging.
+      mergedClasses.put(source.type, target.type);
+      // Step 5: Make deferred renamings final.
+      deferredRenamings.forEach((from, to) -> renamedMembersLense.map(from.method, to.method));
+      return true;
+    }
+
+    private DexEncodedMethod filterShadowedInterfaceMethods(DexEncodedMethod m) {
+      DexEncodedMethod actual = appInfo.lookupVirtualDefinition(target.type, m.method);
+      assert actual != null;
+      if (actual != m) {
+        // We will drop a method here, so record it as a potential renaming.
+        deferredRenamings.put(m, actual);
+        return null;
+      }
+      // We will keep the method, so the class better be abstract.
+      assert target.accessFlags.isAbstract();
+      return m;
+    }
+
+    private <T extends KeyedDexItem<S>, S extends PresortedComparable<S>> void addAll(
+        Collection<Wrapper<S>> collection, T[] items, Equivalence<S> equivalence) {
+      for (T item : items) {
+        collection.add(equivalence.wrap(item.getKey()));
+      }
+    }
+
+    private <T> Set<T> mergeArrays(T[] one, T[] other) {
+      Set<T> merged = new LinkedHashSet<T>();
+      Collections.addAll(merged, one);
+      Collections.addAll(merged, other);
+      return merged;
+    }
+
+    private <T extends PresortedComparable<T>, S extends KeyedDexItem<T>> Collection<S> mergeItems(
+        Iterator<S> fromItems,
+        S[] toItems,
+        Equivalence<T> equivalence,
+        Set<Wrapper<T>> existing,
+        BiFunction<S, S, S> onConflict) {
+      HashMap<Wrapper<T>, S> methods = new HashMap<>();
+      // First add everything from the target class. These items are not preprocessed.
+      for (S item : toItems) {
+        methods.put(equivalence.wrap(item.getKey()), item);
+      }
+      // Now add the new methods, resolving shadowing.
+      addNonShadowed(fromItems, methods, equivalence, existing, onConflict);
+      return methods.values();
+    }
+
+    private <T extends PresortedComparable<T>, S extends KeyedDexItem<T>> void addNonShadowed(
+        Iterator<S> items,
+        HashMap<Wrapper<T>, S> map,
+        Equivalence<T> equivalence,
+        Set<Wrapper<T>> existing,
+        BiFunction<S, S, S> onConflict) {
+      while (items.hasNext()) {
+        S item = items.next();
+        if (item == null) {
+          // This item was filtered out by a preprocessing.
+          continue;
+        }
+        Wrapper<T> wrapped = equivalence.wrap(item.getKey());
+        if (existing.contains(wrapped)) {
+          S resolved = onConflict.apply(map.get(wrapped), item);
+          wrapped = equivalence.wrap(resolved.getKey());
+          map.put(wrapped, resolved);
+        } else {
+          map.put(wrapped, item);
+        }
+      }
+    }
+
+    private DexString makeMergedName(String nameString, DexType holder) {
+      return application.dexItemFactory
+          .createString(nameString + "$" + holder.toSourceString().replace('.', '$'));
+    }
+
+    private DexEncodedMethod abortOnNonAbstract(DexEncodedMethod existing,
+        DexEncodedMethod method) {
+      if (existing == null) {
+        // This is a conflict between a static and virtual method. Abort.
+        abortMerge = true;
+        return method;
+      }
+      // Ignore if we merge in an abstract method or if we override a bridge method that would
+      // bridge to the superclasses method.
+      if (method.accessFlags.isAbstract()) {
+        // We make a method disappear here, so record the renaming so that calls to the previous
+        // target get forwarded properly.
+        deferredRenamings.put(method, existing);
+        return existing;
+      } else if (existing.accessFlags.isBridge()) {
+        InvokeSingleTargetExtractor extractor = new InvokeSingleTargetExtractor();
+        existing.getCode().registerReachableDefinitions(extractor);
+        if (extractor.getTarget() != method.method) {
+          abortMerge = true;
+        }
+        return method;
+      } else {
+        abortMerge = true;
+        return existing;
+      }
+    }
+
+    private DexEncodedMethod renameConstructors(DexEncodedMethod method) {
+      // Only rename instance initializers.
+      if (!method.accessFlags.isConstructor() || method.accessFlags.isStatic()) {
+        return method;
+      }
+      DexType holder = method.method.holder;
+      DexEncodedMethod result = method
+          .toRenamedMethod(makeMergedName(CONSTRUCTOR_NAME, holder), application.dexItemFactory);
+      result.markForceInline();
+      deferredRenamings.put(method, result);
+      // Renamed constructors turn into ordinary private functions. They can be private, as
+      // they are only references from their direct subclass, which they were merged into.
+      result.accessFlags.unsetConstructor();
+      result.accessFlags.unsetPublic();
+      result.accessFlags.unsetProtected();
+      result.accessFlags.setPrivate();
+      return result;
+    }
+
+    private DexEncodedMethod renameMethod(DexEncodedMethod existing, DexEncodedMethod method) {
+      // We cannot handle renaming static initializers yet and constructors should have been
+      // renamed already.
+      assert !method.accessFlags.isConstructor();
+      DexType holder = method.method.holder;
+      String name = method.method.name.toSourceString();
+      DexEncodedMethod result = method
+          .toRenamedMethod(makeMergedName(name, holder), application.dexItemFactory);
+      renamedMembersLense.map(method.method, result.method);
+      return result;
+    }
+
+    private DexEncodedField renameField(DexEncodedField existing, DexEncodedField field) {
+      DexString oldName = field.field.name;
+      DexType holder = field.field.clazz;
+      DexEncodedField result = field
+          .toRenamedField(makeMergedName(oldName.toSourceString(), holder),
+              application.dexItemFactory);
+      renamedMembersLense.map(field.field, result.field);
+      return result;
+    }
+  }
+
+  private class TreeFixer {
+
+    private final Builder lense = GraphLense.builder();
+    Map<DexProto, DexProto> protoFixupCache = new IdentityHashMap<>();
+
+    private GraphLense fixupTypeReferences(GraphLense graphLense) {
+      // Globally substitute merged class types in protos and holders.
+      for (DexProgramClass clazz : appInfo.classes()) {
+        clazz.directMethods = substituteTypesIn(clazz.directMethods);
+        clazz.virtualMethods = substituteTypesIn(clazz.virtualMethods);
+        clazz.virtualMethods = removeDupes(clazz.virtualMethods);
+        clazz.staticFields = substituteTypesIn(clazz.staticFields);
+        clazz.instanceFields = substituteTypesIn(clazz.instanceFields);
+      }
+      // Record type renamings so instanceof and checkcast checks are also fixed.
+      for (DexType type : mergedClasses.keySet()) {
+        DexType fixed = fixupType(type);
+        lense.map(type, fixed);
+      }
+      return lense.build(graphLense, application.dexItemFactory);
+    }
+
+    private DexEncodedMethod[] removeDupes(DexEncodedMethod[] methods) {
+      if (methods == null) {
+        return null;
+      }
+      Map<DexMethod, DexEncodedMethod> filtered = new IdentityHashMap<>();
+      for (DexEncodedMethod method : methods) {
+        DexEncodedMethod previous = filtered.put(method.method, method);
+        if (previous != null) {
+          if (!previous.accessFlags.isBridge()) {
+            if (!method.accessFlags.isBridge()) {
+              throw new CompilationError("Class merging produced invalid result.");
+            } else {
+              filtered.put(previous.method, previous);
+            }
+          }
+        }
+      }
+      if (filtered.size() == methods.length) {
+        return methods;
+      }
+      return filtered.values().toArray(new DexEncodedMethod[filtered.size()]);
+    }
+
+    private DexEncodedMethod[] substituteTypesIn(DexEncodedMethod[] methods) {
+      if (methods == null) {
+        return null;
+      }
+      for (int i = 0; i < methods.length; i++) {
+        DexEncodedMethod encodedMethod = methods[i];
+        DexMethod method = encodedMethod.method;
+        DexProto newProto = getUpdatedProto(method.proto);
+        DexType newHolder = fixupType(method.holder);
+        DexMethod newMethod = application.dexItemFactory.createMethod(newHolder, newProto,
+            method.name);
+        if (newMethod != encodedMethod.method) {
+          lense.map(encodedMethod.method, newMethod);
+          methods[i] = encodedMethod.toTypeSubstitutedMethod(newMethod);
+        }
+      }
+      return methods;
+    }
+
+    private DexEncodedField[] substituteTypesIn(DexEncodedField[] fields) {
+      if (fields == null) {
+        return null;
+      }
+      for (int i = 0; i < fields.length; i++) {
+        DexEncodedField encodedField = fields[i];
+        DexField field = encodedField.field;
+        DexType newType = fixupType(field.type);
+        DexType newHolder = fixupType(field.clazz);
+        DexField newField = application.dexItemFactory.createField(newHolder, newType, field.name);
+        if (newField != encodedField.field) {
+          lense.map(encodedField.field, newField);
+          fields[i] = encodedField.toTypeSubstitutedField(newField);
+        }
+      }
+      return fields;
+    }
+
+    private DexProto getUpdatedProto(DexProto proto) {
+      DexProto result = protoFixupCache.get(proto);
+      if (result == null) {
+        DexType returnType = fixupType(proto.returnType);
+        DexType[] arguments = fixupTypes(proto.parameters.values);
+        result = application.dexItemFactory.createProto(returnType, arguments);
+        protoFixupCache.put(proto, result);
+      }
+      return result;
+    }
+
+    private DexType fixupType(DexType type) {
+      if (type.isArrayType()) {
+        DexType base = type.toBaseType(application.dexItemFactory);
+        DexType fixed = fixupType(base);
+        if (base == fixed) {
+          return type;
+        } else {
+          return type.replaceBaseType(fixed, application.dexItemFactory);
+        }
+      }
+      while (mergedClasses.containsKey(type)) {
+        type = mergedClasses.get(type);
+      }
+      return type;
+    }
+
+    private DexType[] fixupTypes(DexType[] types) {
+      DexType[] result = new DexType[types.length];
+      for (int i = 0; i < result.length; i++) {
+        result[i] = fixupType(types[i]);
+      }
+      return result;
+    }
+  }
+
+  private static class CollisionDetector {
+
+    // TODO(herhut): Maybe cache seenPositions for target classes.
+    private final Map<DexString, IntIntHashMap> seenPositions = new IdentityHashMap<>();
+    private final HashMapInt<DexProto> targetProtoCache;
+    private final HashMapInt<DexProto> sourceProtoCache;
+    private final DexType source, target;
+    private final Set<DexMethod> invokes;
+    private final Map<DexType, DexType> substituions;
+
+    private CollisionDetector(DexType source, DexType target, Set<DexMethod> invokes,
+        Map<DexType, DexType> substitutions) {
+      this.source = source;
+      this.target = target;
+      this.invokes = invokes;
+      this.substituions = substitutions;
+      this.targetProtoCache = new IdentityHashMapInt<>(invokes.size() / 2);
+      this.sourceProtoCache = new IdentityHashMapInt<>(invokes.size() / 2);
+    }
+
+    boolean mayCollide() {
+      fillSeenPositions(invokes);
+      // If the type is not used in methods at all, there cannot be any conflict.
+      if (seenPositions.isEmpty()) {
+        return false;
+      }
+      for (DexMethod method : invokes) {
+        IntIntHashMap positionsMap = seenPositions.get(method.name);
+        if (positionsMap != null) {
+          int arity = method.proto.parameters.values.length;
+          if (positionsMap.containsKey(arity)) {
+            int previous = positionsMap.get(arity);
+            assert previous != 0;
+            int positions = computePositionsFor(method.proto, source, sourceProtoCache,
+                substituions);
+            if ((positions & previous) != 0) {
+              return true;
+            }
+          }
+        }
+      }
+      return false;
+    }
+
+    private void fillSeenPositions(Collection<DexMethod> invokes) {
+      for (DexMethod method : invokes) {
+        DexType[] parameters = method.proto.parameters.values;
+        int arity = parameters.length;
+        int positions = computePositionsFor(method.proto, target, targetProtoCache, substituions);
+        if (positions != 0) {
+          IntIntHashMap positionsMap =
+              seenPositions.computeIfAbsent(method.name, k -> new IntIntHashMap());
+          int value = 0;
+          if (positionsMap.containsKey(arity)) {
+            value = positionsMap.get(arity);
+          }
+          value |= positions;
+          positionsMap.put(arity, value);
+        }
+      }
+      int filled = 0;
+      for (IntIntHashMap pos : seenPositions.values()) {
+        filled += pos.size();
+      }
+    }
+
+    private int computePositionsFor(DexProto proto, DexType type,
+        HashMapInt<DexProto> cache, Map<DexType, DexType> substituions) {
+      if (cache.containsKey(proto)) {
+        return cache.get(proto);
+      }
+      int result = 0;
+      int bits = 0;
+      int accumulator = 0;
+      for (DexType aType : proto.parameters.values) {
+        if (substituions != null) {
+          // Substitute the type with the already merged class to estimate what it will
+          // look like.
+          while (substituions.containsKey(aType)) {
+            aType = substituions.get(aType);
+          }
+        }
+        accumulator <<= 1;
+        bits++;
+        if (aType == type) {
+          accumulator |= 1;
+        }
+        // Handle overflow on 32 bit boundary.
+        if (bits == Integer.SIZE) {
+          result |= accumulator;
+          accumulator = 0;
+          bits = 0;
+        }
+      }
+      // We also take the return type into account for potential conflicts.
+      DexType returnType = proto.returnType;
+      if (substituions != null) {
+        while (substituions.containsKey(returnType)) {
+          returnType = substituions.get(returnType);
+        }
+      }
+      accumulator <<= 1;
+      if (returnType == type) {
+        accumulator |= 1;
+      }
+      result |= accumulator;
+      cache.put(proto, result);
+      return result;
+    }
+  }
+}
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 5f2996f..f801cdd 100644
--- a/src/main/java/com/android/tools/r8/shaking/TreePruner.java
+++ b/src/main/java/com/android/tools/r8/shaking/TreePruner.java
@@ -76,10 +76,10 @@
             // However, this might extend an abstract class and we might have removed the
             // corresponding methods in this class. This might happen if we only keep this
             // class around for its constants.
-            // TODO(herhut): Find alternative for abstract final classes.
-          } else {
-            clazz.accessFlags.setAbstract();
+            // For now, we remove the final flag to still be able to mark it abstract.
+            clazz.accessFlags.unsetFinal();
           }
+          clazz.accessFlags.setAbstract();
         }
         // The class is used and must be kept. Remove the unused fields and methods from
         // the class.
diff --git a/src/main/java/com/android/tools/r8/utils/AndroidApp.java b/src/main/java/com/android/tools/r8/utils/AndroidApp.java
index 6d46efe..85d5c57 100644
--- a/src/main/java/com/android/tools/r8/utils/AndroidApp.java
+++ b/src/main/java/com/android/tools/r8/utils/AndroidApp.java
@@ -203,12 +203,16 @@
     return proguardSeeds == null ? null : proguardSeeds.getStream(closer);
   }
 
-  /** True if the package distribution resource exists. */
+  /**
+   * True if the package distribution resource exists.
+   */
   public boolean hasPackageDistribution() {
     return packageDistribution != null;
   }
 
-  /** Get the input stream of the package distribution resource if it exists. */
+  /**
+   * Get the input stream of the package distribution resource if it exists.
+   */
   public InputStream getPackageDistribution(Closer closer) throws IOException {
     return packageDistribution == null ? null : packageDistribution.getStream(closer);
   }
@@ -407,7 +411,9 @@
       return addProgramFiles(Arrays.asList(files));
     }
 
-    /** Add program file resources. */
+    /**
+     * Add program file resources.
+     */
     public Builder addProgramFiles(Collection<Path> files) throws IOException {
       for (Path file : files) {
         addFile(file, Resource.Kind.PROGRAM);
@@ -422,7 +428,9 @@
       return addClasspathFiles(Arrays.asList(files));
     }
 
-    /** Add classpath file resources. */
+    /**
+     * Add classpath file resources.
+     */
     public Builder addClasspathFiles(Collection<Path> files) throws IOException {
       for (Path file : files) {
         addFile(file, Resource.Kind.CLASSPATH);
@@ -437,7 +445,9 @@
       return addLibraryFiles(Arrays.asList(files));
     }
 
-    /** Add library file resources. */
+    /**
+     * Add library file resources.
+     */
     public Builder addLibraryFiles(Collection<Path> files) throws IOException {
       for (Path file : files) {
         addFile(file, Resource.Kind.LIBRARY);
@@ -452,7 +462,9 @@
       return addDexProgramData(Arrays.asList(data));
     }
 
-    /** Add dex program-data. */
+    /**
+     * Add dex program-data.
+     */
     public Builder addDexProgramData(Collection<byte[]> data) {
       for (byte[] datum : data) {
         dexSources.add(InternalResource.fromBytes(Resource.Kind.PROGRAM, datum));
@@ -467,7 +479,9 @@
       return addClassProgramData(Arrays.asList(data));
     }
 
-    /** Add Java-bytecode program data. */
+    /**
+     * Add Java-bytecode program data.
+     */
     public Builder addClassProgramData(Collection<byte[]> data) {
       for (byte[] datum : data) {
         classSources.add(InternalResource.fromBytes(Resource.Kind.PROGRAM, datum));
@@ -475,36 +489,48 @@
       return this;
     }
 
-    /** Set proguard-map file. */
+    /**
+     * Set proguard-map file.
+     */
     public Builder setProguardMapFile(Path file) {
       proguardMap = file == null ? null : InternalResource.fromFile(null, file);
       return this;
     }
 
-    /** Set proguard-map data. */
+    /**
+     * Set proguard-map data.
+     */
     public Builder setProguardMapData(String content) {
       return setProguardMapData(content == null ? null : content.getBytes(StandardCharsets.UTF_8));
     }
 
-    /** Set proguard-map data. */
+    /**
+     * Set proguard-map data.
+     */
     public Builder setProguardMapData(byte[] content) {
       proguardMap = content == null ? null : InternalResource.fromBytes(null, content);
       return this;
     }
 
-    /** Set proguard-seeds data. */
+    /**
+     * Set proguard-seeds data.
+     */
     public Builder setProguardSeedsData(byte[] content) {
       proguardSeeds = content == null ? null : InternalResource.fromBytes(null, content);
       return this;
     }
 
-    /** Set the package-distribution file. */
+    /**
+     * Set the package-distribution file.
+     */
     public Builder setPackageDistributionFile(Path file) {
       packageDistribution = file == null ? null : InternalResource.fromFile(null, file);
       return this;
     }
 
-    /** Set the main-dex list file. */
+    /**
+     * Set the main-dex list file.
+     */
     public Builder setMainDexListFile(Path file) {
       mainDexList = file == null ? null : InternalResource.fromFile(null, file);
       return this;
diff --git a/src/main/java/com/android/tools/r8/utils/FieldSignatureEquivalence.java b/src/main/java/com/android/tools/r8/utils/FieldSignatureEquivalence.java
new file mode 100644
index 0000000..8006e6d
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/utils/FieldSignatureEquivalence.java
@@ -0,0 +1,34 @@
+// Copyright (c) 2017, 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;
+
+import com.android.tools.r8.graph.DexField;
+import com.google.common.base.Equivalence;
+
+/**
+ * Implements an equivalence on {@link DexField} that does not take the holder into account.
+ *
+ * <p>Useful when comparing method implementations by their signature only.
+ */
+public class FieldSignatureEquivalence extends Equivalence<DexField> {
+
+  private static final FieldSignatureEquivalence THEINSTANCE = new FieldSignatureEquivalence();
+
+  private FieldSignatureEquivalence() {
+  }
+
+  public static FieldSignatureEquivalence get() {
+    return THEINSTANCE;
+  }
+
+  @Override
+  protected boolean doEquivalent(DexField a, DexField b) {
+    return a.name.equals(b.name) && a.type.equals(b.type);
+  }
+
+  @Override
+  protected int doHash(DexField field) {
+    return field.name.hashCode() * 31 + field.type.hashCode();
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/utils/MethodJavaSignatureEquivalence.java b/src/main/java/com/android/tools/r8/utils/MethodJavaSignatureEquivalence.java
new file mode 100644
index 0000000..1b60380
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/utils/MethodJavaSignatureEquivalence.java
@@ -0,0 +1,36 @@
+// Copyright (c) 2017, 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;
+
+import com.android.tools.r8.graph.DexMethod;
+import com.google.common.base.Equivalence;
+
+/**
+ * Implements an equivalence on {@link DexMethod} that does not take the holder nor return type into
+ * account.
+ *
+ * <p>Useful when deciding whether methods shadow each other wrt. Java semantics.
+ */
+public class MethodJavaSignatureEquivalence extends Equivalence<DexMethod> {
+
+  private static final MethodJavaSignatureEquivalence THEINSTANCE
+      = new MethodJavaSignatureEquivalence();
+
+  private MethodJavaSignatureEquivalence() {
+  }
+
+  public static MethodJavaSignatureEquivalence get() {
+    return THEINSTANCE;
+  }
+
+  @Override
+  protected boolean doEquivalent(DexMethod a, DexMethod b) {
+    return a.name.equals(b.name) && a.proto.parameters.equals(b.proto.parameters);
+  }
+
+  @Override
+  protected int doHash(DexMethod method) {
+    return method.name.hashCode() * 31 + method.proto.parameters.hashCode();
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/utils/MethodSignatureEquivalence.java b/src/main/java/com/android/tools/r8/utils/MethodSignatureEquivalence.java
index 86ce165..c47494a 100644
--- a/src/main/java/com/android/tools/r8/utils/MethodSignatureEquivalence.java
+++ b/src/main/java/com/android/tools/r8/utils/MethodSignatureEquivalence.java
@@ -3,13 +3,11 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.utils;
 
-import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexMethod;
 import com.google.common.base.Equivalence;
 
 /**
- * Implements an equivalence on {@link DexEncodedMethod} that does not take the holder into
- * account.
+ * Implements an equivalence on {@link DexMethod} that does not take the holder into account.
  *
  * <p>Useful when comparing method implementations by their signature only.
  */
diff --git a/src/test/examples/classmerging/ClassWithConflictingMethod.java b/src/test/examples/classmerging/ClassWithConflictingMethod.java
new file mode 100644
index 0000000..b4bf9d7
--- /dev/null
+++ b/src/test/examples/classmerging/ClassWithConflictingMethod.java
@@ -0,0 +1,11 @@
+// Copyright (c) 2017, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package classmerging;
+
+public class ClassWithConflictingMethod {
+
+  public static int conflict(ConflictingInterface item) {
+    return 123;
+  }
+}
diff --git a/src/test/examples/classmerging/ConflictingInterface.java b/src/test/examples/classmerging/ConflictingInterface.java
new file mode 100644
index 0000000..6202e3c
--- /dev/null
+++ b/src/test/examples/classmerging/ConflictingInterface.java
@@ -0,0 +1,9 @@
+// Copyright (c) 2017, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package classmerging;
+
+public interface ConflictingInterface {
+
+  public String method();
+}
diff --git a/src/test/examples/classmerging/ConflictingInterfaceImpl.java b/src/test/examples/classmerging/ConflictingInterfaceImpl.java
new file mode 100644
index 0000000..e46edaf
--- /dev/null
+++ b/src/test/examples/classmerging/ConflictingInterfaceImpl.java
@@ -0,0 +1,12 @@
+// Copyright (c) 2017, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package classmerging;
+
+public class ConflictingInterfaceImpl implements ConflictingInterface {
+
+  @Override
+  public String method() {
+    return "ConflictingInterfaceImpl::method";
+  }
+}
diff --git a/src/test/examples/classmerging/GenericAbstractClass.java b/src/test/examples/classmerging/GenericAbstractClass.java
new file mode 100644
index 0000000..42620f6
--- /dev/null
+++ b/src/test/examples/classmerging/GenericAbstractClass.java
@@ -0,0 +1,13 @@
+// Copyright (c) 2017, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package classmerging;
+
+public abstract class GenericAbstractClass<T> {
+
+  public abstract T method();
+
+  public T otherMethod() {
+    return null;
+  }
+}
diff --git a/src/test/examples/classmerging/GenericAbstractClassImpl.java b/src/test/examples/classmerging/GenericAbstractClassImpl.java
new file mode 100644
index 0000000..931465e
--- /dev/null
+++ b/src/test/examples/classmerging/GenericAbstractClassImpl.java
@@ -0,0 +1,17 @@
+// Copyright (c) 2017, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package classmerging;
+
+public class GenericAbstractClassImpl extends GenericAbstractClass<String> {
+
+  @Override
+  public String method() {
+    return "Hello from GenericAbstractClassImpl";
+  }
+
+  @Override
+  public String otherMethod() {
+    return "otherMethod";
+  }
+}
diff --git a/src/test/examples/classmerging/GenericInterface.java b/src/test/examples/classmerging/GenericInterface.java
new file mode 100644
index 0000000..cda0b32
--- /dev/null
+++ b/src/test/examples/classmerging/GenericInterface.java
@@ -0,0 +1,9 @@
+// Copyright (c) 2017, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package classmerging;
+
+public interface GenericInterface<T> {
+
+  T method();
+}
diff --git a/src/test/examples/classmerging/GenericInterfaceImpl.java b/src/test/examples/classmerging/GenericInterfaceImpl.java
new file mode 100644
index 0000000..6a14107
--- /dev/null
+++ b/src/test/examples/classmerging/GenericInterfaceImpl.java
@@ -0,0 +1,12 @@
+// Copyright (c) 2017, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package classmerging;
+
+public class GenericInterfaceImpl implements GenericInterface<String> {
+
+  @Override
+  public String method() {
+    return "method";
+  }
+}
diff --git a/src/test/examples/classmerging/OtherClassWithConflictingMethod.java b/src/test/examples/classmerging/OtherClassWithConflictingMethod.java
new file mode 100644
index 0000000..cd7efd1
--- /dev/null
+++ b/src/test/examples/classmerging/OtherClassWithConflictingMethod.java
@@ -0,0 +1,11 @@
+// Copyright (c) 2017, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package classmerging;
+
+public class OtherClassWithConflictingMethod {
+
+  public static int conflict(ConflictingInterfaceImpl item) {
+    return 321;
+  }
+}
diff --git a/src/test/examples/classmerging/Outer.java b/src/test/examples/classmerging/Outer.java
new file mode 100644
index 0000000..652f794
--- /dev/null
+++ b/src/test/examples/classmerging/Outer.java
@@ -0,0 +1,26 @@
+// Copyright (c) 2017, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package classmerging;
+
+class Outer {
+
+  /**
+   * This class is package private to trigger the generation of bridge methods
+   * for the visibility change of methods from public subtypes.
+   */
+  class SuperClass {
+
+    public String method() {
+      return "Method in SuperClass.";
+    }
+  }
+
+  public class SubClass extends SuperClass {
+    // Intentionally left empty.
+  }
+
+  public SubClass getInstance() {
+    return new SubClass();
+  }
+}
diff --git a/src/test/examples/classmerging/SubClass.java b/src/test/examples/classmerging/SubClass.java
new file mode 100644
index 0000000..b6a9054
--- /dev/null
+++ b/src/test/examples/classmerging/SubClass.java
@@ -0,0 +1,22 @@
+// Copyright (c) 2017, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package classmerging;
+
+public class SubClass extends SuperClass {
+
+  private int field;
+
+  public SubClass(int field) {
+    this(field, field + 100);
+  }
+
+  public SubClass(int one, int other) {
+    super(one);
+    field = other;
+  }
+
+  public String toString() {
+    return "is " + field + " " + getField();
+  }
+}
diff --git a/src/test/examples/classmerging/SubClassThatReferencesSuperMethod.java b/src/test/examples/classmerging/SubClassThatReferencesSuperMethod.java
new file mode 100644
index 0000000..c12804c
--- /dev/null
+++ b/src/test/examples/classmerging/SubClassThatReferencesSuperMethod.java
@@ -0,0 +1,12 @@
+// Copyright (c) 2017, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package classmerging;
+
+public class SubClassThatReferencesSuperMethod extends SuperClassWithReferencedMethod {
+
+  @Override
+  public String referencedMethod() {
+    return "From sub: " + super.referencedMethod();
+  }
+}
diff --git a/src/test/examples/classmerging/SuperClass.java b/src/test/examples/classmerging/SuperClass.java
new file mode 100644
index 0000000..b7c9207
--- /dev/null
+++ b/src/test/examples/classmerging/SuperClass.java
@@ -0,0 +1,17 @@
+// Copyright (c) 2017, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package classmerging;
+
+public class SuperClass {
+
+  private final int field;
+
+  public SuperClass(int field) {
+    this.field = field;
+  }
+
+  public int getField() {
+    return field;
+  }
+}
diff --git a/src/test/examples/classmerging/SuperClassWithReferencedMethod.java b/src/test/examples/classmerging/SuperClassWithReferencedMethod.java
new file mode 100644
index 0000000..8d4e7b5
--- /dev/null
+++ b/src/test/examples/classmerging/SuperClassWithReferencedMethod.java
@@ -0,0 +1,11 @@
+// Copyright (c) 2017, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package classmerging;
+
+public class SuperClassWithReferencedMethod {
+
+  public String referencedMethod() {
+    return "From Super";
+  }
+}
diff --git a/src/test/examples/classmerging/Test.java b/src/test/examples/classmerging/Test.java
new file mode 100644
index 0000000..6d5c51f
--- /dev/null
+++ b/src/test/examples/classmerging/Test.java
@@ -0,0 +1,34 @@
+// Copyright (c) 2017, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package classmerging;
+
+public class Test {
+
+  public static void main(String... args) {
+    GenericInterface iface = new GenericInterfaceImpl();
+    callMethodOnIface(iface);
+    GenericAbstractClass clazz = new GenericAbstractClassImpl();
+    callMethodOnAbstractClass(clazz);
+    ConflictingInterfaceImpl impl = new ConflictingInterfaceImpl();
+    callMethodOnIface(impl);
+    System.out.println(new SubClassThatReferencesSuperMethod().referencedMethod());
+    System.out.println(new Outer().getInstance().method());
+    System.out.println(new SubClass(42));
+  }
+
+  private static void callMethodOnIface(GenericInterface iface) {
+    System.out.println(iface.method());
+  }
+
+  private static void callMethodOnAbstractClass(GenericAbstractClass clazz) {
+    System.out.println(clazz.method());
+    System.out.println(clazz.otherMethod());
+  }
+
+  private static void callMethodOnIface(ConflictingInterface iface) {
+    System.out.println(iface.method());
+    System.out.println(ClassWithConflictingMethod.conflict(null));
+    System.out.println(OtherClassWithConflictingMethod.conflict(null));
+  }
+}
diff --git a/src/test/examples/classmerging/keep-rules.txt b/src/test/examples/classmerging/keep-rules.txt
new file mode 100644
index 0000000..58b262b
--- /dev/null
+++ b/src/test/examples/classmerging/keep-rules.txt
@@ -0,0 +1,12 @@
+# Copyright (c) 2016, the R8 project authors. Please see the AUTHORS file
+# for details. All rights reserved. Use of this source code is governed by a
+# BSD-style license that can be found in the LICENSE file.
+
+# Keep the application entry point. Get rid of everything that is not
+# reachable from there.
+-keep public class classmerging.Test {
+  public static void main(...);
+}
+
+# allow access modification to enable minification
+-allowaccessmodification
diff --git a/src/test/examplesAndroidO/invokecustom/keep-rules.txt b/src/test/examplesAndroidO/invokecustom/keep-rules.txt
index 52fa2a7..bcefc4b 100644
--- a/src/test/examplesAndroidO/invokecustom/keep-rules.txt
+++ b/src/test/examplesAndroidO/invokecustom/keep-rules.txt
@@ -8,7 +8,7 @@
   public static void main(...);
 }
 
--keepclassmembers  class * {
+-keepclasseswithmembers  class * {
   *** targetMethodTest*(...);
 }
 
diff --git a/src/test/java/com/android/tools/r8/classmerging/ClassMergingTest.java b/src/test/java/com/android/tools/r8/classmerging/ClassMergingTest.java
new file mode 100644
index 0000000..2326eb5
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/classmerging/ClassMergingTest.java
@@ -0,0 +1,72 @@
+package com.android.tools.r8.classmerging;
+
+import com.android.tools.r8.CompilationException;
+import com.android.tools.r8.R8Command;
+import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.shaking.ProguardRuleParserException;
+import com.android.tools.r8.utils.DexInspector;
+import java.io.IOException;
+import java.nio.file.Path;
+import java.nio.file.Paths;
+import java.util.concurrent.ExecutionException;
+import org.junit.Assert;
+import org.junit.Before;
+import org.junit.Rule;
+import org.junit.Test;
+import org.junit.rules.TemporaryFolder;
+
+public class ClassMergingTest {
+
+  private static final Path EXAMPLE_JAR = Paths.get(ToolHelper.EXAMPLES_BUILD_DIR)
+      .resolve("classmerging.jar");
+  private static final Path EXAMPLE_KEEP = Paths.get(ToolHelper.EXAMPLES_DIR)
+      .resolve("classmerging").resolve("keep-rules.txt");
+
+  @Rule
+  public TemporaryFolder temp = ToolHelper.getTemporaryFolderForTest();
+
+  @Before
+  public void runR8()
+      throws IOException, ProguardRuleParserException, ExecutionException, CompilationException {
+    // Disable access modification, as it otherwise is difficult to test visibility bridge methods.
+    ToolHelper.runR8(
+        R8Command.builder()
+            .setOutputPath(Paths.get(temp.getRoot().getCanonicalPath()))
+            .addProgramFiles(EXAMPLE_JAR)
+            .addProguardConfigurationFiles(EXAMPLE_KEEP)
+            .setMinification(false)
+            .build(), o -> o.allowAccessModification = false);
+    inspector = new DexInspector(
+        Paths.get(temp.getRoot().getCanonicalPath()).resolve("classes.dex"));
+  }
+
+  private DexInspector inspector;
+
+  @Test
+  public void testClassesHaveBeenMerged() throws IOException, ExecutionException {
+    // GenericInterface should be merged into GenericInterfaceImpl.
+    Assert.assertFalse(inspector.clazz("classmerging.GenericInterface").isPresent());
+    Assert.assertTrue(inspector.clazz("classmerging.GenericInterfaceImpl").isPresent());
+    Assert.assertFalse(inspector.clazz("classmerging.GenericAbstractClass").isPresent());
+    Assert.assertTrue(inspector.clazz("classmerging.GenericInterfaceImpl").isPresent());
+    Assert.assertFalse(inspector.clazz("classmerging.Outer$SuperClass").isPresent());
+    Assert.assertTrue(inspector.clazz("classmerging.Outer$SubClass").isPresent());
+    Assert.assertFalse(inspector.clazz("classmerging.SuperClass").isPresent());
+    Assert.assertTrue(inspector.clazz("classmerging.SubClass").isPresent());
+  }
+
+
+  @Test
+  public void testConflictWasDetected() throws IOException, ExecutionException {
+    Assert.assertTrue(inspector.clazz("classmerging.ConflictingInterface").isPresent());
+    Assert.assertTrue(inspector.clazz("classmerging.ConflictingInterfaceImpl").isPresent());
+  }
+
+  @Test
+  public void testSuperCallWasDetected() throws IOException, ExecutionException {
+    Assert.assertTrue(inspector.clazz("classmerging.SuperClassWithReferencedMethod").isPresent());
+    Assert
+        .assertTrue(inspector.clazz("classmerging.SubClassThatReferencesSuperMethod").isPresent());
+  }
+
+}