diff --git a/src/main/java/com/android/tools/r8/BaseCompilerCommand.java b/src/main/java/com/android/tools/r8/BaseCompilerCommand.java
index 34a3a93..584b4de 100644
--- a/src/main/java/com/android/tools/r8/BaseCompilerCommand.java
+++ b/src/main/java/com/android/tools/r8/BaseCompilerCommand.java
@@ -25,6 +25,7 @@
 
   private final CompilationMode mode;
   private final ProgramConsumer programConsumer;
+  private final StringConsumer mainDexListConsumer;
   private final int minApiLevel;
   private final Reporter reporter;
   private final boolean enableDesugaring;
@@ -33,6 +34,7 @@
   BaseCompilerCommand(boolean printHelp, boolean printVersion) {
     super(printHelp, printVersion);
     programConsumer = null;
+    mainDexListConsumer = null;
     mode = null;
     minApiLevel = 0;
     reporter = new Reporter();
@@ -44,6 +46,7 @@
       AndroidApp app,
       CompilationMode mode,
       ProgramConsumer programConsumer,
+      StringConsumer mainDexListConsumer,
       int minApiLevel,
       Reporter reporter,
       boolean enableDesugaring,
@@ -53,6 +56,7 @@
     assert mode != null;
     this.mode = mode;
     this.programConsumer = programConsumer;
+    this.mainDexListConsumer = mainDexListConsumer;
     this.minApiLevel = minApiLevel;
     this.reporter = reporter;
     this.enableDesugaring = enableDesugaring;
@@ -81,6 +85,13 @@
     return programConsumer;
   }
 
+  /**
+   * Get the main dex list consumer that will receive the final complete main dex list.
+   */
+  public StringConsumer getMainDexListConsumer() {
+    return mainDexListConsumer;
+  }
+
   /** Get the use-desugaring state. True if enabled, false otherwise. */
   public boolean getEnableDesugaring() {
     return enableDesugaring;
@@ -109,6 +120,7 @@
       extends BaseCommand.Builder<C, B> {
 
     private ProgramConsumer programConsumer = null;
+    private StringConsumer mainDexListConsumer = null;
     private Path outputPath = null;
     // TODO(b/70656566): Remove default output mode when deprecated API is removed.
     private OutputMode outputMode = OutputMode.DexIndexed;
@@ -189,6 +201,13 @@
     }
 
     /**
+     * Get the main dex list consumer that will receive the final complete main dex list.
+     */
+    public StringConsumer getMainDexListConsumer() {
+      return mainDexListConsumer;
+    }
+
+    /**
      * If set to true, legacy multidex partitioning will be optimized to reduce LinearAlloc usage
      * during Dalvik DexOpt. Has no effect when compiling for a target with native multidex support
      * or without main dex list specification.
@@ -224,6 +243,33 @@
     }
 
     /**
+     * Set an output destination to which main-dex-list content should be written.
+     *
+     * <p>This is a short-hand for setting a {@link StringConsumer.FileConsumer} using {@link
+     * #setMainDexListConsumer}. Note that any subsequent call to this method or {@link
+     * #setMainDexListConsumer} will override the previous setting.
+     *
+     * @param mainDexListOutputPath File-system path to write output at.
+     */
+    public B setMainDexListOutputPath(Path mainDexListOutputPath) {
+      mainDexListConsumer = new StringConsumer.FileConsumer(mainDexListOutputPath);
+      return self();
+    }
+
+    /**
+     * Set a consumer for receiving the main-dex-list content.
+     *
+     * <p>Note that any subsequent call to this method or {@link #setMainDexListOutputPath} will
+     * override the previous setting.
+     *
+     * @param mainDexListConsumer Consumer to receive the content once produced.
+     */
+    public B setMainDexListConsumer(StringConsumer mainDexListConsumer) {
+      this.mainDexListConsumer = mainDexListConsumer;
+      return self();
+    }
+
+    /**
      * Set the output path-and-mode.
      *
      * <p>Setting the output path-and-mode will override any previous set consumer or any previous
diff --git a/src/main/java/com/android/tools/r8/D8Command.java b/src/main/java/com/android/tools/r8/D8Command.java
index e0f330d..f0217b9 100644
--- a/src/main/java/com/android/tools/r8/D8Command.java
+++ b/src/main/java/com/android/tools/r8/D8Command.java
@@ -137,6 +137,8 @@
         if (getProgramConsumer() instanceof DexFilePerClassFileConsumer) {
           reporter.error("Option --main-dex-list cannot be used with --file-per-class");
         }
+      } else if (getMainDexListConsumer() != null) {
+        reporter.error("Option --main-dex-list-output require --main-dex-list");
       }
       super.validate();
     }
@@ -153,6 +155,7 @@
           getAppBuilder().build(),
           getMode(),
           getProgramConsumer(),
+          getMainDexListConsumer(),
           getMinApiLevel(),
           getReporter(),
           !getDisableDesugaring(),
@@ -209,6 +212,7 @@
       AndroidApp inputApp,
       CompilationMode mode,
       ProgramConsumer programConsumer,
+      StringConsumer mainDexListConsumer,
       int minApiLevel,
       Reporter diagnosticsHandler,
       boolean enableDesugaring,
@@ -218,6 +222,7 @@
         inputApp,
         mode,
         programConsumer,
+        mainDexListConsumer,
         minApiLevel,
         diagnosticsHandler,
         enableDesugaring,
@@ -235,6 +240,7 @@
     assert !internal.debug;
     internal.debug = getMode() == CompilationMode.DEBUG;
     internal.programConsumer = getProgramConsumer();
+    internal.mainDexListConsumer = getMainDexListConsumer();
     internal.minimalMainDex = internal.debug;
     internal.minApiLevel = getMinApiLevel();
     internal.intermediate = intermediate;
diff --git a/src/main/java/com/android/tools/r8/D8CommandParser.java b/src/main/java/com/android/tools/r8/D8CommandParser.java
index a933b8f..b84b398 100644
--- a/src/main/java/com/android/tools/r8/D8CommandParser.java
+++ b/src/main/java/com/android/tools/r8/D8CommandParser.java
@@ -104,6 +104,7 @@
               "  --file-per-class        # Produce a separate dex file per input class",
               "  --no-desugaring         # Force disable desugaring.",
               "  --main-dex-list <file>  # List of classes to place in the primary dex file.",
+              "  --main-dex-list-output <file> # Output resulting main dex list in <file>.",
               "  --version               # Print the version of d8.",
               "  --help                  # Print this message."));
 
@@ -198,6 +199,8 @@
           }
         } else if (arg.equals("--main-dex-list")) {
           builder.addMainDexListFiles(Paths.get(expandedArgs[++i]));
+        } else if (arg.equals("--main-dex-list-output")) {
+          builder.setMainDexListOutputPath(Paths.get(expandedArgs[++i]));
         } else if (arg.equals("--optimize-multidex-for-linearalloc")) {
           builder.setOptimizeMultidexForLinearAlloc(true);
         } else if (arg.equals("--min-api")) {
diff --git a/src/main/java/com/android/tools/r8/R8.java b/src/main/java/com/android/tools/r8/R8.java
index 6906161..7f77c6b 100644
--- a/src/main/java/com/android/tools/r8/R8.java
+++ b/src/main/java/com/android/tools/r8/R8.java
@@ -14,6 +14,7 @@
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexApplication;
 import com.android.tools.r8.graph.DexCallSite;
+import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.GraphLense;
@@ -304,7 +305,10 @@
                   .prunedCopyFrom(application, pruner.getRemovedClasses()));
           new AbstractMethodRemover(appView.appInfo()).run();
         }
-        new AnnotationRemover(appView.appInfo().withLiveness(), compatibility, options).run();
+
+        new AnnotationRemover(appView.appInfo().withLiveness(), options)
+            .ensureValid(compatibility)
+            .run();
 
         // TODO(69445518): This is still work in progress, and this file writing is currently used
         // for testing.
@@ -478,6 +482,8 @@
             // Print reasons on the application after pruning, so that we reflect the actual result.
             ReasonPrinter reasonPrinter = enqueuer.getReasonPrinter(rootSet.reasonAsked);
             reasonPrinter.run(application);
+            // Remove annotations that refer to types that no longer exist.
+            new AnnotationRemover(appView.appInfo().withLiveness(), options).run();
           }
         } finally {
           timing.end();
@@ -522,6 +528,8 @@
         return;
       }
 
+      assert application.classes().stream().allMatch(DexClass::isValid);
+
       // Generate the resulting application resources.
       writeApplication(
           executorService,
diff --git a/src/main/java/com/android/tools/r8/R8Command.java b/src/main/java/com/android/tools/r8/R8Command.java
index a1858a9..338fb4f 100644
--- a/src/main/java/com/android/tools/r8/R8Command.java
+++ b/src/main/java/com/android/tools/r8/R8Command.java
@@ -90,8 +90,6 @@
     private boolean allowPartiallyImplementedProguardOptions = false;
     private boolean allowTestProguardOptions = false;
 
-    private StringConsumer mainDexListConsumer = null;
-
     // TODO(zerny): Consider refactoring CompatProguardCommandBuilder to avoid subclassing.
     Builder() {
       this(new DefaultR8DiagnosticsHandler());
@@ -178,33 +176,6 @@
       return self();
     }
 
-    /**
-     * Set an output destination to which main-dex-list content should be written.
-     *
-     * <p>This is a short-hand for setting a {@link StringConsumer.FileConsumer} using {@link
-     * #setMainDexListConsumer}. Note that any subsequent call to this method or {@link
-     * #setMainDexListConsumer} will override the previous setting.
-     *
-     * @param mainDexListOutputPath File-system path to write output at.
-     */
-    public Builder setMainDexListOutputPath(Path mainDexListOutputPath) {
-      mainDexListConsumer = new StringConsumer.FileConsumer(mainDexListOutputPath);
-      return self();
-    }
-
-    /**
-     * Set a consumer for receiving the main-dex-list content.
-     *
-     * <p>Note that any subsequent call to this method or {@link #setMainDexListOutputPath} will
-     * override the previous setting.
-     *
-     * @param mainDexListConsumer Consumer to receive the content once produced.
-     */
-    public Builder setMainDexListConsumer(StringConsumer mainDexListConsumer) {
-      this.mainDexListConsumer = mainDexListConsumer;
-      return self();
-    }
-
     /** Add proguard configuration-file resources. */
     public Builder addProguardConfigurationFiles(Path... paths) {
       guard(() -> {
@@ -321,7 +292,7 @@
       if (getProgramConsumer() instanceof DexFilePerClassFileConsumer) {
         reporter.error("R8 does not support compiling to a single DEX file per Java class file");
       }
-      if (mainDexListConsumer != null
+      if (getMainDexListConsumer() != null
           && mainDexRules.isEmpty()
           && !getAppBuilder().hasMainDexList()) {
         reporter.error(
@@ -433,7 +404,7 @@
               getAppBuilder().build(),
               getProgramConsumer(),
               mainDexKeepRules,
-              mainDexListConsumer,
+              getMainDexListConsumer(),
               configuration,
               getMode(),
               getMinApiLevel(),
@@ -503,7 +474,6 @@
   static final String USAGE_MESSAGE = R8CommandParser.USAGE_MESSAGE;
 
   private final ImmutableList<ProguardConfigurationRule> mainDexKeepRules;
-  private final StringConsumer mainDexListConsumer;
   private final ProguardConfiguration proguardConfiguration;
   private final boolean enableTreeShaking;
   private final boolean enableMinification;
@@ -576,12 +546,11 @@
       StringConsumer proguardMapConsumer,
       Path proguardCompatibilityRulesOutput,
       boolean optimizeMultidexForLinearAlloc) {
-    super(inputApp, mode, programConsumer, minApiLevel, reporter, enableDesugaring,
-        optimizeMultidexForLinearAlloc);
+    super(inputApp, mode, programConsumer, mainDexListConsumer, minApiLevel, reporter,
+        enableDesugaring, optimizeMultidexForLinearAlloc);
     assert proguardConfiguration != null;
     assert mainDexKeepRules != null;
     this.mainDexKeepRules = mainDexKeepRules;
-    this.mainDexListConsumer = mainDexListConsumer;
     this.proguardConfiguration = proguardConfiguration;
     this.enableTreeShaking = enableTreeShaking;
     this.enableMinification = enableMinification;
@@ -594,7 +563,6 @@
   private R8Command(boolean printHelp, boolean printVersion) {
     super(printHelp, printVersion);
     mainDexKeepRules = ImmutableList.of();
-    mainDexListConsumer = null;
     proguardConfiguration = null;
     enableTreeShaking = false;
     enableMinification = false;
@@ -641,7 +609,7 @@
     assert !internal.verbose;
     internal.mainDexKeepRules = mainDexKeepRules;
     internal.minimalMainDex = getMode() == CompilationMode.DEBUG;
-    internal.mainDexListConsumer = mainDexListConsumer;
+    internal.mainDexListConsumer = getMainDexListConsumer();
     internal.lineNumberOptimization =
         !internal.debug && (proguardConfiguration.isOptimizing() || internal.enableMinification)
             ? LineNumberOptimization.ON
diff --git a/src/main/java/com/android/tools/r8/Version.java b/src/main/java/com/android/tools/r8/Version.java
index 29d54b4..bdea79c 100644
--- a/src/main/java/com/android/tools/r8/Version.java
+++ b/src/main/java/com/android/tools/r8/Version.java
@@ -11,7 +11,7 @@
 
   // This field is accessed from release scripts using simple pattern matching.
   // Therefore, changing this field could break our release scripts.
-  public static final String LABEL = "1.4.12-dev";
+  public static final String LABEL = "1.4.13-dev";
 
   private Version() {
   }
diff --git a/src/main/java/com/android/tools/r8/cf/TypeVerificationHelper.java b/src/main/java/com/android/tools/r8/cf/TypeVerificationHelper.java
index 16a03e2..53907db 100644
--- a/src/main/java/com/android/tools/r8/cf/TypeVerificationHelper.java
+++ b/src/main/java/com/android/tools/r8/cf/TypeVerificationHelper.java
@@ -193,7 +193,7 @@
     if (result.isClassType()) {
       return result.asClassTypeLatticeElement().getClassType();
     } else if (result.isArrayType()) {
-      return result.asArrayTypeLatticeElement().getArrayType();
+      return result.asArrayTypeLatticeElement().getArrayType(factory);
     }
     throw new CompilationError("Unexpected join " + result + " of types: " +
         String.join(", ",
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 d79276e..5a4b204 100644
--- a/src/main/java/com/android/tools/r8/graph/DexClass.java
+++ b/src/main/java/com/android/tools/r8/graph/DexClass.java
@@ -524,4 +524,9 @@
     return getKotlinInfo() != null;
   }
 
+  public boolean isValid() {
+    assert !isInterface()
+        || Arrays.stream(virtualMethods()).noneMatch(method -> method.accessFlags.isFinal());
+    return true;
+  }
 }
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 0b07644..e9966f5 100644
--- a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
+++ b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
@@ -18,10 +18,12 @@
 import com.android.tools.r8.ir.analysis.type.ArrayTypeLatticeElement;
 import com.android.tools.r8.ir.analysis.type.ClassTypeLatticeElement;
 import com.android.tools.r8.ir.analysis.type.ReferenceTypeLatticeElement;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.Position;
 import com.android.tools.r8.kotlin.Kotlin;
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.utils.ArrayUtils;
+import com.android.tools.r8.utils.LRUCacheTable;
 import com.google.common.base.Strings;
 import com.google.common.collect.BiMap;
 import com.google.common.collect.HashBiMap;
@@ -66,6 +68,8 @@
   // ReferenceTypeLattice canonicalization.
   private final ConcurrentHashMap<DexType, ReferenceTypeLatticeElement>
       referenceTypeLatticeElements = new ConcurrentHashMap<>();
+  public final LRUCacheTable<Set<DexType>, Set<DexType>, Set<DexType>>
+      leastUpperBoundOfInterfacesTable = LRUCacheTable.create(8, 8);
 
   boolean sorted = false;
 
@@ -1009,7 +1013,10 @@
           }
         } else {
           assert type.isArrayType();
-          typeLattice = new ArrayTypeLatticeElement(type, isNullable);
+          DexType elementType = type.toArrayElementType(this);
+          TypeLatticeElement elementTypeLattice =
+              TypeLatticeElement.fromDexType(elementType, true, appInfo, true);
+          typeLattice = new ArrayTypeLatticeElement(elementTypeLattice, isNullable);
         }
         referenceTypeLatticeElements.put(type, typeLattice);
       }
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/TypeChecker.java b/src/main/java/com/android/tools/r8/ir/analysis/TypeChecker.java
index 96227c4..0da99ae 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/TypeChecker.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/TypeChecker.java
@@ -70,24 +70,22 @@
         instruction.isInstancePut()
             ? instruction.asInstancePut().value()
             : instruction.asStaticPut().inValue();
-    TypeLatticeElement fieldType =
-        TypeLatticeElement.fromDexType(instruction.getField().type, true, appInfo);
     TypeLatticeElement valueType = value.getTypeLattice();
+    TypeLatticeElement fieldType = TypeLatticeElement.fromDexType(
+        instruction.getField().type, valueType.isNullable(), appInfo);
     return isSubtypeOf(valueType, fieldType);
   }
 
   public boolean check(Throw instruction) {
-    TypeLatticeElement throwableType =
-        TypeLatticeElement.fromDexType(appInfo.dexItemFactory.throwableType, true, appInfo);
     TypeLatticeElement valueType = instruction.exception().getTypeLattice();
+    TypeLatticeElement throwableType = TypeLatticeElement.fromDexType(
+        appInfo.dexItemFactory.throwableType, valueType.isNullable(), appInfo);
     return isSubtypeOf(valueType, throwableType);
   }
 
   private boolean isSubtypeOf(
       TypeLatticeElement expectedSubtype, TypeLatticeElement expectedSupertype) {
     return expectedSubtype.lessThanOrEqual(expectedSupertype, appInfo)
-        || expectedSubtype.isBasedOnMissingClass(appInfo)
-        // TODO(b/119181813): Remove this relaxation when the join of array types is fixed.
-        || (expectedSubtype.isArrayType() && expectedSupertype.isArrayType());
+        || expectedSubtype.isBasedOnMissingClass(appInfo);
   }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/ArrayTypeLatticeElement.java b/src/main/java/com/android/tools/r8/ir/analysis/type/ArrayTypeLatticeElement.java
index 4ff54d3..6bb13a7 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/type/ArrayTypeLatticeElement.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/ArrayTypeLatticeElement.java
@@ -9,25 +9,49 @@
 
 public class ArrayTypeLatticeElement extends ReferenceTypeLatticeElement {
 
-  public ArrayTypeLatticeElement(DexType type, boolean isNullable) {
-    super(type, isNullable);
-    assert type.isArrayType();
+  private final TypeLatticeElement memberTypeLattice;
+
+  public ArrayTypeLatticeElement(TypeLatticeElement memberTypeLattice, boolean isNullable) {
+    super(isNullable, null);
+    this.memberTypeLattice = memberTypeLattice;
   }
 
-  public DexType getArrayType() {
-    return type;
+  public DexType getArrayType(DexItemFactory factory) {
+    TypeLatticeElement baseTypeLattice = getArrayBaseTypeLattice();
+    DexType baseType;
+    if (baseTypeLattice.isPrimitive()) {
+      baseType = baseTypeLattice.asPrimitiveTypeLatticeElement().toDexType(factory);
+    } else {
+      assert baseTypeLattice.isClassType();
+      baseType = baseTypeLattice.asClassTypeLatticeElement().getClassType();
+    }
+    return factory.createArrayType(getNesting(), baseType);
   }
 
-  public int getNesting() {
-    return type.getNumberOfLeadingSquareBrackets();
+  int getNesting() {
+    int nesting = 1;
+    TypeLatticeElement member = getArrayMemberTypeAsMemberType();
+    while (member.isArrayType()) {
+      ++nesting;
+      member = member.asArrayTypeLatticeElement().getArrayMemberTypeAsMemberType();
+    }
+    return nesting;
   }
 
-  public DexType getArrayElementType(DexItemFactory factory) {
-    return type.toArrayElementType(factory);
+  TypeLatticeElement getArrayMemberTypeAsMemberType() {
+    return memberTypeLattice;
   }
 
-  public DexType getArrayBaseType(DexItemFactory factory) {
-    return type.toBaseType(factory);
+  public TypeLatticeElement getArrayMemberTypeAsValueType() {
+    return memberTypeLattice.isFineGrainedType() ? INT : memberTypeLattice;
+  }
+
+  private TypeLatticeElement getArrayBaseTypeLattice() {
+    TypeLatticeElement base = getArrayMemberTypeAsMemberType();
+    while (base.isArrayType()) {
+      base = base.asArrayTypeLatticeElement().getArrayMemberTypeAsMemberType();
+    }
+    return base;
   }
 
   @Override
@@ -37,7 +61,8 @@
     }
     synchronized (this) {
       if (dual == null) {
-        ArrayTypeLatticeElement dual = new ArrayTypeLatticeElement(type, !isNullable());
+        ArrayTypeLatticeElement dual =
+            new ArrayTypeLatticeElement(memberTypeLattice, !isNullable());
         linkDualLattice(this, dual);
       }
     }
@@ -56,7 +81,7 @@
 
   @Override
   public boolean isBasedOnMissingClass(AppInfo appInfo) {
-    return getArrayBaseType(appInfo.dexItemFactory).isMissingOrHasMissingSuperType(appInfo);
+    return memberTypeLattice.isBasedOnMissingClass(appInfo);
   }
 
   @Override
@@ -70,13 +95,55 @@
   }
 
   @Override
-  public TypeLatticeElement arrayGet(AppInfo appInfo) {
-    return fromDexType(getArrayElementType(appInfo.dexItemFactory), true, appInfo);
+  public String toString() {
+    return memberTypeLattice.toString() + "[]";
+  }
+
+  @Override
+  public boolean equals(Object o) {
+    if (this == o) {
+      return true;
+    }
+    if (!(o instanceof ArrayTypeLatticeElement)) {
+      return false;
+    }
+    ArrayTypeLatticeElement other = (ArrayTypeLatticeElement) o;
+    if (isNullable() != other.isNullable()) {
+      return false;
+    }
+    if (type != null && other.type != null && !type.equals(other.type)) {
+      return false;
+    }
+    return memberTypeLattice.equals(other.memberTypeLattice);
   }
 
   @Override
   public int hashCode() {
-    return (isNullable() ? 1 : -1) * type.hashCode();
+    return (isNullable() ? 1 : -1) * memberTypeLattice.hashCode();
+  }
+
+  ReferenceTypeLatticeElement join(ArrayTypeLatticeElement other, AppInfo appInfo) {
+    TypeLatticeElement aMember = getArrayMemberTypeAsMemberType();
+    TypeLatticeElement bMember = other.getArrayMemberTypeAsMemberType();
+    if (aMember.equals(bMember)) {
+      // Return null indicating the join is the same as the member to avoid object allocation.
+      return null;
+    }
+    boolean isNullable = isNullable() || other.isNullable();
+    if (aMember.isArrayType() && bMember.isArrayType()) {
+      ReferenceTypeLatticeElement join =
+          aMember.asArrayTypeLatticeElement().join(bMember.asArrayTypeLatticeElement(), appInfo);
+      return join == null ? null : new ArrayTypeLatticeElement(join, isNullable);
+    }
+    if (aMember.isClassType() && bMember.isClassType()) {
+      ClassTypeLatticeElement join =
+          aMember.asClassTypeLatticeElement().join(bMember.asClassTypeLatticeElement(), appInfo);
+      return join == null ? null : new ArrayTypeLatticeElement(join, isNullable);
+    }
+    if (aMember.isPrimitive() || bMember.isPrimitive()) {
+      return objectClassType(appInfo, isNullable);
+    }
+    return objectArrayType(appInfo, isNullable);
   }
 
 }
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/BooleanTypeLatticeElement.java b/src/main/java/com/android/tools/r8/ir/analysis/type/BooleanTypeLatticeElement.java
new file mode 100644
index 0000000..abcdb9e
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/BooleanTypeLatticeElement.java
@@ -0,0 +1,32 @@
+// Copyright (c) 2018, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.ir.analysis.type;
+
+public class BooleanTypeLatticeElement extends PrimitiveTypeLatticeElement {
+  private static final BooleanTypeLatticeElement INSTANCE = new BooleanTypeLatticeElement();
+
+  static BooleanTypeLatticeElement getInstance() {
+    return INSTANCE;
+  }
+
+  @Override
+  boolean isBoolean() {
+    return true;
+  }
+
+  @Override
+  public String toString() {
+    return "BOOLEAN";
+  }
+
+  @Override
+  public boolean equals(Object o) {
+    return this == o;
+  }
+
+  @Override
+  public int hashCode() {
+    return System.identityHashCode(INSTANCE);
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/BottomTypeLatticeElement.java b/src/main/java/com/android/tools/r8/ir/analysis/type/BottomTypeLatticeElement.java
index 6931b46..e86d66f 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/type/BottomTypeLatticeElement.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/BottomTypeLatticeElement.java
@@ -28,11 +28,6 @@
   }
 
   @Override
-  public TypeLatticeElement arrayGet(AppInfo appInfo) {
-    return this;
-  }
-
-  @Override
   public TypeLatticeElement checkCast(AppInfo appInfo, DexType castType) {
     return this;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/ByteTypeLatticeElement.java b/src/main/java/com/android/tools/r8/ir/analysis/type/ByteTypeLatticeElement.java
new file mode 100644
index 0000000..d05c25e
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/ByteTypeLatticeElement.java
@@ -0,0 +1,32 @@
+// Copyright (c) 2018, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.ir.analysis.type;
+
+public class ByteTypeLatticeElement extends PrimitiveTypeLatticeElement {
+  private static final ByteTypeLatticeElement INSTANCE = new ByteTypeLatticeElement();
+
+  static ByteTypeLatticeElement getInstance() {
+    return INSTANCE;
+  }
+
+  @Override
+  boolean isByte() {
+    return true;
+  }
+
+  @Override
+  public String toString() {
+    return "BYTE";
+  }
+
+  @Override
+  public boolean equals(Object o) {
+    return this == o;
+  }
+
+  @Override
+  public int hashCode() {
+    return System.identityHashCode(INSTANCE);
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/CharTypeLatticeElement.java b/src/main/java/com/android/tools/r8/ir/analysis/type/CharTypeLatticeElement.java
new file mode 100644
index 0000000..27834aa
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/CharTypeLatticeElement.java
@@ -0,0 +1,32 @@
+// Copyright (c) 2018, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.ir.analysis.type;
+
+public class CharTypeLatticeElement extends PrimitiveTypeLatticeElement {
+  private static final CharTypeLatticeElement INSTANCE = new CharTypeLatticeElement();
+
+  static CharTypeLatticeElement getInstance() {
+    return INSTANCE;
+  }
+
+  @Override
+  boolean isChar() {
+    return true;
+  }
+
+  @Override
+  public String toString() {
+    return "BYTE";
+  }
+
+  @Override
+  public boolean equals(Object o) {
+    return this == o;
+  }
+
+  @Override
+  public int hashCode() {
+    return System.identityHashCode(INSTANCE);
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/ClassTypeLatticeElement.java b/src/main/java/com/android/tools/r8/ir/analysis/type/ClassTypeLatticeElement.java
index 84146a2..c25395d 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/type/ClassTypeLatticeElement.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/ClassTypeLatticeElement.java
@@ -4,7 +4,14 @@
 package com.android.tools.r8.ir.analysis.type;
 
 import com.android.tools.r8.graph.AppInfo;
+import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexType;
+import com.google.common.collect.ImmutableSet;
+import java.util.ArrayDeque;
+import java.util.HashSet;
+import java.util.IdentityHashMap;
+import java.util.Map;
+import java.util.Queue;
 import java.util.Set;
 import java.util.stream.Collectors;
 
@@ -23,7 +30,7 @@
 
   private ClassTypeLatticeElement(
       DexType classType, boolean isNullable, Set<DexType> interfaces, AppInfo appInfo) {
-    super(classType, isNullable);
+    super(isNullable, classType);
     assert classType.isClassType();
     appInfoForLazyInterfacesComputation = appInfo;
     lazyInterfaces = interfaces;
@@ -42,8 +49,7 @@
       if (lazyInterfaces == null) {
         Set<DexType> itfs = type.implementedInterfaces(appInfoForLazyInterfacesComputation);
         lazyInterfaces =
-            TypeLatticeElement.computeLeastUpperBoundOfInterfaces(
-                appInfoForLazyInterfacesComputation, itfs, itfs);
+            computeLeastUpperBoundOfInterfaces(appInfoForLazyInterfacesComputation, itfs, itfs);
         appInfoForLazyInterfacesComputation = null;
       }
     }
@@ -96,10 +102,10 @@
   public String toString() {
     StringBuilder builder = new StringBuilder();
     builder.append(super.toString());
-    builder.append(" [");
+    builder.append(" {");
     builder.append(
         getInterfaces().stream().map(DexType::toString).collect(Collectors.joining(", ")));
-    builder.append("]");
+    builder.append("}");
     return builder.toString();
   }
 
@@ -108,4 +114,115 @@
     // The interfaces of a type do not contribute to its hashCode as they are lazily computed.
     return (isNullable() ? 1 : -1) * type.hashCode();
   }
+
+  ClassTypeLatticeElement join(ClassTypeLatticeElement other, AppInfo appInfo) {
+    DexType lubType = getClassType().computeLeastUpperBoundOfClasses(appInfo, other.getClassType());
+    Set<DexType> c1lubItfs = getInterfaces();
+    Set<DexType> c2lubItfs = other.getInterfaces();
+    Set<DexType> lubItfs = null;
+    if (c1lubItfs.size() == c2lubItfs.size() && c1lubItfs.containsAll(c2lubItfs)) {
+      lubItfs = c1lubItfs;
+    }
+    if (lubItfs == null) {
+      lubItfs = computeLeastUpperBoundOfInterfaces(appInfo, c1lubItfs, c2lubItfs);
+    }
+    boolean isNullable = isNullable() || other.isNullable();
+    return new ClassTypeLatticeElement(lubType, isNullable, lubItfs);
+  }
+
+  private enum InterfaceMarker {
+    LEFT,
+    RIGHT
+  }
+
+  private static class InterfaceWithMarker {
+    final DexType itf;
+    final InterfaceMarker marker;
+
+    InterfaceWithMarker(DexType itf, InterfaceMarker marker) {
+      this.itf = itf;
+      this.marker = marker;
+    }
+  }
+
+  static Set<DexType> computeLeastUpperBoundOfInterfaces(
+      AppInfo appInfo, Set<DexType> s1, Set<DexType> s2) {
+    Set<DexType> cached = appInfo.dexItemFactory.leastUpperBoundOfInterfacesTable.get(s1, s2);
+    if (cached != null) {
+      return cached;
+    }
+    cached = appInfo.dexItemFactory.leastUpperBoundOfInterfacesTable.get(s2, s1);
+    if (cached != null) {
+      return cached;
+    }
+    Map<DexType, Set<InterfaceMarker>> seen = new IdentityHashMap<>();
+    Queue<InterfaceWithMarker> worklist = new ArrayDeque<>();
+    for (DexType itf1 : s1) {
+      worklist.add(new InterfaceWithMarker(itf1, InterfaceMarker.LEFT));
+    }
+    for (DexType itf2 : s2) {
+      worklist.add(new InterfaceWithMarker(itf2, InterfaceMarker.RIGHT));
+    }
+    while (!worklist.isEmpty()) {
+      InterfaceWithMarker item = worklist.poll();
+      DexType itf = item.itf;
+      InterfaceMarker marker = item.marker;
+      Set<InterfaceMarker> markers = seen.computeIfAbsent(itf, k -> new HashSet<>());
+      // If this interface is a lower one in this set, skip.
+      if (markers.contains(marker)) {
+        continue;
+      }
+      // If this interface is already visited by the other set, add marker for this set and skip.
+      if (markers.size() == 1) {
+        markers.add(marker);
+        continue;
+      }
+      // Otherwise, this type is freshly visited.
+      markers.add(marker);
+      // Put super interfaces into the worklist.
+      DexClass itfClass = appInfo.definitionFor(itf);
+      if (itfClass != null) {
+        for (DexType superItf : itfClass.interfaces.values) {
+          markers = seen.computeIfAbsent(superItf, k -> new HashSet<>());
+          if (!markers.contains(marker)) {
+            worklist.add(new InterfaceWithMarker(superItf, marker));
+          }
+        }
+      }
+    }
+
+    ImmutableSet.Builder<DexType> commonBuilder = ImmutableSet.builder();
+    for (Map.Entry<DexType, Set<InterfaceMarker>> entry : seen.entrySet()) {
+      // Keep commonly visited interfaces only
+      if (entry.getValue().size() < 2) {
+        continue;
+      }
+      commonBuilder.add(entry.getKey());
+    }
+    Set<DexType> commonlyVisited = commonBuilder.build();
+
+    ImmutableSet.Builder<DexType> lubBuilder = ImmutableSet.builder();
+    for (DexType itf : commonlyVisited) {
+      // If there is a strict sub interface of this interface, it is not the least element.
+      boolean notTheLeast = false;
+      for (DexType other : commonlyVisited) {
+        if (other.isStrictSubtypeOf(itf, appInfo)) {
+          notTheLeast = true;
+          break;
+        }
+      }
+      if (notTheLeast) {
+        continue;
+      }
+      lubBuilder.add(itf);
+    }
+    Set<DexType> lub = lubBuilder.build();
+    // Cache the computation result only if the given two sets of interfaces are different.
+    if (s1.size() != s2.size() || !s1.containsAll(s2)) {
+      synchronized (appInfo.dexItemFactory.leastUpperBoundOfInterfacesTable) {
+        appInfo.dexItemFactory.leastUpperBoundOfInterfacesTable.put(s1, s2, lub);
+      }
+    }
+    return lub;
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/PrimitiveTypeLatticeElement.java b/src/main/java/com/android/tools/r8/ir/analysis/type/PrimitiveTypeLatticeElement.java
index 51097d8..4c633f5 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/type/PrimitiveTypeLatticeElement.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/PrimitiveTypeLatticeElement.java
@@ -5,6 +5,7 @@
 
 import com.android.tools.r8.errors.InternalCompilerError;
 import com.android.tools.r8.errors.Unreachable;
+import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.ir.code.NumericType;
 
@@ -32,17 +33,62 @@
     return this;
   }
 
-  public static PrimitiveTypeLatticeElement fromDexType(DexType type) {
+  static PrimitiveTypeLatticeElement fromDexType(DexType type, boolean asArrayElementType) {
     assert type.isPrimitiveType();
-    return fromTypeDescriptorChar((char) type.descriptor.content[0]);
+    return fromTypeDescriptorChar((char) type.descriptor.content[0], asArrayElementType);
   }
 
-  public static PrimitiveTypeLatticeElement fromTypeDescriptorChar(char descriptor) {
+  DexType toDexType(DexItemFactory factory) {
+    if (isBoolean()) {
+      return factory.booleanType;
+    }
+    if (isByte()) {
+      return factory.byteType;
+    }
+    if (isShort()) {
+      return factory.shortType;
+    }
+    if (isChar()) {
+      return factory.charType;
+    }
+    if (isInt()) {
+      return factory.intType;
+    }
+    if (isFloat()) {
+      return factory.floatType;
+    }
+    if (isLong()) {
+      return factory.longType;
+    }
+    if (isDouble()) {
+      return factory.doubleType;
+    }
+    throw new Unreachable("Imprecise primitive type '" + toString() + "'");
+  }
+
+  private static PrimitiveTypeLatticeElement fromTypeDescriptorChar(
+      char descriptor, boolean asArrayElementType) {
     switch (descriptor) {
       case 'Z':
+        if (asArrayElementType) {
+          return TypeLatticeElement.BOOLEAN;
+        }
+        // fall through
       case 'B':
+        if (asArrayElementType) {
+          return TypeLatticeElement.BYTE;
+        }
+        // fall through
       case 'S':
+        if (asArrayElementType) {
+          return TypeLatticeElement.SHORT;
+        }
+        // fall through
       case 'C':
+        if (asArrayElementType) {
+          return TypeLatticeElement.CHAR;
+        }
+        // fall through
       case 'I':
         return TypeLatticeElement.INT;
       case 'F':
@@ -76,23 +122,22 @@
     }
   }
 
-  public static TypeLatticeElement join(
-      PrimitiveTypeLatticeElement t1, PrimitiveTypeLatticeElement t2) {
-    if (t1 == t2) {
-      return t1;
+  TypeLatticeElement join(PrimitiveTypeLatticeElement other) {
+    if (this == other) {
+      return this;
     }
-    if (t1.isSingle()) {
-      if (t2.isSingle()) {
+    if (isSingle()) {
+      if (other.isSingle()) {
         return TypeLatticeElement.SINGLE;
       }
-      assert t2.isWide();
+      assert other.isWide();
       return TypeLatticeElement.TOP;
     }
-    assert t1.isWide();
-    if (t2.isWide()) {
+    assert isWide();
+    if (other.isWide()) {
       return TypeLatticeElement.WIDE;
     }
-    assert t2.isSingle();
+    assert other.isSingle();
     return TypeLatticeElement.TOP;
   }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/ReferenceTypeLatticeElement.java b/src/main/java/com/android/tools/r8/ir/analysis/type/ReferenceTypeLatticeElement.java
index 423c8cc..e7282e1 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/type/ReferenceTypeLatticeElement.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/ReferenceTypeLatticeElement.java
@@ -11,8 +11,9 @@
 
 public class ReferenceTypeLatticeElement extends TypeLatticeElement {
   private static final ReferenceTypeLatticeElement NULL_INSTANCE =
-      new ReferenceTypeLatticeElement(DexItemFactory.nullValueType, true);
+      new ReferenceTypeLatticeElement(true, DexItemFactory.nullValueType);
 
+  // TODO(b/72693244): Consider moving this to ClassTypeLatticeElement.
   final DexType type;
 
   // Link between maybe-null and definitely-not-null reference type lattices.
@@ -28,7 +29,7 @@
     t2.dual = t1;
   }
 
-  ReferenceTypeLatticeElement(DexType type, boolean isNullable) {
+  ReferenceTypeLatticeElement(boolean isNullable, DexType type) {
     super(isNullable);
     this.type = type;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/ShortTypeLatticeElement.java b/src/main/java/com/android/tools/r8/ir/analysis/type/ShortTypeLatticeElement.java
new file mode 100644
index 0000000..6b56f08
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/ShortTypeLatticeElement.java
@@ -0,0 +1,32 @@
+// Copyright (c) 2018, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.ir.analysis.type;
+
+public class ShortTypeLatticeElement extends PrimitiveTypeLatticeElement {
+  private static final ShortTypeLatticeElement INSTANCE = new ShortTypeLatticeElement();
+
+  static ShortTypeLatticeElement getInstance() {
+    return INSTANCE;
+  }
+
+  @Override
+  boolean isShort() {
+    return true;
+  }
+
+  @Override
+  public String toString() {
+    return "SHORT";
+  }
+
+  @Override
+  public boolean equals(Object o) {
+    return this == o;
+  }
+
+  @Override
+  public int hashCode() {
+    return System.identityHashCode(INSTANCE);
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/TopTypeLatticeElement.java b/src/main/java/com/android/tools/r8/ir/analysis/type/TopTypeLatticeElement.java
index 4ffe7b1..5221ae3 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/type/TopTypeLatticeElement.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/TopTypeLatticeElement.java
@@ -28,11 +28,6 @@
   }
 
   @Override
-  public TypeLatticeElement arrayGet(AppInfo appInfo) {
-    return this;
-  }
-
-  @Override
   public TypeLatticeElement checkCast(AppInfo appInfo, DexType castType) {
     return this;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/TypeLatticeElement.java b/src/main/java/com/android/tools/r8/ir/analysis/type/TypeLatticeElement.java
index 7b1e28a..b29cd31 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/type/TypeLatticeElement.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/TypeLatticeElement.java
@@ -5,19 +5,10 @@
 
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.AppInfo;
-import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.ir.code.NumericType;
 import com.android.tools.r8.ir.code.Value;
-import com.android.tools.r8.utils.LRUCacheTable;
-import com.google.common.collect.ImmutableSet;
-import java.util.ArrayDeque;
-import java.util.HashSet;
-import java.util.IdentityHashMap;
-import java.util.Map;
-import java.util.Queue;
-import java.util.Set;
 
 /**
  * The base abstraction of lattice elements for local type analysis.
@@ -25,6 +16,10 @@
 public abstract class TypeLatticeElement {
   public static final BottomTypeLatticeElement BOTTOM = BottomTypeLatticeElement.getInstance();
   public static final TopTypeLatticeElement TOP = TopTypeLatticeElement.getInstance();
+  static final BooleanTypeLatticeElement BOOLEAN = BooleanTypeLatticeElement.getInstance();
+  static final ByteTypeLatticeElement BYTE = ByteTypeLatticeElement.getInstance();
+  static final ShortTypeLatticeElement SHORT = ShortTypeLatticeElement.getInstance();
+  static final CharTypeLatticeElement CHAR = CharTypeLatticeElement.getInstance();
   public static final IntTypeLatticeElement INT = IntTypeLatticeElement.getInstance();
   public static final FloatTypeLatticeElement FLOAT = FloatTypeLatticeElement.getInstance();
   public static final SingleTypeLatticeElement SINGLE = SingleTypeLatticeElement.getInstance();
@@ -34,8 +29,6 @@
   public static final ReferenceTypeLatticeElement NULL =
       ReferenceTypeLatticeElement.getNullTypeLatticeElement();
 
-  private static final LRUCacheTable<Set<DexType>, Set<DexType>, Set<DexType>>
-      leastUpperBoundOfInterfacesTable = LRUCacheTable.create(8, 8);
 
   // TODO(b/72693244): Switch to NullLatticeElement.
   private final boolean isNullable;
@@ -106,8 +99,7 @@
     }
     if (isPrimitive()) {
       return other.isPrimitive()
-          ? PrimitiveTypeLatticeElement.join(
-              asPrimitiveTypeLatticeElement(), other.asPrimitiveTypeLatticeElement())
+          ? asPrimitiveTypeLatticeElement().join(other.asPrimitiveTypeLatticeElement())
           : TOP;
     }
     if (other.isPrimitive()) {
@@ -124,157 +116,17 @@
     // From now on, getClass() == other.getClass()
     if (isArrayType()) {
       assert other.isArrayType();
-      ArrayTypeLatticeElement a1 = asArrayTypeLatticeElement();
-      ArrayTypeLatticeElement a2 = other.asArrayTypeLatticeElement();
-      // Identical types are the same elements
-      if (a1.getArrayType() == a2.getArrayType()) {
-        return a1.isNullable() ? a1 : a2;
-      }
-      // If non-equal, find the inner-most reference types for each.
-      DexType a1BaseReferenceType = a1.getArrayBaseType(appInfo.dexItemFactory);
-      int a1Nesting = a1.getNesting();
-      if (a1BaseReferenceType.isPrimitiveType()) {
-        a1Nesting--;
-        a1BaseReferenceType = appInfo.dexItemFactory.objectType;
-      }
-      DexType a2BaseReferenceType = a2.getArrayBaseType(appInfo.dexItemFactory);
-      int a2Nesting = a2.getNesting();
-      if (a2BaseReferenceType.isPrimitiveType()) {
-        a2Nesting--;
-        a2BaseReferenceType = appInfo.dexItemFactory.objectType;
-      }
-      assert a1BaseReferenceType.isClassType() && a2BaseReferenceType.isClassType();
-      // If any nestings hit zero object is the join.
-      if (a1Nesting == 0 || a2Nesting == 0) {
-        return objectClassType(appInfo, isNullable);
-      }
-      // If the nestings differ the join is the smallest nesting level.
-      if (a1Nesting != a2Nesting) {
-        int min = Math.min(a1Nesting, a2Nesting);
-        return objectArrayType(appInfo, min, isNullable);
-      }
-      // For different class element types, compute the least upper bound of element types.
-      DexType baseTypeLub =
-          a1BaseReferenceType.computeLeastUpperBoundOfClasses(appInfo, a2BaseReferenceType);
-      // Create the full array type.
-      DexType arrayTypeLub = appInfo.dexItemFactory.createArrayType(a1Nesting, baseTypeLub);
-      return fromDexType(arrayTypeLub, isNullable, appInfo);
+      TypeLatticeElement join =
+          asArrayTypeLatticeElement().join(other.asArrayTypeLatticeElement(), appInfo);
+      return join != null ? join : (isNullable() ? this : other);
     }
     if (isClassType()) {
       assert other.isClassType();
-      ClassTypeLatticeElement c1 = asClassTypeLatticeElement();
-      ClassTypeLatticeElement c2 = other.asClassTypeLatticeElement();
-      DexType lubType =
-          c1.getClassType().computeLeastUpperBoundOfClasses(appInfo, c2.getClassType());
-      Set<DexType> c1lubItfs = c1.getInterfaces();
-      Set<DexType> c2lubItfs = c2.getInterfaces();
-      Set<DexType> lubItfs = null;
-      if (c1lubItfs.size() == c2lubItfs.size() && c1lubItfs.containsAll(c2lubItfs)) {
-        lubItfs = c1lubItfs;
-      }
-      if (lubItfs == null) {
-        lubItfs = computeLeastUpperBoundOfInterfaces(appInfo, c1lubItfs, c2lubItfs);
-      }
-      return new ClassTypeLatticeElement(lubType, isNullable, lubItfs);
+      return asClassTypeLatticeElement().join(other.asClassTypeLatticeElement(), appInfo);
     }
     throw new Unreachable("unless a new type lattice is introduced.");
   }
 
-  private enum InterfaceMarker {
-    LEFT,
-    RIGHT
-  }
-
-  private static class InterfaceWithMarker {
-    final DexType itf;
-    final InterfaceMarker marker;
-
-    InterfaceWithMarker(DexType itf, InterfaceMarker marker) {
-      this.itf = itf;
-      this.marker = marker;
-    }
-  }
-
-  public static Set<DexType> computeLeastUpperBoundOfInterfaces(
-      AppInfo appInfo, Set<DexType> s1, Set<DexType> s2) {
-    Set<DexType> cached = leastUpperBoundOfInterfacesTable.get(s1, s2);
-    if (cached != null) {
-      return cached;
-    }
-    cached = leastUpperBoundOfInterfacesTable.get(s2, s1);
-    if (cached != null) {
-      return cached;
-    }
-    Map<DexType, Set<InterfaceMarker>> seen = new IdentityHashMap<>();
-    Queue<InterfaceWithMarker> worklist = new ArrayDeque<>();
-    for (DexType itf1 : s1) {
-      worklist.add(new InterfaceWithMarker(itf1, InterfaceMarker.LEFT));
-    }
-    for (DexType itf2 : s2) {
-      worklist.add(new InterfaceWithMarker(itf2, InterfaceMarker.RIGHT));
-    }
-    while (!worklist.isEmpty()) {
-      InterfaceWithMarker item = worklist.poll();
-      DexType itf = item.itf;
-      InterfaceMarker marker = item.marker;
-      Set<InterfaceMarker> markers = seen.computeIfAbsent(itf, k -> new HashSet<>());
-      // If this interface is a lower one in this set, skip.
-      if (markers.contains(marker)) {
-        continue;
-      }
-      // If this interface is already visited by the other set, add marker for this set and skip.
-      if (markers.size() == 1) {
-        markers.add(marker);
-        continue;
-      }
-      // Otherwise, this type is freshly visited.
-      markers.add(marker);
-      // Put super interfaces into the worklist.
-      DexClass itfClass = appInfo.definitionFor(itf);
-      if (itfClass != null) {
-        for (DexType superItf : itfClass.interfaces.values) {
-          markers = seen.computeIfAbsent(superItf, k -> new HashSet<>());
-          if (!markers.contains(marker)) {
-            worklist.add(new InterfaceWithMarker(superItf, marker));
-          }
-        }
-      }
-    }
-
-    ImmutableSet.Builder<DexType> commonBuilder = ImmutableSet.builder();
-    for (Map.Entry<DexType, Set<InterfaceMarker>> entry : seen.entrySet()) {
-      // Keep commonly visited interfaces only
-      if (entry.getValue().size() < 2) {
-        continue;
-      }
-      commonBuilder.add(entry.getKey());
-    }
-    Set<DexType> commonlyVisited = commonBuilder.build();
-
-    ImmutableSet.Builder<DexType> lubBuilder = ImmutableSet.builder();
-    for (DexType itf : commonlyVisited) {
-      // If there is a strict sub interface of this interface, it is not the least element.
-      boolean notTheLeast = false;
-      for (DexType other : commonlyVisited) {
-        if (other.isStrictSubtypeOf(itf, appInfo)) {
-          notTheLeast = true;
-          break;
-        }
-      }
-      if (notTheLeast) {
-        continue;
-      }
-      lubBuilder.add(itf);
-    }
-    Set<DexType> lub = lubBuilder.build();
-    // Cache the computation result only if the given two sets of interfaces are different.
-    if (s1.size() != s2.size() || !s1.containsAll(s2)) {
-      synchronized (leastUpperBoundOfInterfacesTable) {
-        leastUpperBoundOfInterfacesTable.put(s1, s2, lub);
-      }
-    }
-    return lub;
-  }
 
   public static TypeLatticeElement join(
       Iterable<TypeLatticeElement> typeLattices, AppInfo appInfo) {
@@ -383,6 +235,22 @@
     return false;
   }
 
+  boolean isBoolean() {
+    return false;
+  }
+
+  boolean isByte() {
+    return false;
+  }
+
+  boolean isShort() {
+    return false;
+  }
+
+  boolean isChar() {
+    return false;
+  }
+
   public boolean isInt() {
     return false;
   }
@@ -410,6 +278,13 @@
         || isBottom();
   }
 
+  public boolean isFineGrainedType() {
+    return isBoolean()
+        || isByte()
+        || isShort()
+        || isChar();
+  }
+
   /**
    * Should use {@link #isConstantNull()} or {@link #isDefinitelyNull()} instead.
    */
@@ -444,14 +319,17 @@
     return isWide() ? 2 : 1;
   }
 
-  static TypeLatticeElement objectClassType(AppInfo appInfo, boolean isNullable) {
-    return fromDexType(appInfo.dexItemFactory.objectType, isNullable, appInfo);
+  static ClassTypeLatticeElement objectClassType(AppInfo appInfo, boolean isNullable) {
+    return fromDexType(appInfo.dexItemFactory.objectType, isNullable, appInfo)
+        .asClassTypeLatticeElement();
   }
 
-  static TypeLatticeElement objectArrayType(AppInfo appInfo, int nesting, boolean isNullable) {
+  static ArrayTypeLatticeElement objectArrayType(AppInfo appInfo, boolean isNullable) {
     return fromDexType(
-        appInfo.dexItemFactory.createArrayType(nesting, appInfo.dexItemFactory.objectType),
-        isNullable, appInfo);
+        appInfo.dexItemFactory.createArrayType(1, appInfo.dexItemFactory.objectType),
+        isNullable,
+        appInfo)
+        .asArrayTypeLatticeElement();
   }
 
   public static TypeLatticeElement classClassType(AppInfo appInfo) {
@@ -463,11 +341,16 @@
   }
 
   public static TypeLatticeElement fromDexType(DexType type, boolean isNullable, AppInfo appInfo) {
+    return fromDexType(type, isNullable, appInfo, false);
+  }
+
+  public static TypeLatticeElement fromDexType(
+      DexType type, boolean isNullable, AppInfo appInfo, boolean asArrayElementType) {
     if (type == DexItemFactory.nullValueType) {
       return NULL;
     }
     if (type.isPrimitiveType()) {
-      return PrimitiveTypeLatticeElement.fromDexType(type);
+      return PrimitiveTypeLatticeElement.fromDexType(type, asArrayElementType);
     }
     return appInfo.dexItemFactory.createReferenceTypeLatticeElement(type, isNullable, appInfo);
   }
@@ -496,14 +379,6 @@
         || (isWide() && other.isWide());
   }
 
-  public static TypeLatticeElement newArray(DexType arrayType, boolean isNullable) {
-    return new ArrayTypeLatticeElement(arrayType, isNullable);
-  }
-
-  public TypeLatticeElement arrayGet(AppInfo appInfo) {
-    return BOTTOM;
-  }
-
   public TypeLatticeElement checkCast(AppInfo appInfo, DexType castType) {
     TypeLatticeElement castTypeLattice = fromDexType(castType, isNullable(), appInfo);
     if (lessThanOrEqual(castTypeLattice, appInfo)) {
diff --git a/src/main/java/com/android/tools/r8/ir/code/ArrayGet.java b/src/main/java/com/android/tools/r8/ir/code/ArrayGet.java
index 2549eaa..3879639 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ArrayGet.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ArrayGet.java
@@ -19,6 +19,7 @@
 import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.ArrayTypeLatticeElement;
 import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
@@ -170,29 +171,47 @@
 
   @Override
   public TypeLatticeElement evaluate(AppInfo appInfo) {
+    ArrayTypeLatticeElement arrayTypeLattice = array().getTypeLattice().isArrayType()
+        ? array().getTypeLattice().asArrayTypeLatticeElement()
+        : null;
     switch (getMemberType()) {
       case OBJECT:
         // If the out-type of the array is bottom (the input array must be definitely null), then
         // the instruction cannot return. For now we return NULL as the type to ensure we have a
         // type consistent witness for the out-value type. We could consider returning bottom in
         // this case as the value is indeed empty, i.e., the instruction will always fail.
-        TypeLatticeElement outType = array().getTypeLattice().arrayGet(appInfo);
-        return outType.isBottom() ? TypeLatticeElement.NULL : outType;
+        TypeLatticeElement valueType = arrayTypeLattice == null
+            ? TypeLatticeElement.NULL
+            : arrayTypeLattice.getArrayMemberTypeAsValueType();
+        assert valueType.isReference();
+        return valueType;
       case BOOLEAN:
       case BYTE:
       case CHAR:
       case SHORT:
       case INT:
+        assert arrayTypeLattice == null
+            || arrayTypeLattice.getArrayMemberTypeAsValueType().isInt();
         return TypeLatticeElement.INT;
       case FLOAT:
+        assert arrayTypeLattice == null
+            || arrayTypeLattice.getArrayMemberTypeAsValueType().isFloat();
         return TypeLatticeElement.FLOAT;
       case LONG:
+        assert arrayTypeLattice == null
+            || arrayTypeLattice.getArrayMemberTypeAsValueType().isLong();
         return TypeLatticeElement.LONG;
       case DOUBLE:
+        assert arrayTypeLattice == null
+            || arrayTypeLattice.getArrayMemberTypeAsValueType().isDouble();
         return TypeLatticeElement.DOUBLE;
       case INT_OR_FLOAT:
+        assert arrayTypeLattice == null
+            || arrayTypeLattice.getArrayMemberTypeAsValueType().isSingle();
         return checkConstraint(dest(), ValueTypeConstraint.INT_OR_FLOAT);
       case LONG_OR_DOUBLE:
+        assert arrayTypeLattice == null
+            || arrayTypeLattice.getArrayMemberTypeAsValueType().isWide();
         return checkConstraint(dest(), ValueTypeConstraint.LONG_OR_DOUBLE);
       default:
         throw new Unreachable("Unexpected member type: " + getMemberType());
diff --git a/src/main/java/com/android/tools/r8/ir/code/IRCode.java b/src/main/java/com/android/tools/r8/ir/code/IRCode.java
index e11f1bd..6022b6d 100644
--- a/src/main/java/com/android/tools/r8/ir/code/IRCode.java
+++ b/src/main/java/com/android/tools/r8/ir/code/IRCode.java
@@ -679,6 +679,7 @@
     return verifySSATypeLattice(
         v -> {
           assert v.getTypeLattice().isPreciseType();
+          assert !v.getTypeLattice().isFineGrainedType();
           // For now we assume no bottom types on IR values. We may want to reconsider this for
           // representing unreachable code.
           assert !v.getTypeLattice().isBottom();
diff --git a/src/main/java/com/android/tools/r8/ir/code/Instruction.java b/src/main/java/com/android/tools/r8/ir/code/Instruction.java
index 3738542..a008185 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Instruction.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Instruction.java
@@ -1208,7 +1208,7 @@
         DexType outBaseType =
             outTypeLatticeElement
                 .asArrayTypeLatticeElement()
-                .getArrayType()
+                .getArrayType(appInfo.dexItemFactory)
                 .toBaseType(appInfo.dexItemFactory);
         assert graphLense.lookupType(outBaseType) == outBaseType;
       } else if (outTypeLatticeElement.isClassType()) {
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeMultiNewArray.java b/src/main/java/com/android/tools/r8/ir/code/InvokeMultiNewArray.java
index cfd3b1d..2f28110 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeMultiNewArray.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeMultiNewArray.java
@@ -67,7 +67,7 @@
 
   @Override
   public TypeLatticeElement evaluate(AppInfo appInfo) {
-    return TypeLatticeElement.newArray(type, false);
+    return TypeLatticeElement.fromDexType(type, false, appInfo);
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeNewArray.java b/src/main/java/com/android/tools/r8/ir/code/InvokeNewArray.java
index df74e17..c49650a 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeNewArray.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeNewArray.java
@@ -97,7 +97,7 @@
 
   @Override
   public TypeLatticeElement evaluate(AppInfo appInfo) {
-    return TypeLatticeElement.newArray(type, false);
+    return TypeLatticeElement.fromDexType(type, false, appInfo);
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/ir/code/NewArrayEmpty.java b/src/main/java/com/android/tools/r8/ir/code/NewArrayEmpty.java
index 95a9225..09ea5af 100644
--- a/src/main/java/com/android/tools/r8/ir/code/NewArrayEmpty.java
+++ b/src/main/java/com/android/tools/r8/ir/code/NewArrayEmpty.java
@@ -107,6 +107,6 @@
 
   @Override
   public TypeLatticeElement evaluate(AppInfo appInfo) {
-    return TypeLatticeElement.newArray(type, false);
+    return TypeLatticeElement.fromDexType(type, false, appInfo);
   }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/ValueTypeConstraint.java b/src/main/java/com/android/tools/r8/ir/code/ValueTypeConstraint.java
index 8371375..9c376fb 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ValueTypeConstraint.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ValueTypeConstraint.java
@@ -134,7 +134,7 @@
     if (typeLatticeElement.isReference()) {
       return OBJECT;
     }
-    if (typeLatticeElement.isInt()) {
+    if (typeLatticeElement.isFineGrainedType() || typeLatticeElement.isInt()) {
       return INT;
     }
     if (typeLatticeElement.isFloat()) {
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 38842da..bdee0ac 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
@@ -56,6 +56,7 @@
 import com.android.tools.r8.ir.optimize.Outliner;
 import com.android.tools.r8.ir.optimize.PeepholeOptimizer;
 import com.android.tools.r8.ir.optimize.RedundantFieldLoadElimination;
+import com.android.tools.r8.ir.optimize.ReflectionOptimizer;
 import com.android.tools.r8.ir.optimize.UninstantiatedTypeOptimization;
 import com.android.tools.r8.ir.optimize.classinliner.ClassInliner;
 import com.android.tools.r8.ir.optimize.lambda.LambdaMerger;
@@ -904,7 +905,7 @@
 
     if (appInfo.hasLiveness()) {
       // Reflection optimization 1. getClass() -> const-class
-      codeRewriter.rewriteGetClass(code);
+      ReflectionOptimizer.rewriteGetClass(appInfo.withLiveness(), code);
     }
 
     if (!isDebugMode) {
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/TypeConstraintResolver.java b/src/main/java/com/android/tools/r8/ir/conversion/TypeConstraintResolver.java
index f2fe507..1ed85c4 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/TypeConstraintResolver.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/TypeConstraintResolver.java
@@ -180,8 +180,7 @@
     if (array.getTypeLattice().isArrayType()) {
       // If the array type is known it uniquely defines the actual member type.
       ArrayTypeLatticeElement arrayType = array.getTypeLattice().asArrayTypeLatticeElement();
-      constraint =
-          ValueTypeConstraint.fromDexType(arrayType.getArrayElementType(builder.getFactory()));
+      constraint = ValueTypeConstraint.fromTypeLattice(arrayType.getArrayMemberTypeAsValueType());
     } else {
       // If not, e.g., the array input is null, the canonical value determines the final type.
       constraint = getCanonicalTypeConstraint(canonical, true);
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java b/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
index 98ee72c..18c31ed 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
@@ -47,7 +47,6 @@
 import com.android.tools.r8.ir.code.CheckCast;
 import com.android.tools.r8.ir.code.Cmp;
 import com.android.tools.r8.ir.code.Cmp.Bias;
-import com.android.tools.r8.ir.code.ConstClass;
 import com.android.tools.r8.ir.code.ConstInstruction;
 import com.android.tools.r8.ir.code.ConstNumber;
 import com.android.tools.r8.ir.code.ConstString;
@@ -1948,67 +1947,6 @@
     return converter.definitionFor(type);
   }
 
-  // Rewrite getClass() call to const-class if the type of the given instance is effectively final.
-  public void rewriteGetClass(IRCode code) {
-    InstructionIterator it = code.instructionIterator();
-    while (it.hasNext()) {
-      Instruction current = it.next();
-      // Conservatively bail out if the containing block has catch handlers.
-      // TODO(b/118509730): unless join of all catch types is ClassNotFoundException ?
-      if (current.getBlock().hasCatchHandlers()) {
-        continue;
-      }
-      if (!current.isInvokeVirtual()) {
-        continue;
-      }
-      InvokeVirtual invoke = current.asInvokeVirtual();
-      DexMethod invokedMethod = invoke.getInvokedMethod();
-      // Class<?> Object#getClass() is final and cannot be overridden.
-      if (invokedMethod != appInfo.dexItemFactory.objectMethods.getClass) {
-        continue;
-      }
-      Value in = invoke.getReceiver();
-      if (in.hasLocalInfo()) {
-        continue;
-      }
-      TypeLatticeElement inType = in.getTypeLattice();
-      // Check the receiver is either class type or array type. Also make sure it is not nullable.
-      if (!(inType.isClassType() || inType.isArrayType())
-          || inType.isNullable()) {
-        continue;
-      }
-      DexType type = inType.isClassType()
-          ? inType.asClassTypeLatticeElement().getClassType()
-          : inType.asArrayTypeLatticeElement().getArrayType();
-      DexType baseType = type.toBaseType(appInfo.dexItemFactory);
-      // Make sure base type is a class type.
-      if (!baseType.isClassType()) {
-        continue;
-      }
-      // Only consider program class, e.g., platform can introduce sub types in different versions.
-      DexClass clazz = appInfo.definitionFor(baseType);
-      if (clazz == null || !clazz.isProgramClass()) {
-        continue;
-      }
-      // Only consider effectively final class. Exception: new Base().getClass().
-      if (!baseType.hasSubtypes()
-          || !appInfo.withLiveness().isInstantiatedIndirectly(baseType)
-          || (!in.isPhi() && in.definition.isCreatingInstanceOrArray())) {
-        // Make sure the target (base) type is visible.
-        ConstraintWithTarget constraints =
-            ConstraintWithTarget.classIsVisible(code.method.method.getHolder(), baseType, appInfo);
-        if (constraints == ConstraintWithTarget.NEVER) {
-          continue;
-        }
-        TypeLatticeElement typeLattice = TypeLatticeElement.classClassType(appInfo);
-        Value value = code.createValue(typeLattice, invoke.getLocalInfo());
-        ConstClass constClass = new ConstClass(value, type);
-        it.replaceCurrentInstruction(constClass);
-      }
-    }
-    assert code.isConsistentSSA();
-  }
-
   public void removeTrivialCheckCastAndInstanceOfInstructions(
       IRCode code, boolean enableWholeProgramOptimizations) {
     if (!enableWholeProgramOptimizations) {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/ReflectionOptimizer.java b/src/main/java/com/android/tools/r8/ir/optimize/ReflectionOptimizer.java
index ecd3a7a..496e113 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/ReflectionOptimizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/ReflectionOptimizer.java
@@ -9,8 +9,19 @@
 
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.DexClass;
+import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexString;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
+import com.android.tools.r8.ir.code.ConstClass;
+import com.android.tools.r8.ir.code.IRCode;
+import com.android.tools.r8.ir.code.Instruction;
+import com.android.tools.r8.ir.code.InstructionIterator;
+import com.android.tools.r8.ir.code.InvokeVirtual;
+import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
 import com.android.tools.r8.ir.optimize.ReflectionOptimizer.ClassNameComputationInfo.ClassNameComputationOption;
+import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
 import com.google.common.base.Strings;
 
 public class ReflectionOptimizer {
@@ -57,6 +68,67 @@
     }
   }
 
+  // Rewrite getClass() call to const-class if the type of the given instance is effectively final.
+  public static void rewriteGetClass(AppInfoWithLiveness appInfo, IRCode code) {
+    InstructionIterator it = code.instructionIterator();
+    while (it.hasNext()) {
+      Instruction current = it.next();
+      // Conservatively bail out if the containing block has catch handlers.
+      // TODO(b/118509730): unless join of all catch types is ClassNotFoundException ?
+      if (current.getBlock().hasCatchHandlers()) {
+        continue;
+      }
+      if (!current.isInvokeVirtual()) {
+        continue;
+      }
+      InvokeVirtual invoke = current.asInvokeVirtual();
+      DexMethod invokedMethod = invoke.getInvokedMethod();
+      // Class<?> Object#getClass() is final and cannot be overridden.
+      if (invokedMethod != appInfo.dexItemFactory.objectMethods.getClass) {
+        continue;
+      }
+      Value in = invoke.getReceiver();
+      if (in.hasLocalInfo()) {
+        continue;
+      }
+      TypeLatticeElement inType = in.getTypeLattice();
+      // Check the receiver is either class type or array type. Also make sure it is not nullable.
+      if (!(inType.isClassType() || inType.isArrayType())
+          || inType.isNullable()) {
+        continue;
+      }
+      DexType type = inType.isClassType()
+          ? inType.asClassTypeLatticeElement().getClassType()
+          : inType.asArrayTypeLatticeElement().getArrayType(appInfo.dexItemFactory);
+      DexType baseType = type.toBaseType(appInfo.dexItemFactory);
+      // Make sure base type is a class type.
+      if (!baseType.isClassType()) {
+        continue;
+      }
+      // Only consider program class, e.g., platform can introduce sub types in different versions.
+      DexClass clazz = appInfo.definitionFor(baseType);
+      if (clazz == null || !clazz.isProgramClass()) {
+        continue;
+      }
+      // Only consider effectively final class. Exception: new Base().getClass().
+      if (!baseType.hasSubtypes()
+          || !appInfo.isInstantiatedIndirectly(baseType)
+          || (!in.isPhi() && in.definition.isCreatingInstanceOrArray())) {
+        // Make sure the target (base) type is visible.
+        ConstraintWithTarget constraints =
+            ConstraintWithTarget.classIsVisible(code.method.method.getHolder(), baseType, appInfo);
+        if (constraints == ConstraintWithTarget.NEVER) {
+          continue;
+        }
+        TypeLatticeElement typeLattice = TypeLatticeElement.classClassType(appInfo);
+        Value value = code.createValue(typeLattice, invoke.getLocalInfo());
+        ConstClass constClass = new ConstClass(value, type);
+        it.replaceCurrentInstruction(constClass);
+      }
+    }
+    assert code.isConsistentSSA();
+  }
+
   public static String computeClassName(
       DexString descriptor, DexClass holder, ClassNameComputationInfo classNameComputationInfo) {
     return computeClassName(
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/lambda/LambdaMerger.java b/src/main/java/com/android/tools/r8/ir/optimize/lambda/LambdaMerger.java
index 68eb269..50d22e1 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/lambda/LambdaMerger.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/lambda/LambdaMerger.java
@@ -307,9 +307,11 @@
             .sorted(DexEncodedMethod::slowCompare)
             .collect(Collectors.toList());
     for (DexEncodedMethod method : methods) {
-      converter.processMethod(method, feedback,
+      DexEncodedMethod mappedMethod =
+          converter.graphLense().mapDexEncodedMethod(converter.appInfo, method);
+      converter.processMethod(mappedMethod, feedback,
           x -> false, CallSiteInformation.empty(), Outliner::noProcessing);
-      assert method.isProcessed();
+      assert mappedMethod.isProcessed();
     }
   }
 
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/staticizer/StaticizingProcessor.java b/src/main/java/com/android/tools/r8/ir/optimize/staticizer/StaticizingProcessor.java
index 093ac43..7eb9624 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/staticizer/StaticizingProcessor.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/staticizer/StaticizingProcessor.java
@@ -20,6 +20,7 @@
 import com.android.tools.r8.ir.code.InstructionIterator;
 import com.android.tools.r8.ir.code.InvokeMethodWithReceiver;
 import com.android.tools.r8.ir.code.InvokeStatic;
+import com.android.tools.r8.ir.code.Phi;
 import com.android.tools.r8.ir.code.StaticGet;
 import com.android.tools.r8.ir.code.StaticPut;
 import com.android.tools.r8.ir.code.Value;
@@ -34,6 +35,7 @@
 import com.google.common.collect.Streams;
 import java.util.ArrayList;
 import java.util.HashMap;
+import java.util.HashSet;
 import java.util.IdentityHashMap;
 import java.util.Iterator;
 import java.util.List;
@@ -237,7 +239,7 @@
   }
 
   private void removeReferencesToThis(DexEncodedMethod method, IRCode code) {
-    fixupStaticizedValueUsers(code, code.getThis());
+    fixupStaticizedThisUsers(code, code.getThis());
   }
 
   private void rewriteReferences(DexEncodedMethod method, IRCode code) {
@@ -250,11 +252,12 @@
             .collect(Collectors.toList());
 
     singletonFieldReads.forEach(read -> {
-      CandidateInfo candidateInfo = singletonFields.get(read.getField());
+      DexField field = read.getField();
+      CandidateInfo candidateInfo = singletonFields.get(field);
       assert candidateInfo != null;
       Value value = read.dest();
       if (value != null) {
-        fixupStaticizedValueUsers(code, value);
+        fixupStaticizedFieldReadUsers(code, value, field);
       }
       if (!candidateInfo.preserveRead.get()) {
         read.removeOrReplaceByDebugLocalRead();
@@ -266,12 +269,116 @@
     }
   }
 
-  // Fixup value usages: rewrites all method calls so that they point to static methods.
-  private void fixupStaticizedValueUsers(IRCode code, Value thisValue) {
+  // Fixup `this` usages: rewrites all method calls so that they point to static methods.
+  private void fixupStaticizedThisUsers(IRCode code, Value thisValue) {
     assert thisValue != null;
     assert thisValue.numberOfPhiUsers() == 0;
 
-    for (Instruction user : thisValue.uniqueUsers()) {
+    fixupStaticizedValueUsers(code, thisValue.uniqueUsers());
+
+    assert thisValue.numberOfUsers() == 0;
+  }
+
+  // Re-processing finalized code may create slightly different IR code than what the examining
+  // phase has seen. For example,
+  //
+  //  b1:
+  //    s1 <- static-get singleton
+  //    ...
+  //    invoke-virtual { s1, ... } mtd1
+  //    goto Exit
+  //  b2:
+  //    s2 <- static-get singleoton
+  //    ...
+  //    invoke-virtual { s2, ... } mtd1
+  //    goto Exit
+  //  ...
+  //  Exit: ...
+  //
+  // ~>
+  //
+  //  b1:
+  //    s1 <- static-get singleton
+  //    ...
+  //    goto Exit
+  //  b2:
+  //    s2 <- static-get singleton
+  //    ...
+  //    goto Exit
+  //  Exit:
+  //    sp <- phi(s1, s2)
+  //    invoke-virtual { sp, ... } mtd1
+  //    ...
+  //
+  // From staticizer's viewpoint, `sp` is trivial in the sense that it is composed of values that
+  // refer to the same singleton field. If so, we can safely relax the assertion; remove uses of
+  // field reads; remove quasi-trivial phis; and then remove original field reads.
+  private boolean testAndcollectPhisComposedOfSameFieldRead(
+      Set<Phi> phisToCheck, DexField field, Set<Phi> trivialPhis) {
+    for (Phi phi : phisToCheck) {
+      Set<Phi> chainedPhis = Sets.newIdentityHashSet();
+      for (Value operand : phi.getOperands()) {
+        if (operand.isPhi()) {
+          chainedPhis.add(operand.asPhi());
+        } else {
+          if (!operand.definition.isStaticGet()) {
+            return false;
+          }
+          if (operand.definition.asStaticGet().getField() != field) {
+            return false;
+          }
+        }
+      }
+      if (!chainedPhis.isEmpty()) {
+        if (!testAndcollectPhisComposedOfSameFieldRead(chainedPhis, field, trivialPhis)) {
+          return false;
+        }
+      }
+      trivialPhis.add(phi);
+    }
+    return true;
+  }
+
+  // Fixup field read usages. Same as {@link #fixupStaticizedThisUsers} except this one is handling
+  // quasi-trivial phis that might be introduced while re-processing finalized code.
+  private void fixupStaticizedFieldReadUsers(IRCode code, Value dest, DexField field) {
+    assert dest != null;
+    // During the examine phase, field reads with any phi users have been invalidated, hence zero.
+    // However, it may be not true if re-processing introduces phis after optimizing common suffix.
+    Set<Phi> trivialPhis = Sets.newIdentityHashSet();
+    boolean hasTrivialPhis =
+        testAndcollectPhisComposedOfSameFieldRead(dest.uniquePhiUsers(), field, trivialPhis);
+    assert dest.numberOfPhiUsers() == 0 || hasTrivialPhis;
+    Set<Instruction> users = new HashSet<>(dest.uniqueUsers());
+    // If that is the case, method calls we want to fix up include users of those phis.
+    if (hasTrivialPhis) {
+      for (Phi phi : trivialPhis) {
+        users.addAll(phi.uniqueUsers());
+      }
+    }
+
+    fixupStaticizedValueUsers(code, users);
+
+    if (hasTrivialPhis) {
+      // We can't directly use Phi#removeTrivialPhi because they still refer to different operands.
+      for (Phi phi : trivialPhis) {
+        // First, make sure phi users are indeed uses of field reads and removed via fixup.
+        assert phi.numberOfUsers() == 0;
+        // Then, manually clean up this from all of the operands.
+        for (Value operand : phi.getOperands()) {
+          operand.removePhiUser(phi);
+        }
+        // And remove it from the containing block.
+        phi.getBlock().removePhi(phi);
+      }
+    }
+
+    // No matter what, number of phi users should be zero too.
+    assert dest.numberOfUsers() == 0 && dest.numberOfPhiUsers() == 0;
+  }
+
+  private void fixupStaticizedValueUsers(IRCode code, Set<Instruction> users) {
+    for (Instruction user : users) {
       assert user.isInvokeVirtual() || user.isInvokeDirect();
       InvokeMethodWithReceiver invoke = user.asInvokeMethodWithReceiver();
       Value newValue = null;
@@ -287,8 +394,6 @@
       invoke.replace(new InvokeStatic(
           invoke.getInvokedMethod(), newValue, args.subList(1, args.size())));
     }
-
-    assert thisValue.numberOfUsers() == 0;
   }
 
   private void remapMovedCandidates(IRCode code) {
diff --git a/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java b/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java
index 1f5b0b1..d626407 100644
--- a/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java
+++ b/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java
@@ -21,13 +21,10 @@
   private final AppInfoWithLiveness appInfo;
   private final ProguardKeepAttributes keep;
   private final InternalOptions options;
-  private final ProguardConfiguration.Builder compatibility;
 
-  public AnnotationRemover(AppInfoWithLiveness appInfo,
-      ProguardConfiguration.Builder compatibility, InternalOptions options) {
+  public AnnotationRemover(AppInfoWithLiveness appInfo, InternalOptions options) {
     this.appInfo = appInfo;
     this.keep = options.proguardConfiguration.getKeepAttributes();
-    this.compatibility = compatibility;
     this.options = options;
   }
 
@@ -128,8 +125,12 @@
     return isAnnotationTypeLive(annotation);
   }
 
-  public void run() {
+  public AnnotationRemover ensureValid(ProguardConfiguration.Builder compatibility) {
     keep.ensureValid(options.forceProguardCompatibility, compatibility);
+    return this;
+  }
+
+  public void run() {
     for (DexProgramClass clazz : appInfo.classes()) {
       stripAttributes(clazz);
       clazz.annotations = clazz.annotations.keepIf(this::filterAnnotations);
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 1084322..a9f5a71 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -862,20 +862,24 @@
     }
   }
 
-  private void markMethodAsTargeted(DexEncodedMethod encodedMethod, KeepReason reason) {
-    markTypeAsLive(encodedMethod.method.holder);
-    markParameterAndReturnTypesAsLive(encodedMethod);
-    if (Log.ENABLED) {
-      Log.verbose(getClass(), "Method `%s` is targeted.", encodedMethod.method);
+  private void markMethodAsTargeted(DexEncodedMethod method, KeepReason reason) {
+    if (!targetedMethods.add(method, reason)) {
+      return;
     }
-    targetedMethods.add(encodedMethod, reason);
+    markTypeAsLive(method.method.holder);
+    markParameterAndReturnTypesAsLive(method);
+    processAnnotations(method.annotations.annotations);
+    method.parameterAnnotationsList.forEachAnnotation(this::processAnnotation);
+    if (Log.ENABLED) {
+      Log.verbose(getClass(), "Method `%s` is targeted.", method.method);
+    }
     if (forceProguardCompatibility) {
       // Keep targeted default methods in compatibility mode. The tree pruner will otherwise make
       // these methods abstract, whereas Proguard does not (seem to) touch their code.
-      DexClass clazz = appInfo.definitionFor(encodedMethod.method.holder);
-      if (!encodedMethod.accessFlags.isAbstract()
+      DexClass clazz = appInfo.definitionFor(method.method.holder);
+      if (!method.accessFlags.isAbstract()
           && clazz.isInterface() && !clazz.isLibraryClass()) {
-        markMethodAsKeptWithCompatRule(encodedMethod);
+        markMethodAsKeptWithCompatRule(method);
       }
     }
   }
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 3a2f4e2..d1e0606 100644
--- a/src/main/java/com/android/tools/r8/shaking/StaticClassMerger.java
+++ b/src/main/java/com/android/tools/r8/shaking/StaticClassMerger.java
@@ -13,7 +13,6 @@
 import com.android.tools.r8.graph.DexString;
 import com.android.tools.r8.graph.GraphLense;
 import com.android.tools.r8.graph.GraphLense.NestedGraphLense;
-import com.android.tools.r8.graph.TopDownClassHierarchyTraversal;
 import com.android.tools.r8.logging.Log;
 import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
 import com.android.tools.r8.shaking.VerticalClassMerger.IllegalAccessDetector;
@@ -127,13 +126,11 @@
   }
 
   public GraphLense run() {
-    // Visit the program classes in a top-down order according to the class hierarchy.
-    Iterable<DexProgramClass> classes = appView.appInfo().app.classesWithDeterministicOrder();
-    TopDownClassHierarchyTraversal.visit(appView, classes, clazz -> {
+    for (DexProgramClass clazz : appView.appInfo().app.classesWithDeterministicOrder()) {
       if (satisfiesMergeCriteria(clazz)) {
         merge(clazz);
       }
-    });
+    }
     if (Log.ENABLED) {
       Log.info(
           getClass(),
@@ -204,6 +201,11 @@
     return true;
   }
 
+  private boolean isValidRepresentative(DexProgramClass clazz) {
+    // Disallow interfaces from being representatives, since interface methods require desugaring.
+    return !clazz.isInterface();
+  }
+
   private boolean merge(DexProgramClass clazz) {
     assert satisfiesMergeCriteria(clazz);
 
@@ -216,8 +218,12 @@
   private boolean mergeGlobally(DexProgramClass clazz, String pkg) {
     Representative globalRepresentative = representatives.get(GLOBAL);
     if (globalRepresentative == null) {
-      // Make the current class the global representative.
-      setRepresentative(GLOBAL, getOrCreateRepresentative(clazz, pkg));
+      if (isValidRepresentative(clazz)) {
+        // Make the current class the global representative.
+        setRepresentative(GLOBAL, getOrCreateRepresentative(clazz, pkg));
+      } else {
+        clearRepresentative(GLOBAL);
+      }
 
       // Do not attempt to merge this class inside its own package, because that could lead to
       // an increase in the global representative, which is not desirable.
@@ -227,8 +233,12 @@
       globalRepresentative.include(clazz);
 
       if (globalRepresentative.isFull()) {
-        // Make the current class the global representative instead.
-        setRepresentative(GLOBAL, getOrCreateRepresentative(clazz, pkg));
+        if (isValidRepresentative(clazz)) {
+          // Make the current class the global representative instead.
+          setRepresentative(GLOBAL, getOrCreateRepresentative(clazz, pkg));
+        } else {
+          clearRepresentative(GLOBAL);
+        }
 
         // Do not attempt to merge this class inside its own package, because that could lead to
         // an increase in the global representative, which is not desirable.
@@ -244,7 +254,8 @@
   private boolean mergeInsidePackage(DexProgramClass clazz, String pkg) {
     Representative packageRepresentative = representatives.get(pkg);
     if (packageRepresentative != null) {
-      if (clazz.accessFlags.isMoreVisibleThan(packageRepresentative.clazz.accessFlags)) {
+      if (isValidRepresentative(clazz)
+          && clazz.accessFlags.isMoreVisibleThan(packageRepresentative.clazz.accessFlags)) {
         // Use `clazz` as a representative for this package instead.
         Representative newRepresentative = getOrCreateRepresentative(clazz, pkg);
         newRepresentative.include(packageRepresentative.clazz);
@@ -271,7 +282,9 @@
     }
 
     // We were unable to use the current representative for this package (if any).
-    setRepresentative(pkg, getOrCreateRepresentative(clazz, pkg));
+    if (isValidRepresentative(clazz)) {
+      setRepresentative(pkg, getOrCreateRepresentative(clazz, pkg));
+    }
     return false;
   }
 
@@ -288,6 +301,7 @@
   }
 
   private void setRepresentative(String pkg, Representative representative) {
+    assert isValidRepresentative(representative.clazz);
     if (Log.ENABLED) {
       if (pkg.equals(GLOBAL)) {
         Log.info(
@@ -305,6 +319,17 @@
     representatives.put(pkg, representative);
   }
 
+  private void clearRepresentative(String pkg) {
+    if (Log.ENABLED) {
+      if (pkg.equals(GLOBAL)) {
+        Log.info(getClass(), "Removing the global representative");
+      } else {
+        Log.info(getClass(), "Removing the representative for package %s", pkg);
+      }
+    }
+    representatives.remove(pkg);
+  }
+
   private boolean mayMergeAcrossPackageBoundaries(DexProgramClass clazz) {
     // Check that the class is public. Otherwise, accesses to `clazz` from within its current
     // package may become illegal.
diff --git a/src/main/java/com/android/tools/r8/utils/ArchiveBuilder.java b/src/main/java/com/android/tools/r8/utils/ArchiveBuilder.java
index 24ee70c..69d65ea 100644
--- a/src/main/java/com/android/tools/r8/utils/ArchiveBuilder.java
+++ b/src/main/java/com/android/tools/r8/utils/ArchiveBuilder.java
@@ -33,8 +33,7 @@
   private int openCount = 0;
   private int classesFileIndex = 0;
   private Map<Integer, DelayedData> delayedClassesDexFiles = new HashMap<>();
-  private SortedSet<DelayedData> delayedFiles = new TreeSet<>();
-  private SortedSet<String> delayedDirectories = new TreeSet<>();
+  private SortedSet<DelayedData> delayedWrites = new TreeSet<>();
 
   public ArchiveBuilder(Path archive) {
     this.archive = archive;
@@ -66,11 +65,14 @@
   private void writeDelayed(DiagnosticsHandler handler) {
     // We should never have any indexed files at this point
     assert delayedClassesDexFiles.isEmpty();
-    for (String directory : delayedDirectories) {
-      writeDirectoryNow(directory, handler);
-    }
-    for (DelayedData data : delayedFiles) {
-      writeFileNow(data.name, data.content, handler);
+    for (DelayedData data : delayedWrites) {
+      if (data.isDirectory) {
+        assert data.content == null;
+        writeDirectoryNow(data.name, handler);
+      } else {
+        assert data.content != null;
+        writeFileNow(data.name, data.content, handler);
+      }
     }
   }
 
@@ -106,7 +108,7 @@
 
   @Override
   public synchronized void addDirectory(String name, DiagnosticsHandler handler) {
-    delayedDirectories.add(name);
+    delayedWrites.add(DelayedData.createDirectory(name));
   }
 
   private void writeDirectoryNow(String name, DiagnosticsHandler handler) {
@@ -131,7 +133,7 @@
     try (InputStream in = content.getByteStream()) {
       ByteDataView view = ByteDataView.of(ByteStreams.toByteArray(in));
       synchronized (this) {
-        delayedFiles.add(new DelayedData(name, view));
+        delayedWrites.add(DelayedData.createFile(name, view));
       }
     } catch (IOException e) {
       handleIOException(e, handler);
@@ -143,7 +145,7 @@
 
   @Override
   public synchronized void addFile(String name, ByteDataView content, DiagnosticsHandler handler) {
-    delayedFiles.add(new DelayedData(name,  ByteDataView.of(content.copyByteData())));
+    delayedWrites.add(DelayedData.createFile(name,  ByteDataView.of(content.copyByteData())));
   }
 
   private void writeFileNow(String name, ByteDataView content, DiagnosticsHandler handler) {
@@ -174,7 +176,7 @@
     } else {
       // Data is released in the application writer, take a copy.
       delayedClassesDexFiles.put(index,
-          new DelayedData(name, ByteDataView.of(content.copyByteData())));
+          new DelayedData(name, ByteDataView.of(content.copyByteData()), false));
     }
   }
 
@@ -191,9 +193,20 @@
   private static class DelayedData implements Comparable<DelayedData> {
     public final String name;
     public final ByteDataView content;
-    public DelayedData(String name, ByteDataView content) {
+    public final boolean isDirectory;
+
+    public static DelayedData createFile(String name, ByteDataView content) {
+      return new DelayedData(name, content, false);
+    }
+
+    public static DelayedData createDirectory(String name) {
+      return new DelayedData(name, null, true);
+    }
+
+    private DelayedData(String name, ByteDataView content, boolean isDirectory) {
       this.name = name;
       this.content = content;
+      this.isDirectory = isDirectory;
     }
 
     @Override
diff --git a/src/test/java/com/android/tools/r8/TestCompilerBuilder.java b/src/test/java/com/android/tools/r8/TestCompilerBuilder.java
index afa8e7b..9425df9 100644
--- a/src/test/java/com/android/tools/r8/TestCompilerBuilder.java
+++ b/src/test/java/com/android/tools/r8/TestCompilerBuilder.java
@@ -37,6 +37,7 @@
   // Default initialized setup. Can be overwritten if needed.
   private Path defaultLibrary;
   private ProgramConsumer programConsumer;
+  private StringConsumer mainDexListConsumer;
   private AndroidApiLevel defaultMinApiLevel = ToolHelper.getMinApiLevelForDexVm();
   private Consumer<InternalOptions> optionsConsumer = DEFAULT_OPTIONS;
 
@@ -62,6 +63,7 @@
   public CR compile() throws CompilationFailedException {
     AndroidAppConsumers sink = new AndroidAppConsumers();
     builder.setProgramConsumer(sink.wrapProgramConsumer(programConsumer));
+    builder.setMainDexListConsumer(mainDexListConsumer);
     if (defaultLibrary != null) {
       builder.addLibraryFiles(defaultLibrary);
     }
@@ -113,6 +115,17 @@
     return self();
   }
 
+  public T setMainDexListConsumer(StringConsumer consumer) {
+    assert consumer != null;
+    this.mainDexListConsumer = consumer;
+    return self();
+  }
+
+  public T addMainDexListFiles(Collection<Path> files) {
+    builder.addMainDexListFiles(files);
+    return self();
+  }
+
   @Override
   public T addProgramClassFileData(Collection<byte[]> classes) {
     for (byte[] clazz : classes) {
diff --git a/src/test/java/com/android/tools/r8/classmerging/StaticClassMergerInterfaceTest.java b/src/test/java/com/android/tools/r8/classmerging/StaticClassMergerInterfaceTest.java
new file mode 100644
index 0000000..294eca0
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/classmerging/StaticClassMergerInterfaceTest.java
@@ -0,0 +1,105 @@
+// Copyright (c) 2018, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.classmerging;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.core.IsNot.not;
+import static org.junit.Assert.assertThat;
+
+import com.android.tools.r8.NeverClassInline;
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.ToolHelper.DexVm.Version;
+import com.android.tools.r8.utils.StringUtils;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+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 StaticClassMergerInterfaceTest extends TestBase {
+
+  private final Backend backend;
+
+  @Parameters(name = "Backend: {0}")
+  public static Backend[] data() {
+    return Backend.values();
+  }
+
+  public StaticClassMergerInterfaceTest(Backend backend) {
+    this.backend = backend;
+  }
+
+  @Test
+  public void test() throws Exception {
+    String expectedOutput = StringUtils.lines("In A.a()", "In B.b()", "In C.c()");
+
+    CodeInspector inspector =
+        testForR8(backend)
+            .addInnerClasses(StaticClassMergerInterfaceTest.class)
+            .addKeepMainRule(TestClass.class)
+            .addKeepRules("-dontobfuscate")
+            .enableInliningAnnotations()
+            .enableClassInliningAnnotations()
+            .run(TestClass.class)
+            .assertSuccessWithOutput(expectedOutput)
+            .inspector();
+
+    // Check that A has not been merged into B. The static class merger visits classes in alpha-
+    // betical order. By the time A is processed, there is no merge representative and A is not
+    // a valid merge representative itself, because it is an interface.
+    if (ToolHelper.getDexVm().getVersion().isNewerThan(Version.V6_0_1) || backend == Backend.CF) {
+      assertThat(inspector.clazz(A.class), isPresent());
+    } else {
+      assertThat(inspector.clazz(A.class.getTypeName() + "$-CC"), isPresent());
+    }
+
+
+    // By the time B is processed, there is no merge representative, so it should be present.
+    assertThat(inspector.clazz(B.class), isPresent());
+
+    // By the time C is processed, B should be merge candidate. Therefore, we should allow C.c() to
+    // be moved to B *although C is an interface*.
+    assertThat(inspector.clazz(C.class), not(isPresent()));
+  }
+
+  static class TestClass {
+
+    public static void main(String[] args) {
+      A.a();
+      B.b();
+      C.c();
+    }
+  }
+
+  @NeverClassInline
+  interface A {
+
+    @NeverInline
+    static void a() {
+      System.out.println("In A.a()");
+    }
+  }
+
+  @NeverClassInline
+  static class B {
+
+    @NeverInline
+    static void b() {
+      System.out.println("In B.b()");
+    }
+  }
+
+  @NeverClassInline
+  interface C {
+
+    @NeverInline
+    static void c() {
+      System.out.println("In C.c()");
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/ir/analysis/type/ArrayTypeTest.java b/src/test/java/com/android/tools/r8/ir/analysis/type/ArrayTypeTest.java
index ac73d7d..8e38855 100644
--- a/src/test/java/com/android/tools/r8/ir/analysis/type/ArrayTypeTest.java
+++ b/src/test/java/com/android/tools/r8/ir/analysis/type/ArrayTypeTest.java
@@ -5,15 +5,18 @@
 package com.android.tools.r8.ir.analysis.type;
 
 import static com.android.tools.r8.ir.analysis.type.TypeLatticeElement.FLOAT;
+import static com.android.tools.r8.ir.analysis.type.TypeLatticeElement.INT;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertTrue;
 
 import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.ir.code.ArrayGet;
 import com.android.tools.r8.ir.code.ArrayPut;
+import com.android.tools.r8.ir.code.BasicBlock;
 import com.android.tools.r8.ir.code.ConstNumber;
 import com.android.tools.r8.ir.code.IRCode;
 import com.android.tools.r8.ir.code.Instruction;
+import com.android.tools.r8.ir.code.Phi;
 import com.android.tools.r8.ir.code.Value;
 import java.util.function.Consumer;
 import org.junit.Test;
@@ -34,6 +37,13 @@
     buildAndCheckIR("nestedArrayTest", nestedArrayTestInspector(appInfo));
   }
 
+  @Test
+  public void testJoinOfArraysForPrimitivesSmallerThanInt() throws Exception {
+    buildAndCheckIR(
+        "joinOfArraysForPrimitivesSmallerThanInt",
+        joinOfArraysForPrimitivesSmallerThanInt(appInfo));
+  }
+
   private static Consumer<IRCode> arrayTestInspector(AppInfo appInfo) {
     return code -> {
       Iterable<Instruction> instructions = code::instructionIterator;
@@ -53,9 +63,7 @@
           assertTrue(array.getTypeLattice().isArrayType());
 
           ArrayTypeLatticeElement arrayType = array.getTypeLattice().asArrayTypeLatticeElement();
-          TypeLatticeElement elementType =
-              TypeLatticeElement.fromDexType(
-                  arrayType.getArrayElementType(appInfo.dexItemFactory), true, appInfo);
+          TypeLatticeElement elementType = arrayType.getArrayMemberTypeAsMemberType();
 
           assertEquals(FLOAT, elementType);
           assertEquals(FLOAT, value.getTypeLattice());
@@ -75,9 +83,7 @@
         assertTrue(array.getTypeLattice().isArrayType());
 
         ArrayTypeLatticeElement arrayType = array.getTypeLattice().asArrayTypeLatticeElement();
-        TypeLatticeElement elementType =
-            TypeLatticeElement.fromDexType(
-                arrayType.getArrayElementType(appInfo.dexItemFactory), true, appInfo);
+        TypeLatticeElement elementType = arrayType.getArrayMemberTypeAsMemberType();
 
         assertEquals(FLOAT, elementType);
         assertEquals(FLOAT, value.getTypeLattice());
@@ -94,6 +100,19 @@
     };
   }
 
+  private static Consumer<IRCode> joinOfArraysForPrimitivesSmallerThanInt(AppInfo appInfo) {
+    return code -> {
+      int phiCount = 0;
+      for (BasicBlock block : code.blocks) {
+        for (Phi phi : block.getPhis()) {
+          phiCount++;
+          assertEquals(INT, phi.getTypeLattice());
+        }
+      }
+      assertEquals(2, phiCount);
+    };
+  }
+
   static class TestClass {
 
     public static void arrayTest() {
@@ -119,5 +138,14 @@
       float x = 1f;
       array[0][0] = x;
     }
+
+    public static void joinOfArraysForPrimitivesSmallerThanInt(
+        boolean predicate, byte[] bs, char[] cs) {
+      char s = (char) (predicate ? bs[0] : cs[0]);
+      byte b = (predicate ? bs[0] : bs[0]);
+      if (s == b) {
+        System.out.println("Meh, just to use variables.");
+      }
+    }
   }
 }
diff --git a/src/test/java/com/android/tools/r8/ir/analysis/type/NullabilityTest.java b/src/test/java/com/android/tools/r8/ir/analysis/type/NullabilityTest.java
index dfe22c7..adf80ae 100644
--- a/src/test/java/com/android/tools/r8/ir/analysis/type/NullabilityTest.java
+++ b/src/test/java/com/android/tools/r8/ir/analysis/type/NullabilityTest.java
@@ -159,9 +159,12 @@
       forEachOutValue(irCode, (v, l) -> {
         if (l.isArrayType()) {
           ArrayTypeLatticeElement lattice = l.asArrayTypeLatticeElement();
+          assertEquals(1, lattice.getNesting());
+          TypeLatticeElement elementTypeLattice = lattice.getArrayMemberTypeAsMemberType();
+          assertTrue(elementTypeLattice.isClassType());
           assertEquals(
               appInfo.dexItemFactory.stringType,
-              lattice.getArrayElementType(appInfo.dexItemFactory));
+              elementTypeLattice.asClassTypeLatticeElement().getClassType());
           assertEquals(v.definition.isArgument(), l.isNullable());
         } else if (l.isClassType()) {
           verifyClassTypeLattice(expectedLattices, mainClass, v, l);
@@ -185,9 +188,12 @@
       forEachOutValue(irCode, (v, l) -> {
         if (l.isArrayType()) {
           ArrayTypeLatticeElement lattice = l.asArrayTypeLatticeElement();
+          assertEquals(1, lattice.getNesting());
+          TypeLatticeElement elementTypeLattice = lattice.getArrayMemberTypeAsMemberType();
+          assertTrue(elementTypeLattice.isClassType());
           assertEquals(
               appInfo.dexItemFactory.stringType,
-              lattice.getArrayElementType(appInfo.dexItemFactory));
+              elementTypeLattice.asClassTypeLatticeElement().getClassType());
           assertEquals(v.definition.isArgument(), l.isNullable());
         } else if (l.isClassType()) {
           verifyClassTypeLattice(expectedLattices, mainClass, v, l);
diff --git a/src/test/java/com/android/tools/r8/ir/analysis/type/TypeAnalysisTest.java b/src/test/java/com/android/tools/r8/ir/analysis/type/TypeAnalysisTest.java
index e0d7f71..09f6a01 100644
--- a/src/test/java/com/android/tools/r8/ir/analysis/type/TypeAnalysisTest.java
+++ b/src/test/java/com/android/tools/r8/ir/analysis/type/TypeAnalysisTest.java
@@ -189,7 +189,7 @@
       if (v == finalArray) {
         assertTrue(l.isArrayType());
         ArrayTypeLatticeElement lattice = l.asArrayTypeLatticeElement();
-        assertTrue(lattice.getArrayType().isPrimitiveArrayType());
+        assertTrue(lattice.getArrayMemberTypeAsMemberType().isPrimitive());
         assertEquals(1, lattice.getNesting());
         assertFalse(lattice.isNullable());
       }
@@ -222,7 +222,7 @@
       if (v == finalArray) {
         assertTrue(l.isArrayType());
         ArrayTypeLatticeElement lattice = l.asArrayTypeLatticeElement();
-        assertTrue(lattice.getArrayType().isPrimitiveArrayType());
+        assertTrue(lattice.getArrayMemberTypeAsMemberType().isPrimitive());
         assertEquals(1, lattice.getNesting());
         assertFalse(lattice.isNullable());
       }
diff --git a/src/test/java/com/android/tools/r8/ir/analysis/type/TypeAnalysisTestBase.java b/src/test/java/com/android/tools/r8/ir/analysis/type/TypeAnalysisTestBase.java
index e444e93..5cd64b9 100644
--- a/src/test/java/com/android/tools/r8/ir/analysis/type/TypeAnalysisTestBase.java
+++ b/src/test/java/com/android/tools/r8/ir/analysis/type/TypeAnalysisTestBase.java
@@ -22,7 +22,7 @@
 import java.util.function.Predicate;
 import org.junit.Before;
 
-public class TypeAnalysisTestBase extends TestBase {
+public abstract class TypeAnalysisTestBase extends TestBase {
 
   private final AndroidApp app;
   private final String className;
diff --git a/src/test/java/com/android/tools/r8/ir/analysis/type/TypeLatticeTest.java b/src/test/java/com/android/tools/r8/ir/analysis/type/TypeLatticeTest.java
index d1b3f9e..fbfc09b 100644
--- a/src/test/java/com/android/tools/r8/ir/analysis/type/TypeLatticeTest.java
+++ b/src/test/java/com/android/tools/r8/ir/analysis/type/TypeLatticeTest.java
@@ -3,7 +3,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.analysis.type;
 
-import static com.android.tools.r8.ir.analysis.type.TypeLatticeElement.computeLeastUpperBoundOfInterfaces;
+import static com.android.tools.r8.ir.analysis.type.ClassTypeLatticeElement.computeLeastUpperBoundOfInterfaces;
 import static com.android.tools.r8.ir.analysis.type.TypeLatticeElement.fromDexType;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
@@ -293,9 +293,41 @@
 
   @Test
   public void joinInterfaceArrayAndImplementerArray() {
+    DexType queue = factory.createType("Ljava/util/Queue;");
+    DexType arrayDeque = factory.createType("Ljava/util/ArrayDeque;");
     assertEquals(
-        // TODO(b/119181813): This should be array(1, charSequence)
-        array(1, factory.objectType),
+        array(1, queue),
+        join(
+            array(1, queue),
+            array(1, arrayDeque)));
+    assertEquals(
+        array(2, queue),
+        join(
+            array(2, arrayDeque),
+            array(2, queue)));
+
+    DexType type = factory.createType("Ljava/lang/reflect/Type;");
+    DexType wType = factory.createType("Ljava/lang/reflect/WildcardType;");
+    DexType pType = factory.createType("Ljava/lang/reflect/ParameterizedType;");
+    assertEquals(
+        array(1, type),
+        join(
+            array(1, wType),
+            array(1, pType)));
+    assertEquals(
+        array(2, type),
+        join(
+            array(2, wType),
+            array(2, factory.classType)));
+    assertEquals(
+        array(1, type),
+        join(
+            array(1, wType),
+            array(1, pType),
+            array(1, factory.classType)));
+
+    assertEquals(
+        array(1, factory.charSequenceType),
         join(
             array(1, factory.charSequenceType),
             array(1, factory.stringType)));
@@ -347,6 +379,18 @@
         join(
             array(1, factory.longType),
             array(1, factory.intType)));
+
+    // Test primitive types smaller than int.
+    assertEquals(
+        element(factory.objectType),
+        join(
+            array(1, factory.intType),
+            array(1, factory.byteType)));
+    assertEquals(
+        element(factory.objectType),
+        join(
+            array(1, factory.charType),
+            array(1, factory.shortType)));
   }
 
   @Test
@@ -397,10 +441,10 @@
   @Test
   public void joinDistinctTypesClassArrays() {
     assertEquals(
-        array(3, factory.objectType),
+        array(3, factory.serializableType),
         join(
             array(3, factory.stringType),
-            array(3, factory.stringBuilderType)));
+            array(3, factory.classType)));
   }
 
   @Test
diff --git a/src/test/java/com/android/tools/r8/kotlin/MetadataStripTest.java b/src/test/java/com/android/tools/r8/kotlin/MetadataStripTest.java
index 1ab3147..dc2ba39 100644
--- a/src/test/java/com/android/tools/r8/kotlin/MetadataStripTest.java
+++ b/src/test/java/com/android/tools/r8/kotlin/MetadataStripTest.java
@@ -41,8 +41,6 @@
       o -> {
         o.enableTreeShaking = true;
         o.enableMinification = true;
-        // TODO(b/119626580): assertion failure at fixupStaticizedValueUsers.
-        o.enableClassStaticizer = false;
       };
 
   @Parameterized.Parameters(name = "Backend: {0} target: {1}")
diff --git a/src/test/java/com/android/tools/r8/maindexlist/MainDexListOutputTest.java b/src/test/java/com/android/tools/r8/maindexlist/MainDexListOutputTest.java
index c053e62..9d9f21d 100644
--- a/src/test/java/com/android/tools/r8/maindexlist/MainDexListOutputTest.java
+++ b/src/test/java/com/android/tools/r8/maindexlist/MainDexListOutputTest.java
@@ -9,16 +9,19 @@
 
 import com.android.tools.r8.CompilationFailedException;
 import com.android.tools.r8.DexIndexedConsumer;
+import com.android.tools.r8.DexIndexedConsumer.ArchiveConsumer;
 import com.android.tools.r8.Diagnostic;
 import com.android.tools.r8.DiagnosticsHandler;
 import com.android.tools.r8.OutputMode;
 import com.android.tools.r8.R8Command;
+import com.android.tools.r8.StringConsumer;
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.ToolHelper;
 import com.android.tools.r8.origin.Origin;
 import com.android.tools.r8.utils.FileUtils;
 import com.android.tools.r8.utils.StringDiagnostic;
 import com.google.common.collect.ImmutableList;
+import java.io.IOException;
 import java.nio.file.Path;
 import java.util.stream.Collectors;
 import org.junit.Rule;
@@ -27,6 +30,34 @@
 
 public class MainDexListOutputTest extends TestBase {
 
+  interface MyConsumer<T> {
+    void accept(T element);
+  }
+
+  class TestClass {
+    public void f(MyConsumer<String> s) {
+      s.accept("asdf");
+    }
+
+    public void g() {
+      f(System.out::println);
+    }
+  }
+
+  private static String testClassMainDexName =
+      "com/android/tools/r8/maindexlist/MainDexListOutputTest$TestClass.class";
+
+  private static class TestMainDexListConsumer implements StringConsumer {
+    public boolean called = false;
+
+    @Override
+    public void accept(String string, DiagnosticsHandler handler) {
+      called = true;
+      assertTrue(string.contains(testClassMainDexName));
+      assertTrue(string.contains("Lambda"));
+    }
+  }
+
   class Reporter implements DiagnosticsHandler {
     int errorCount = 0;
 
@@ -77,4 +108,37 @@
             .filter(s -> !s.isEmpty())
             .collect(Collectors.toList()));
   }
+
+  @Test
+  public void testD8DesugaredLambdasInMainDexList() throws IOException, CompilationFailedException {
+    Path mainDexList = writeTextToTempFile(testClassMainDexName);
+    TestMainDexListConsumer consumer = new TestMainDexListConsumer();
+    testForD8()
+        .addProgramClasses(ImmutableList.of(TestClass.class, MyConsumer.class))
+        .addMainDexListFiles(ImmutableList.of(mainDexList))
+        .setMainDexListConsumer(consumer)
+        .compile();
+    assertTrue(consumer.called);
+  }
+
+  @Test
+  public void testD8DesugaredLambdasInMainDexListMerging()
+      throws IOException, CompilationFailedException {
+    Path mainDexList = writeTextToTempFile(testClassMainDexName);
+    Path dexOutput = temp.getRoot().toPath().resolve("classes.zip");
+    // Build intermediate dex code first.
+    testForD8()
+        .addProgramClasses(ImmutableList.of(TestClass.class, MyConsumer.class))
+        .setIntermediate(true)
+        .setProgramConsumer(new ArchiveConsumer(dexOutput))
+        .compile();
+    // Now test that when merging with a main dex list it is correctly updated.
+    TestMainDexListConsumer consumer = new TestMainDexListConsumer();
+    testForD8()
+        .addProgramFiles(dexOutput)
+        .addMainDexListFiles(ImmutableList.of(mainDexList))
+        .setMainDexListConsumer(consumer)
+        .compile();
+    assertTrue(consumer.called);
+  }
 }
diff --git a/src/test/java/com/android/tools/r8/shaking/FieldTypeTest.java b/src/test/java/com/android/tools/r8/shaking/FieldTypeTest.java
index 128b2ac..f8d8e7c 100644
--- a/src/test/java/com/android/tools/r8/shaking/FieldTypeTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/FieldTypeTest.java
@@ -12,8 +12,6 @@
 
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.ToolHelper;
-import com.android.tools.r8.ToolHelper.DexVm;
-import com.android.tools.r8.ToolHelper.DexVm.Version;
 import com.android.tools.r8.ToolHelper.ProcessResult;
 import com.android.tools.r8.VmTestRunner;
 import com.android.tools.r8.jasmin.JasminBuilder;
@@ -203,24 +201,25 @@
     assertEquals(0, javaResult.exitCode);
     assertThat(javaResult.stdout, containsString(impl2.name));
 
-    AndroidApp processedApp = compileWithR8(jasminBuilder.build(), proguardConfig,
-        // Disable inlining to avoid the (short) tested method from being inlined and then removed.
-        internalOptions -> internalOptions.enableInlining = false);
+    AndroidApp processedApp = compileWithR8(
+        jasminBuilder.build(),
+        proguardConfig,
+        internalOptions -> {
+          // Disable inlining to avoid the (short) tested method from being inlined and then
+          // removed.
+          internalOptions.enableInlining = false;
+          internalOptions.testing.allowTypeErrors = true;
+        });
 
     // Run processed (output) program on ART
     ProcessResult artResult = runOnArtRaw(processedApp, mainClassName);
     assertNotEquals(0, artResult.exitCode);
-    assertEquals(-1, artResult.stderr.indexOf("DoFieldPut"));
-    DexVm.Version currentVersion = ToolHelper.getDexVm().getVersion();
-    String errorMessage =
-        currentVersion.isNewerThan(Version.V4_4_4)
-            ? "type Precise Reference: Impl1[] but expected Reference: Itf1[]"
-            : "storing type '[LImpl1;' into field type '[LItf1;'";
-    assertThat(artResult.stderr, containsString(errorMessage));
+    assertThat(artResult.stderr, containsString("java.lang.NullPointerException"));
+    assertThat(artResult.stderr, not(containsString("DoFieldPut")));
 
     CodeInspector inspector = new CodeInspector(processedApp);
     ClassSubject itf1Subject = inspector.clazz(itf1.name);
-    assertThat(itf1Subject, isPresent());
+    assertThat(itf1Subject, not(isPresent()));
   }
 
 }
diff --git a/src/test/java/com/android/tools/r8/shaking/annotations/AnnotationsOnTargetedMethodTest.java b/src/test/java/com/android/tools/r8/shaking/annotations/AnnotationsOnTargetedMethodTest.java
new file mode 100644
index 0000000..a7bdf0b
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/annotations/AnnotationsOnTargetedMethodTest.java
@@ -0,0 +1,117 @@
+// Copyright (c) 2018, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.shaking.annotations;
+
+import static org.junit.Assume.assumeTrue;
+
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.NeverMerge;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.utils.StringUtils;
+import java.lang.annotation.Annotation;
+import java.lang.annotation.ElementType;
+import java.lang.annotation.Retention;
+import java.lang.annotation.RetentionPolicy;
+import java.lang.annotation.Target;
+import java.lang.reflect.Method;
+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 AnnotationsOnTargetedMethodTest extends TestBase {
+
+  private static final String expectedOutput =
+      StringUtils.lines(
+          "In InterfaceImpl.targetedMethod()",
+          "In OtherInterfaceImpl.targetedMethod()",
+          MyAnnotation.class.getName());
+
+  private final Backend backend;
+
+  @Parameters(name = "Backend: {0}")
+  public static Backend[] data() {
+    return Backend.values();
+  }
+
+  public AnnotationsOnTargetedMethodTest(Backend backend) {
+    this.backend = backend;
+  }
+
+  @Test
+  public void jvmTest() throws Exception {
+    assumeTrue(
+        "JVM test independent of Art version - only run when testing on latest",
+        ToolHelper.getDexVm().getVersion().isLatest());
+    testForJvm().addTestClasspath().run(TestClass.class).assertSuccessWithOutput(expectedOutput);
+  }
+
+  @Test
+  public void r8Test() throws Exception {
+    testForR8(backend)
+        .addInnerClasses(AnnotationsOnTargetedMethodTest.class)
+        .addKeepMainRule(TestClass.class)
+        .addKeepRules("-keepattributes *Annotation*", "-dontobfuscate")
+        .enableInliningAnnotations()
+        .enableMergeAnnotations()
+        .run(TestClass.class)
+        .assertSuccessWithOutput(expectedOutput);
+  }
+
+  static class TestClass {
+
+    public static void main(String[] args) {
+      test(new InterfaceImpl());
+      test(new OtherInterfaceImpl());
+
+      Method method = Interface.class.getDeclaredMethods()[0];
+      for (Annotation annotation : method.getAnnotations()) {
+        visitAnnotation((MyAnnotation) annotation);
+      }
+    }
+
+    @NeverInline
+    private static void test(Interface obj) {
+      obj.targetedMethod();
+    }
+
+    @NeverInline
+    private static void visitAnnotation(MyAnnotation annotation) {
+      System.out.println(annotation.annotationType().getName());
+    }
+  }
+
+  @NeverMerge
+  interface Interface {
+
+    @NeverInline
+    @MyAnnotation
+    void targetedMethod();
+  }
+
+  static class InterfaceImpl implements Interface {
+
+    @NeverInline
+    @Override
+    public void targetedMethod() {
+      System.out.println("In InterfaceImpl.targetedMethod()");
+    }
+  }
+
+  static class OtherInterfaceImpl implements Interface {
+
+    @NeverInline
+    @Override
+    public void targetedMethod() {
+      System.out.println("In OtherInterfaceImpl.targetedMethod()");
+    }
+  }
+
+  @Retention(RetentionPolicy.RUNTIME)
+  @Target({ElementType.METHOD})
+  @interface MyAnnotation {}
+}