Merge "Update the retrace test"
diff --git a/.gitignore b/.gitignore
index cb3eaab..22b29da 100644
--- a/.gitignore
+++ b/.gitignore
@@ -19,6 +19,8 @@
 tools/*/art-7.0.0.tar.gz
 tools/*/art-8.1.0
 tools/*/art-8.1.0.tar.gz
+tools/*/art-9.0.0
+tools/*/art-9.0.0.tar.gz
 tools/*/dalvik
 tools/*/dalvik.tar.gz
 tools/*/dalvik-4.0.4
diff --git a/PRESUBMIT.py b/PRESUBMIT.py
new file mode 100644
index 0000000..20faecf
--- /dev/null
+++ b/PRESUBMIT.py
@@ -0,0 +1,15 @@
+# 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.
+
+def CheckDoNotMerge(input_api, output_api):
+  for l in input_api.change.FullDescriptionText().splitlines():
+    if l.lower().startswith('do not merge'):
+      msg = 'Your cl contains: \'Do not merge\' - this will break WIP bots'
+      return [output_api.PresubmitPromptWarning(msg, [])]
+  return []
+
+def CheckChangeOnUpload(input_api, output_api):
+  results = []
+  results.extend(CheckDoNotMerge(input_api, output_api))
+  return results
diff --git a/build.gradle b/build.gradle
index 5ec2f08..0a4f374 100644
--- a/build.gradle
+++ b/build.gradle
@@ -297,6 +297,7 @@
                 "linux/art-6.0.1",
                 "linux/art-7.0.0",
                 "linux/art-8.1.0",
+                "linux/art-9.0.0",
                 "linux/dalvik",
                 "linux/dalvik-4.0.4",
                 "${osString}/dx",
@@ -309,8 +310,8 @@
             def outputDir = "${entry.key}/${entryFile}"
             def gzFile = "${outputDir}.tar.gz"
             def sha1File = "${gzFile}.sha1"
-            inputs.file sha1File
-            outputs.file gzFile
+            // Make the output file part of the input dependencies explictly.
+            inputs.files files(sha1File, gzFile)
             outputs.dir outputDir
             List<String> dlFromStorageArgs = ["-n", "-b", "r8-deps", "-u", "-s", "${sha1File}"]
             if (OperatingSystem.current().isWindows()) {
diff --git a/scripts/update-host-art.sh b/scripts/update-host-art.sh
index 8bfc753..fb45744 100755
--- a/scripts/update-host-art.sh
+++ b/scripts/update-host-art.sh
@@ -130,6 +130,23 @@
 mkdir -p $DEST/usr/icu
 cp -r $ANDROID_HOST_BUILD/usr/icu/* $DEST/usr/icu
 
+# Update links for vdex files for Android P and later.
+if [ -f $DEST/product/$ANDROID_PRODUCT/system/framework/boot.vdex ]; then
+  for VDEXFILE in $DEST/product/$ANDROID_PRODUCT/system/framework/*.vdex; do
+    VDEXNAME=$(basename ${VDEXFILE});
+    for ARCH in arm arm64; do
+      rm $DEST/product/$ANDROID_PRODUCT/system/framework/$ARCH/${VDEXNAME};
+      # This relative link command will create a symbolic link of the form
+      # ../${VDEXNAME} for each architecture.
+      # ln -r -s $DEST/product/$ANDROID_PRODUCT/system/framework/${VDEXNAME} $DEST/product/$ANDROID_PRODUCT/system/framework/$ARCH/${VDEXNAME};
+      # The Cloud Storage dependency tool (download_from_google_storage.py) does
+      # not allow synlinks at all, so instad of the ln in the comment above just
+      # copy the ${VDEXNAME} files.
+      cp $DEST/product/$ANDROID_PRODUCT/system/framework/${VDEXNAME} $DEST/product/$ANDROID_PRODUCT/system/framework/$ARCH/${VDEXNAME};
+    done
+  done
+fi
+
 # Allow failure for strip commands below.
 set +e
 
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 bdbf44f..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.11-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/cf/code/CfDexItemBasedConstString.java b/src/main/java/com/android/tools/r8/cf/code/CfDexItemBasedConstString.java
index 627bbe6..f0c9636 100644
--- a/src/main/java/com/android/tools/r8/cf/code/CfDexItemBasedConstString.java
+++ b/src/main/java/com/android/tools/r8/cf/code/CfDexItemBasedConstString.java
@@ -6,24 +6,34 @@
 import com.android.tools.r8.cf.CfPrinter;
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.DexReference;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.UseRegistry;
 import com.android.tools.r8.ir.conversion.CfSourceCode;
 import com.android.tools.r8.ir.conversion.CfState;
 import com.android.tools.r8.ir.conversion.IRBuilder;
+import com.android.tools.r8.ir.optimize.ReflectionOptimizer.ClassNameComputationInfo;
 import com.android.tools.r8.naming.NamingLens;
 import org.objectweb.asm.MethodVisitor;
 
 public class CfDexItemBasedConstString extends CfInstruction {
 
-  private DexReference item;
+  private final DexReference item;
+  private final ClassNameComputationInfo classNameComputationInfo;
 
-  public CfDexItemBasedConstString(DexReference item) {
+  public CfDexItemBasedConstString(
+      DexReference item, ClassNameComputationInfo classNameComputationInfo) {
     this.item = item;
+    this.classNameComputationInfo = classNameComputationInfo;
   }
 
   public DexReference getItem() {
     return item;
   }
 
+  public ClassNameComputationInfo getClassNameComputationInfo() {
+    return classNameComputationInfo;
+  }
+
   @Override
   public CfDexItemBasedConstString asDexItemBasedConstString() {
     return this;
@@ -52,6 +62,13 @@
   }
 
   @Override
+  public void registerUse(UseRegistry registry, DexType clazz) {
+    if (item.isDexType() && classNameComputationInfo.needsToRegisterTypeReference()) {
+      registry.registerTypeReference(item.asDexType());
+    }
+  }
+
+  @Override
   public void buildIR(IRBuilder builder, CfState state, CfSourceCode code) {
     builder.addDexItemBasedConstString(state.push(builder.getFactory().stringType).register, item);
   }
diff --git a/src/main/java/com/android/tools/r8/code/DexItemBasedConstString.java b/src/main/java/com/android/tools/r8/code/DexItemBasedConstString.java
index 1871c41..a55ddfa 100644
--- a/src/main/java/com/android/tools/r8/code/DexItemBasedConstString.java
+++ b/src/main/java/com/android/tools/r8/code/DexItemBasedConstString.java
@@ -6,7 +6,9 @@
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.DexReference;
 import com.android.tools.r8.graph.ObjectToOffsetMapping;
+import com.android.tools.r8.graph.UseRegistry;
 import com.android.tools.r8.ir.conversion.IRBuilder;
+import com.android.tools.r8.ir.optimize.ReflectionOptimizer.ClassNameComputationInfo;
 import com.android.tools.r8.naming.ClassNameMapper;
 import java.nio.ShortBuffer;
 
@@ -15,14 +17,22 @@
   public static final String NAME = "DexItemBasedConstString";
   public static final String SMALI_NAME = "const-string*";
 
-  public DexItemBasedConstString(int register, DexReference string) {
+  private final ClassNameComputationInfo classNameComputationInfo;
+
+  public DexItemBasedConstString(
+      int register, DexReference string, ClassNameComputationInfo classNameComputationInfo) {
     super(register, string);
+    this.classNameComputationInfo = classNameComputationInfo;
   }
 
   public DexReference getItem() {
     return (DexReference) BBBB;
   }
 
+  public ClassNameComputationInfo getClassNameComputationInfo() {
+    return classNameComputationInfo;
+  }
+
   @Override
   public String getName() {
     return NAME;
@@ -68,6 +78,13 @@
   }
 
   @Override
+  public void registerUse(UseRegistry registry) {
+    if (getItem().isDexType() && classNameComputationInfo.needsToRegisterTypeReference()) {
+      registry.registerTypeReference(getItem().asDexType());
+    }
+  }
+
+  @Override
   public void buildIR(IRBuilder builder) {
     builder.addDexItemBasedConstString(AA, (DexReference) BBBB);
   }
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/DexEncodedMethod.java b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
index 0474696..46738e2 100644
--- a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
+++ b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
@@ -1203,14 +1203,14 @@
     optimizationInfo = info;
   }
 
-  public void copyMetadataFromInlinee(DexEncodedMethod inlinee) {
+  public void copyMetadata(DexEncodedMethod from) {
     checkIfObsolete();
     // Record that the current method uses identifier name string if the inlinee did so.
-    if (inlinee.getOptimizationInfo().useIdentifierNameString()) {
+    if (from.getOptimizationInfo().useIdentifierNameString()) {
       getMutableOptimizationInfo().markUseIdentifierNameString();
     }
-    if (inlinee.classFileVersion > classFileVersion) {
-      upgradeClassFileVersion(inlinee.getClassFileVersion());
+    if (from.classFileVersion > classFileVersion) {
+      upgradeClassFileVersion(from.getClassFileVersion());
     }
   }
 
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 0450937..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;
 
@@ -128,6 +132,9 @@
   public final DexString containsMethodName = createString("contains");
   public final DexString startsWithMethodName = createString("startsWith");
   public final DexString endsWithMethodName = createString("endsWith");
+  public final DexString equalsMethodName = createString("equals");
+  public final DexString equalsIgnoreCaseMethodName = createString("equalsIgnoreCase");
+  public final DexString contentEqualsMethodName = createString("contentEquals");
 
   public final DexString valueOfMethodName = createString("valueOf");
   public final DexString toStringMethodName = createString("toString");
@@ -580,6 +587,9 @@
     public final DexMethod contains;
     public final DexMethod startsWith;
     public final DexMethod endsWith;
+    public final DexMethod equals;
+    public final DexMethod equalsIgnoreCase;
+    public final DexMethod contentEqualsCharSequence;
 
     public final DexMethod valueOf;
     public final DexMethod toString;
@@ -590,17 +600,25 @@
       length = createMethod(
           stringDescriptor, lengthMethodName, intDescriptor, DexString.EMPTY_ARRAY);
 
-      DexString[] needsOneCharSequence = new DexString[]{charSequenceDescriptor};
+      DexString[] needsOneCharSequence = { charSequenceDescriptor };
+      DexString[] needsOneString = { stringDescriptor };
+      DexString[] needsOneObject = { objectDescriptor };
+
       contains = createMethod(
           stringDescriptor, containsMethodName, booleanDescriptor, needsOneCharSequence);
-      DexString[] needsOneString = new DexString[]{stringDescriptor};
       startsWith = createMethod(
           stringDescriptor, startsWithMethodName, booleanDescriptor, needsOneString);
       endsWith = createMethod(
           stringDescriptor, endsWithMethodName, booleanDescriptor, needsOneString);
+      equals = createMethod(
+          stringDescriptor, equalsMethodName, booleanDescriptor, needsOneObject);
+      equalsIgnoreCase = createMethod(
+          stringDescriptor, equalsIgnoreCaseMethodName, booleanDescriptor, needsOneString);
+      contentEqualsCharSequence = createMethod(
+          stringDescriptor, contentEqualsMethodName, booleanDescriptor, needsOneCharSequence);
 
       valueOf = createMethod(
-          stringDescriptor, valueOfMethodName, stringDescriptor, new DexString[]{objectDescriptor});
+          stringDescriptor, valueOfMethodName, stringDescriptor, needsOneObject);
       toString = createMethod(
           stringDescriptor, toStringMethodName, stringDescriptor, DexString.EMPTY_ARRAY);
     }
@@ -975,14 +993,13 @@
 
   public ReferenceTypeLatticeElement createReferenceTypeLatticeElement(
       DexType type, boolean isNullable, AppInfo appInfo) {
-    ReferenceTypeLatticeElement typeLattice = referenceTypeLatticeElements.get(type);
-    if (typeLattice != null) {
-      return isNullable == typeLattice.isNullable() ? typeLattice
-          : typeLattice.getOrCreateDualLattice();
-    }
     synchronized (type) {
-      typeLattice = referenceTypeLatticeElements.get(type);
-      if (typeLattice == null) {
+      ReferenceTypeLatticeElement typeLattice = referenceTypeLatticeElements.get(type);
+      if (typeLattice != null) {
+        typeLattice = isNullable == typeLattice.isNullable() ? typeLattice
+            : typeLattice.getOrCreateDualLattice();
+        assert typeLattice.isNullable() == isNullable;
+      } else {
         if (type.isClassType()) {
           if (!type.isUnknown() && type.isInterface()) {
             typeLattice = new ClassTypeLatticeElement(
@@ -996,12 +1013,16 @@
           }
         } 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);
       }
+      assert typeLattice.isNullable() == isNullable;
+      return typeLattice;
     }
-    return typeLattice;
   }
 
   private static <S extends PresortedComparable<S>> void assignSortedIndices(Collection<S> items,
diff --git a/src/main/java/com/android/tools/r8/graph/DexValue.java b/src/main/java/com/android/tools/r8/graph/DexValue.java
index 6eb69b8..c0413e0 100644
--- a/src/main/java/com/android/tools/r8/graph/DexValue.java
+++ b/src/main/java/com/android/tools/r8/graph/DexValue.java
@@ -11,6 +11,7 @@
 import com.android.tools.r8.ir.code.ConstNumber;
 import com.android.tools.r8.ir.code.Instruction;
 import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.ir.optimize.ReflectionOptimizer.ClassNameComputationInfo;
 import com.android.tools.r8.utils.EncodedValueUtils;
 import java.util.Arrays;
 import org.objectweb.asm.Handle;
@@ -719,9 +720,20 @@
   }
 
   public static class DexItemBasedValueString extends NestedDexValue<DexReference> {
+    private final ClassNameComputationInfo classNameComputationInfo;
 
     public DexItemBasedValueString(DexReference value) {
+      this(value, ClassNameComputationInfo.none());
+    }
+
+    public DexItemBasedValueString(
+        DexReference value, ClassNameComputationInfo classNameComputationInfo) {
       super(value);
+      this.classNameComputationInfo = classNameComputationInfo;
+    }
+
+    public ClassNameComputationInfo getClassNameComputationInfo() {
+      return classNameComputationInfo;
     }
 
     @Override
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/DexItemBasedConstString.java b/src/main/java/com/android/tools/r8/ir/code/DexItemBasedConstString.java
index 3ec7971..2b54a4b 100644
--- a/src/main/java/com/android/tools/r8/ir/code/DexItemBasedConstString.java
+++ b/src/main/java/com/android/tools/r8/ir/code/DexItemBasedConstString.java
@@ -13,25 +13,38 @@
 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;
+import com.android.tools.r8.ir.optimize.ReflectionOptimizer.ClassNameComputationInfo;
 
 public class DexItemBasedConstString extends ConstInstruction {
 
   private final DexReference item;
+  private final ClassNameComputationInfo classNameComputationInfo;
 
   public DexItemBasedConstString(Value dest, DexReference item) {
+    this(dest, item, ClassNameComputationInfo.none());
+  }
+
+  public DexItemBasedConstString(
+      Value dest, DexReference item, ClassNameComputationInfo classNameComputationInfo) {
     super(dest);
     dest.markNeverNull();
     this.item = item;
+    this.classNameComputationInfo = classNameComputationInfo;
   }
 
   public static DexItemBasedConstString copyOf(Value newValue, DexItemBasedConstString original) {
-    return new DexItemBasedConstString(newValue, original.getItem());
+    return new DexItemBasedConstString(
+        newValue, original.getItem(), original.classNameComputationInfo);
   }
 
   public DexReference getItem() {
     return item;
   }
 
+  public ClassNameComputationInfo getClassNameComputationInfo() {
+    return classNameComputationInfo;
+  }
+
   @Override
   public boolean isDexItemBasedConstString() {
     return true;
@@ -45,7 +58,10 @@
   @Override
   public void buildDex(DexBuilder builder) {
     int dest = builder.allocatedRegister(outValue(), getNumber());
-    builder.add(this, new com.android.tools.r8.code.DexItemBasedConstString(dest, item));
+    builder.add(
+        this,
+        new com.android.tools.r8.code.DexItemBasedConstString(
+            dest, item, classNameComputationInfo));
   }
 
   @Override
@@ -99,7 +115,7 @@
 
   @Override
   public void buildCf(CfBuilder builder) {
-    builder.add(new CfDexItemBasedConstString(item));
+    builder.add(new CfDexItemBasedConstString(item, classNameComputationInfo));
   }
 
   @Override
@@ -109,6 +125,6 @@
 
   @Override
   public TypeLatticeElement evaluate(AppInfo appInfo) {
-    return TypeLatticeElement.fromDexType(appInfo.dexItemFactory.stringType, false, appInfo);
+    return TypeLatticeElement.stringClassType(appInfo);
   }
 }
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/Value.java b/src/main/java/com/android/tools/r8/ir/code/Value.java
index 644dfa3..b4ad228 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Value.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Value.java
@@ -726,6 +726,12 @@
     return isConstant() && getConstInstruction().isDexItemBasedConstString();
   }
 
+  public boolean isDexItemBasedConstStringThatNeedsToComputeClassName() {
+    return isDexItemBasedConstString()
+        && getConstInstruction().asDexItemBasedConstString()
+            .getClassNameComputationInfo().needsToComputeClassName();
+  }
+
   public boolean isConstClass() {
     return isConstant() && getConstInstruction().isConstClass();
   }
@@ -762,7 +768,9 @@
    * Returns whether this value is known to never be <code>null</code>.
    */
   public boolean isNeverNull() {
-    return neverNull || (definition != null && definition.isNonNull());
+    return neverNull
+        || (definition != null && definition.isNonNull())
+        || (typeLattice.isReference() && typeLattice.nullElement().isDefinitelyNotNull());
   }
 
   public boolean canBeNull() {
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/CfBuilder.java b/src/main/java/com/android/tools/r8/ir/conversion/CfBuilder.java
index a658474..8f32081 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/CfBuilder.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/CfBuilder.java
@@ -28,7 +28,6 @@
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.GraphLense;
 import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
-import com.android.tools.r8.ir.code.Add;
 import com.android.tools.r8.ir.code.Argument;
 import com.android.tools.r8.ir.code.BasicBlock;
 import com.android.tools.r8.ir.code.CatchHandlers;
@@ -45,7 +44,6 @@
 import com.android.tools.r8.ir.code.Position;
 import com.android.tools.r8.ir.code.StackValue;
 import com.android.tools.r8.ir.code.StackValues;
-import com.android.tools.r8.ir.code.Store;
 import com.android.tools.r8.ir.code.Value;
 import com.android.tools.r8.ir.code.Xor;
 import com.android.tools.r8.ir.optimize.CodeRewriter;
@@ -385,75 +383,59 @@
 
   private void rewriteIincPatterns() {
     for (BasicBlock block : code.blocks) {
-      if (block.getInstructions().size() < IINC_PATTERN_SIZE) {
-        continue;
-      }
-      int earliestAddInstrIdx = 2;
-      int latestAddInstrIdx = block.getInstructions().size() - 3;
       ListIterator<Instruction> it = block.getInstructions().listIterator();
-      int instrIdx = -1;
-      while (it.hasNext()) {
-        ++instrIdx;
-        Instruction current = it.next();
-        if (instrIdx < earliestAddInstrIdx || latestAddInstrIdx < instrIdx || !current.isAdd()) {
-          continue;
-        }
-        it.previous();
-        it.previous();
-        it.previous();
-        Instruction instruction0 = it.next();
-        Instruction instruction1 = it.next();
-        Add instruction2 = it.next().asAdd();
-        Store instruction3 = it.next().asStore();
-
-        // Set bail-out position after Add.
-        it.previous();
-
-        if (instruction3 == null) {
+      // Test that we have enough instructions for iinc.
+      while (IINC_PATTERN_SIZE <= block.getInstructions().size() - it.nextIndex()) {
+        Instruction loadOrConst1 = it.next();
+        if (!loadOrConst1.isLoad() && !loadOrConst1.isConstNumber()) {
           continue;
         }
         Load load;
         ConstNumber constNumber;
-
-        if (instruction0.isLoad()) {
-          load = instruction0.asLoad();
-          constNumber = instruction1.asConstNumber();
+        if (loadOrConst1.isLoad()) {
+          load = loadOrConst1.asLoad();
+          constNumber = it.next().asConstNumber();
         } else {
-          constNumber = instruction0.asConstNumber();
-          load = instruction1.asLoad();
+          load = it.next().asLoad();
+          constNumber = loadOrConst1.asConstNumber();
         }
-
+        Instruction add = it.next().asAdd();
+        Instruction store = it.next().asStore();
+        // Reset pointer to load.
+        it.previous();
+        it.previous();
+        it.previous();
+        it.previous();
         if (load == null
             || constNumber == null
+            || add == null
+            || store == null
             || constNumber.outValue().getTypeLattice() != TypeLatticeElement.INT) {
+          it.next();
           continue;
         }
-
         int increment = constNumber.getIntValue();
         if (increment < Byte.MIN_VALUE || Byte.MAX_VALUE < increment) {
+          it.next();
           continue;
         }
-
-        int register = getLocalRegister(load.inValues().get(0));
-        if (register != getLocalRegister(instruction3.outValue())) {
+        if (getLocalRegister(load.src()) != getLocalRegister(store.outValue())) {
+          it.next();
           continue;
         }
-        Position position = instruction2.getPosition();
-        if (position != instruction0.getPosition()
-            || position != instruction1.getPosition()
-            || position != instruction3.getPosition()) {
+        Position position = add.getPosition();
+        if (position != load.getPosition()
+            || position != constNumber.getPosition()
+            || position != store.getPosition()) {
           continue;
         }
-        it.previous();
-        it.previous();
-        it.previous();
         it.remove();
         it.next();
         it.remove();
         it.next();
         it.remove();
         it.next();
-        Inc inc = new Inc(instruction3.outValue(), load.inValues().get(0), increment);
+        Inc inc = new Inc(store.outValue(), load.inValues().get(0), increment);
         inc.setPosition(position);
         inc.setBlock(block);
         it.set(inc);
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 f0d5d7b..20c04ab 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
@@ -36,6 +36,8 @@
 import com.android.tools.r8.ir.code.Instruction;
 import com.android.tools.r8.ir.code.InstructionListIterator;
 import com.android.tools.r8.ir.code.InvokeMethod;
+import com.android.tools.r8.ir.code.InvokeStatic;
+import com.android.tools.r8.ir.code.NumericType;
 import com.android.tools.r8.ir.code.Value;
 import com.android.tools.r8.ir.desugar.CovariantReturnTypeAnnotationTransformer;
 import com.android.tools.r8.ir.desugar.InterfaceMethodRewriter;
@@ -54,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;
@@ -74,6 +77,7 @@
 import com.android.tools.r8.utils.Timing;
 import com.google.common.base.Suppliers;
 import com.google.common.collect.ArrayListMultimap;
+import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.ListMultimap;
 import com.google.common.collect.Sets;
 import java.util.ArrayList;
@@ -93,6 +97,7 @@
 import java.util.function.BiConsumer;
 import java.util.function.Function;
 import java.util.function.Predicate;
+import java.util.function.Supplier;
 import java.util.stream.Collectors;
 
 public class IRConverter {
@@ -175,7 +180,8 @@
       assert appInfo.hasLiveness();
       AppInfoWithLiveness appInfoWithLiveness = appInfo.withLiveness();
       AppView<? extends AppInfoWithLiveness> appViewWithLiveness = appView.withLiveness();
-      this.nonNullTracker = new NonNullTracker(appInfo);
+      this.nonNullTracker =
+          new NonNullTracker(appInfo, libraryMethodsReturningNonNull(appInfo.dexItemFactory));
       this.inliner = new Inliner(appViewWithLiveness, this, options);
       this.outliner = new Outliner(appInfoWithLiveness, options, this);
       this.memberValuePropagation =
@@ -288,6 +294,16 @@
     return methods;
   }
 
+  // Library methods listed here are based on their original implementations. That is, we assume
+  // these cannot be overridden.
+  public static Set<DexMethod> libraryMethodsReturningNonNull(DexItemFactory factory) {
+    return ImmutableSet.of(
+        factory.stringMethods.valueOf,
+        factory.classMethods.getName,
+        factory.classMethods.getSimpleName
+    );
+  }
+
   private void removeLambdaDeserializationMethods() {
     if (lambdaRewriter != null) {
       lambdaRewriter.removeLambdaDeserializationMethods(appInfo.classes());
@@ -887,27 +903,29 @@
       inliner.performInlining(method, code, isProcessedConcurrently, callSiteInformation);
     }
 
-    // Either marked by IdentifierNameStringMarker or propagated from inlinee.
-    // Then, make it visible to IdentifierMinifier.
-    if (method.getOptimizationInfo().useIdentifierNameString()) {
-      feedback.markUseIdentifierNameString(method);
-    }
-
     if (appInfo.hasLiveness()) {
       // Reflection optimization 1. getClass() -> const-class
-      codeRewriter.rewriteGetClass(code);
+      ReflectionOptimizer.rewriteGetClass(appInfo.withLiveness(), code);
     }
 
     if (!isDebugMode) {
       // TODO(jsjeon): Consider merging these into one single optimize().
       stringOptimizer.computeTrivialOperationsOnConstString(code, appInfo.dexItemFactory);
       // Reflection optimization 2. get*Name() with const-class -> const-string
-      stringOptimizer.rewriteClassGetName(code, appInfo);
+      if (options.enableNameReflectionOptimization) {
+        stringOptimizer.rewriteClassGetName(code, appInfo);
+      }
       // Reflection optimization 3. String#valueOf(const-string) -> no op.
       stringOptimizer.removeTrivialConversions(code, appInfo);
       assert code.isConsistentSSA();
     }
 
+    // Either marked by IdentifierNameStringMarker or name reflection, or propagated from inlinee.
+    // Then, make it visible to IdentifierMinifier.
+    if (method.getOptimizationInfo().useIdentifierNameString()) {
+      feedback.markUseIdentifierNameString(method);
+    }
+
     if (devirtualizer != null) {
       assert code.verifyTypes(appInfo, appView, graphLense());
       devirtualizer.devirtualizeInvokeInterface(code, method.method.getHolder());
@@ -1243,20 +1261,116 @@
     }
   }
 
+  /**
+   * For each block, we look to see if the header matches:
+   *
+   * <pre>
+   *   pseudo-instructions*
+   *   v2 <- long-{mul,div} v0 v1
+   *   pseudo-instructions*
+   *   v5 <- long-{add,sub} v3 v4
+   * </pre>
+   *
+   * where v2 ~=~ v3 or v2 ~=~ v4 (with ~=~ being equal or an alias of) and the block is not a
+   * fallthrough target.
+   */
   private void materializeInstructionBeforeLongOperationsWorkaround(IRCode code) {
     if (!options.canHaveDex2OatLinkedListBug()) {
       return;
     }
+    DexItemFactory factory = options.itemFactory;
+    final Supplier<DexMethod> javaLangLangSignum =
+        Suppliers.memoize(
+            () ->
+                factory.createMethod(
+                    factory.createString("Ljava/lang/Long;"),
+                    factory.createString("signum"),
+                    factory.intDescriptor,
+                    new DexString[] {factory.longDescriptor}));
     for (BasicBlock block : code.blocks) {
       InstructionListIterator it = block.listIterator();
-      Instruction firstMaterializing =
-          it.nextUntil(IRConverter::isMaterializingInstructionOnArtArmVersionM);
-      if (needsInstructionBeforeLongOperation(firstMaterializing)) {
-        ensureInstructionBefore(code, firstMaterializing, it);
+      Instruction firstMaterializing = it.nextUntil(IRConverter::isNotPseudoInstruction);
+      if (!isLongMul(firstMaterializing)) {
+        continue;
+      }
+      Instruction secondMaterializing = it.nextUntil(IRConverter::isNotPseudoInstruction);
+      if (!isLongAddOrSub(secondMaterializing)) {
+        continue;
+      }
+      if (isFallthoughTarget(block)) {
+        continue;
+      }
+      Value outOfMul = firstMaterializing.outValue();
+      for (Value inOfAddOrSub : secondMaterializing.inValues()) {
+        if (isAliasOf(inOfAddOrSub, outOfMul)) {
+          it = block.listIterator();
+          it.nextUntil(i -> i == firstMaterializing);
+          Value longValue = firstMaterializing.inValues().get(0);
+          InvokeStatic invokeLongSignum =
+              new InvokeStatic(
+                  javaLangLangSignum.get(), null, Collections.singletonList(longValue));
+          ensureThrowingInstructionBefore(code, firstMaterializing, it, invokeLongSignum);
+          return;
+        }
       }
     }
   }
 
+  private static boolean isAliasOf(Value usedValue, Value definingValue) {
+    while (true) {
+      if (usedValue == definingValue) {
+        return true;
+      }
+      Instruction definition = usedValue.definition;
+      if (definition == null || !definition.isMove()) {
+        return false;
+      }
+      usedValue = definition.asMove().src();
+    }
+  }
+
+  private static boolean isNotPseudoInstruction(Instruction instruction) {
+    return !(instruction.isDebugInstruction() || instruction.isMove());
+  }
+
+  private static boolean isLongMul(Instruction instruction) {
+    return instruction != null
+        && instruction.isMul()
+        && instruction.asBinop().getNumericType() == NumericType.LONG
+        && instruction.outValue() != null;
+  }
+
+  private static boolean isLongAddOrSub(Instruction instruction) {
+    return instruction != null
+        && (instruction.isAdd() || instruction.isSub())
+        && instruction.asBinop().getNumericType() == NumericType.LONG;
+  }
+
+  private static boolean isFallthoughTarget(BasicBlock block) {
+    for (BasicBlock pred : block.getPredecessors()) {
+      if (pred.exit().fallthroughBlock() == block) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  private void ensureThrowingInstructionBefore(
+      IRCode code, Instruction addBefore, InstructionListIterator it, Instruction instruction) {
+    Instruction check = it.previous();
+    assert addBefore == check;
+    BasicBlock block = check.getBlock();
+    if (block.hasCatchHandlers()) {
+      // Split so the existing instructions retain their handlers and the new instruction has none.
+      BasicBlock split = it.split(code);
+      assert split.hasCatchHandlers();
+      assert !block.hasCatchHandlers();
+      it = block.listIterator(block.getInstructions().size() - 1);
+    }
+    instruction.setPosition(addBefore.getPosition());
+    it.add(instruction);
+  }
+
   private static void ensureInstructionBefore(
       IRCode code, Instruction addBefore, InstructionListIterator it) {
     // Force materialize a constant-zero before the long operation.
@@ -1275,33 +1389,6 @@
     it.add(fixitUser);
   }
 
-  private static boolean needsInstructionBeforeLongOperation(Instruction instruction) {
-    // The cortex fixup will only trigger on long sub and long add instructions.
-    if (!((instruction.isAdd() || instruction.isSub()) && instruction.outType().isWide())) {
-      return false;
-    }
-    // If the block with the instruction is a fallthrough block, then it can't end up being
-    // preceded by the incorrectly linked prologue/epilogue..
-    BasicBlock block = instruction.getBlock();
-    for (BasicBlock pred : block.getPredecessors()) {
-      if (pred.exit().fallthroughBlock() == block) {
-        return false;
-      }
-    }
-    return true;
-  }
-
-  private static boolean isMaterializingInstructionOnArtArmVersionM(Instruction instruction) {
-    return !instruction.isDebugInstruction()
-        && !instruction.isMove()
-        && !isPossiblyNonMaterializingLongOperationOnArtArmVersionM(instruction);
-  }
-
-  private static boolean isPossiblyNonMaterializingLongOperationOnArtArmVersionM(
-      Instruction instruction) {
-    return (instruction.isMul() || instruction.isDiv()) && instruction.outType().isWide();
-  }
-
   private void printC1VisualizerHeader(DexEncodedMethod method) {
     if (printer != null) {
       printer.begin("compilation");
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackDelayed.java b/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackDelayed.java
index 3ef25f5..5dbdbe1 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackDelayed.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackDelayed.java
@@ -59,7 +59,7 @@
   }
 
   @Override
-  public void markUseIdentifierNameString(DexEncodedMethod method) {
+  public synchronized void markUseIdentifierNameString(DexEncodedMethod method) {
     getOptimizationInfoForUpdating(method).markUseIdentifierNameString();
   }
 
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/desugar/LambdaClass.java b/src/main/java/com/android/tools/r8/ir/desugar/LambdaClass.java
index 01555da..7a9ec00 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/LambdaClass.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/LambdaClass.java
@@ -531,6 +531,7 @@
                   encodedMethod.annotations,
                   encodedMethod.parameterAnnotationsList,
                   encodedMethod.getCode());
+          newMethod.copyMetadata(encodedMethod);
           rewriter.methodMapping.put(encodedMethod.method, callTarget);
           // TODO(ager): Should we give the new first parameter an actual name? Maybe 'this'?
           DexCode dexCode = newMethod.getCode().asDexCode();
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 553eaa2..0b54a4d 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
@@ -4,6 +4,11 @@
 
 package com.android.tools.r8.ir.optimize;
 
+import static com.android.tools.r8.ir.optimize.ReflectionOptimizer.ClassNameComputationInfo.ClassNameComputationOption.CANONICAL_NAME;
+import static com.android.tools.r8.ir.optimize.ReflectionOptimizer.ClassNameComputationInfo.ClassNameComputationOption.NAME;
+import static com.android.tools.r8.ir.optimize.ReflectionOptimizer.ClassNameComputationInfo.ClassNameComputationOption.SIMPLE_NAME;
+import static com.android.tools.r8.ir.optimize.ReflectionOptimizer.computeClassName;
+
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.errors.CompilationError;
 import com.android.tools.r8.errors.Unreachable;
@@ -47,7 +52,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;
@@ -151,8 +155,10 @@
   private final Set<DexMethod> libraryMethodsReturningReceiver;
   private final InternalOptions options;
 
-  public CodeRewriter(IRConverter converter,
-      Set<DexMethod> libraryMethodsReturningReceiver, InternalOptions options) {
+  public CodeRewriter(
+      IRConverter converter,
+      Set<DexMethod> libraryMethodsReturningReceiver,
+      InternalOptions options) {
     this.converter = converter;
     this.appInfo = converter.appInfo;
     this.options = options;
@@ -1531,15 +1537,15 @@
       return;
     }
     AppInfoWithLiveness appInfoWithLiveness = appInfo.withLiveness();
+    Set<Value> needToWidenValues = Sets.newIdentityHashSet();
+    Set<Value> needToNarrowValues = Sets.newIdentityHashSet();
     InstructionIterator iterator = code.instructionIterator();
     while (iterator.hasNext()) {
       Instruction current = iterator.next();
       if (current.isInvokeMethod()) {
         InvokeMethod invoke = current.asInvokeMethod();
         if (invoke.outValue() != null && !invoke.outValue().hasLocalInfo()) {
-          boolean isLibraryMethodReturningReceiver =
-              libraryMethodsReturningReceiver.contains(invoke.getInvokedMethod());
-          if (isLibraryMethodReturningReceiver) {
+          if (libraryMethodsReturningReceiver.contains(invoke.getInvokedMethod())) {
             if (checkArgumentType(invoke, invoke.getInvokedMethod(), 0)) {
               invoke.outValue().replaceUsers(invoke.arguments().get(0));
               invoke.setOutValue(null);
@@ -1554,11 +1560,18 @@
               if (definition != null && definition.getOptimizationInfo().returnsArgument()) {
                 int argumentIndex = definition.getOptimizationInfo().getReturnedArgument();
                 // Replace the out value of the invoke with the argument and ignore the out value.
-                if (argumentIndex != -1 && checkArgumentType(invoke, target.method,
-                    argumentIndex)) {
+                if (argumentIndex != -1
+                    && checkArgumentType(invoke, target.method, argumentIndex)) {
                   Value argument = invoke.arguments().get(argumentIndex);
-                  assert invoke.outValue().verifyCompatible(argument.outType());
-                  invoke.outValue().replaceUsers(argument);
+                  Value outValue = invoke.outValue();
+                  assert outValue.verifyCompatible(argument.outType());
+                  if (argument.getTypeLattice().lessThanOrEqual(
+                      outValue.getTypeLattice(), appInfo)) {
+                    needToNarrowValues.addAll(outValue.affectedValues());
+                  } else {
+                    needToWidenValues.addAll(outValue.affectedValues());
+                  }
+                  outValue.replaceUsers(argument);
                   invoke.setOutValue(null);
                 }
               }
@@ -1567,6 +1580,17 @@
         }
       }
     }
+    if (!needToWidenValues.isEmpty() || !needToNarrowValues.isEmpty()) {
+      TypeAnalysis analysis = new TypeAnalysis(appInfo, code.method);
+      // If out value of invoke < argument (e.g., losing non-null info), widen users type.
+      if (!needToWidenValues.isEmpty()) {
+        analysis.widening(needToWidenValues);
+      }
+      // Otherwise, i.e., argument has more precise types, narrow users type.
+      if (!needToNarrowValues.isEmpty()) {
+        analysis.narrowing(needToNarrowValues);
+      }
+    }
     assert code.isConsistentGraph();
   }
 
@@ -1726,7 +1750,7 @@
   }
 
   // Check if the static put is a constant derived from the class holding the method.
-  // This checks for java.lang.Class.getName and java.lang.Class.getSimpleName.
+  // This checks for java.lang.Class.get*Name.
   private boolean isClassNameConstantOf(DexClass clazz, StaticPut put) {
     if (put.getField().type != dexItemFactory.stringType) {
       return false;
@@ -1740,8 +1764,7 @@
   private boolean isClassNameConstantOf(DexClass clazz, Instruction instruction) {
     if (instruction.isInvokeVirtual()) {
       InvokeVirtual invoke = instruction.asInvokeVirtual();
-      if ((invoke.getInvokedMethod() == dexItemFactory.classMethods.getSimpleName
-          || invoke.getInvokedMethod() == dexItemFactory.classMethods.getName)
+      if (dexItemFactory.classMethods.isReflectiveNameLookup(invoke.getInvokedMethod())
           && !invoke.inValues().get(0).isPhi()
           && invoke.inValues().get(0).definition.isConstClass()
           && invoke.inValues().get(0).definition.asConstClass().getValue() == clazz.type) {
@@ -1785,21 +1808,32 @@
             } else if (inValue.isDexItemBasedConstString()) {
               DexItemBasedConstString cnst =
                   inValue.getConstInstruction().asDexItemBasedConstString();
-              encodedField.setStaticValue(new DexItemBasedValueString(cnst.getItem()));
+              assert !cnst.getClassNameComputationInfo().needsToComputeClassName();
+              encodedField.setStaticValue(
+                  new DexItemBasedValueString(cnst.getItem(), cnst.getClassNameComputationInfo()));
             } else {
               assert false;
             }
           } else {
+            // TODO(b/120280603): Consider minification!
             InvokeVirtual invoke = inValue.definition.asInvokeVirtual();
-            String name = method.method.getHolder().toSourceString();
-            if (invoke.getInvokedMethod() == dexItemFactory.classMethods.getSimpleName) {
-              String simpleName = name.substring(name.lastIndexOf('.') + 1);
-              encodedField.setStaticValue(
-                  new DexValueString(dexItemFactory.createString(simpleName)));
-            } else {
-              assert invoke.getInvokedMethod() == dexItemFactory.classMethods.getName;
-              encodedField.setStaticValue(new DexValueString(dexItemFactory.createString(name)));
+            DexMethod invokedMethod = invoke.getInvokedMethod();
+            DexType holderType = method.method.getHolder();
+            DexClass holder = appInfo.definitionFor(holderType);
+            assert holder != null;
+            String descriptor = holderType.toDescriptorString();
+            String name = null;
+            if (invokedMethod == appInfo.dexItemFactory.classMethods.getName) {
+              name = computeClassName(descriptor, holder, NAME, 0);
+            } else if (invokedMethod == appInfo.dexItemFactory.classMethods.getTypeName) {
+              // TODO(b/119426668): desugar Type#getTypeName
+            } else if (invokedMethod == appInfo.dexItemFactory.classMethods.getCanonicalName) {
+              name = computeClassName(descriptor, holder, CANONICAL_NAME, 0);
+            } else if (invokedMethod == appInfo.dexItemFactory.classMethods.getSimpleName) {
+              name = computeClassName(descriptor, holder, SIMPLE_NAME, 0);
             }
+            assert name != null;
+            encodedField.setStaticValue(new DexValueString(dexItemFactory.createString(name)));
           }
         } else if (field.type.isClassType() || field.type.isArrayType()) {
           if (inValue.isZero()) {
@@ -1886,6 +1920,9 @@
               }
               DexField field = put.getField();
               if (clazz.definesStaticField(field)) {
+                if (put.inValue().isDexItemBasedConstStringThatNeedsToComputeClassName()) {
+                  continue;
+                }
                 if (put.inValue().isConstant()) {
                   if ((field.type.isClassType() || field.type.isArrayType())
                       && put.inValue().isZero()) {
@@ -1924,67 +1961,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/DefaultInliningOracle.java b/src/main/java/com/android/tools/r8/ir/optimize/DefaultInliningOracle.java
index bad5456..be94302 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/DefaultInliningOracle.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/DefaultInliningOracle.java
@@ -16,6 +16,7 @@
 import com.android.tools.r8.ir.code.InvokeStatic;
 import com.android.tools.r8.ir.code.Value;
 import com.android.tools.r8.ir.conversion.CallSiteInformation;
+import com.android.tools.r8.ir.conversion.IRConverter;
 import com.android.tools.r8.ir.optimize.Inliner.InlineAction;
 import com.android.tools.r8.ir.optimize.Inliner.InlineeWithReason;
 import com.android.tools.r8.ir.optimize.Inliner.Reason;
@@ -427,7 +428,8 @@
       assert IteratorUtils.peekNext(blockIterator) == block;
 
       // Kick off the tracker to add non-null IRs only to the inlinee blocks.
-      new NonNullTracker(appView.appInfo())
+      new NonNullTracker(appView.appInfo(),
+          IRConverter.libraryMethodsReturningNonNull(appView.dexItemFactory()))
           .addNonNullInPart(code, blockIterator, inlinee.blocks::contains);
       assert !blockIterator.hasNext();
 
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java b/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java
index 63d0242..3c27a60 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java
@@ -647,7 +647,7 @@
                 context.accessFlags.unsetBridge();
               }
 
-              context.copyMetadataFromInlinee(target);
+              context.copyMetadata(target);
               code.copyMetadataFromInlinee(inlinee.code);
             }
           }
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/MemberValuePropagation.java b/src/main/java/com/android/tools/r8/ir/optimize/MemberValuePropagation.java
index 29c7979..b82c743 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/MemberValuePropagation.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/MemberValuePropagation.java
@@ -178,7 +178,12 @@
           DexEncodedMethod target = invoke.lookupSingleTarget(appInfo, callingContext);
           if (target != null) {
             if (target.getOptimizationInfo().neverReturnsNull() && invoke.outValue().canBeNull()) {
-              invoke.outValue().markNeverNull();
+              Value knownToBeNonNullValue = invoke.outValue();
+              knownToBeNonNullValue.markNeverNull();
+              TypeLatticeElement typeLattice = knownToBeNonNullValue.getTypeLattice();
+              assert typeLattice.isNullable() && typeLattice.isReference();
+              knownToBeNonNullValue.narrowing(appInfo, typeLattice.asNonNullable());
+              affectedValues.addAll(knownToBeNonNullValue.affectedValues());
             }
             if (target.getOptimizationInfo().returnsConstant()) {
               long constant = target.getOptimizationInfo().getReturnedConstant();
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/NonNullTracker.java b/src/main/java/com/android/tools/r8/ir/optimize/NonNullTracker.java
index 77339e0..1e62c36 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/NonNullTracker.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/NonNullTracker.java
@@ -7,6 +7,7 @@
 
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.AppInfo;
+import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.ir.analysis.type.TypeAnalysis;
 import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.BasicBlock;
@@ -34,9 +35,11 @@
 public class NonNullTracker {
 
   private final AppInfo appInfo;
+  private final Set<DexMethod> libraryMethodsReturningNonNull;
 
-  public NonNullTracker(AppInfo appInfo) {
+  public NonNullTracker(AppInfo appInfo, Set<DexMethod> libraryMethodsReturningNonNull) {
     this.appInfo = appInfo;
+    this.libraryMethodsReturningNonNull = libraryMethodsReturningNonNull;
   }
 
   @VisibleForTesting
@@ -76,102 +79,48 @@
   public void addNonNullInPart(
       IRCode code, ListIterator<BasicBlock> blockIterator, Predicate<BasicBlock> blockTester) {
     Set<Value> affectedValues = Sets.newIdentityHashSet();
+    Set<Value> knownToBeNonNullValues = Sets.newIdentityHashSet();
     while (blockIterator.hasNext()) {
       BasicBlock block = blockIterator.next();
       if (!blockTester.test(block)) {
         continue;
       }
-      // Add non-null after instructions that implicitly indicate receiver/array is not null.
+      // Add non-null after
+      // 1) invocations that call non-overridable library methods that are known to return non null.
+      // 2) instructions that implicitly indicate receiver/array is not null.
+      // TODO(b/71500340): We can add non-null IRs for known-to-be-non-null parameters here.
       InstructionListIterator iterator = block.listIterator();
       while (iterator.hasNext()) {
         Instruction current = iterator.next();
-        if (!throwsOnNullInput(current)) {
-          continue;
-        }
-        Value knownToBeNonNullValue = getNonNullInput(current);
-        TypeLatticeElement typeLattice = knownToBeNonNullValue.getTypeLattice();
-        // Avoid adding redundant non-null instruction.
-        if (knownToBeNonNullValue.isNeverNull() || !isNonNullCandidate(typeLattice)) {
+        if (current.isInvokeMethod()
+            && libraryMethodsReturningNonNull.contains(
+                current.asInvokeMethod().getInvokedMethod())) {
+          Value knownToBeNonNullValue = current.outValue();
+          // Avoid adding redundant non-null instruction.
           // Otherwise, we will have something like:
           // non_null_rcv <- non-null(rcv)
           // ...
           // another_rcv <- non-null(non_null_rcv)
-          continue;
-        }
-        // First, if the current block has catch handler, split into two blocks, e.g.,
-        //
-        // ...x
-        // invoke(rcv, ...)
-        // ...y
-        //
-        //   ~>
-        //
-        // ...x
-        // invoke(rcv, ...)
-        // goto A
-        //
-        // A: ...y // blockWithNonNullInstruction
-        boolean split = block.hasCatchHandlers();
-        BasicBlock blockWithNonNullInstruction =
-            split ? iterator.split(code, blockIterator) : block;
-
-        // Find all users of the original value that are dominated by either the current block
-        // or the new split-off block. Since NPE can be explicitly caught, nullness should be
-        // propagated through dominance.
-        Set<Instruction> users = knownToBeNonNullValue.uniqueUsers();
-        Set<Instruction> dominatedUsers = Sets.newIdentityHashSet();
-        Map<Phi, IntList> dominatedPhiUsersWithPositions = new IdentityHashMap<>();
-        DominatorTree dominatorTree = new DominatorTree(code, MAY_HAVE_UNREACHABLE_BLOCKS);
-        Set<BasicBlock> dominatedBlocks = Sets.newIdentityHashSet();
-        for (BasicBlock dominatee : dominatorTree.dominatedBlocks(blockWithNonNullInstruction)) {
-          dominatedBlocks.add(dominatee);
-          InstructionListIterator dominateeIterator = dominatee.listIterator();
-          if (dominatee == blockWithNonNullInstruction && !split) {
-            // In the block where the non null instruction will be inserted, skip instructions up
-            // to and including the insertion point.
-            dominateeIterator.nextUntil(instruction -> instruction == current);
-          }
-          while (dominateeIterator.hasNext()) {
-            Instruction potentialUser = dominateeIterator.next();
-            if (users.contains(potentialUser)) {
-              dominatedUsers.add(potentialUser);
-            }
+          if (knownToBeNonNullValue != null && isNonNullCandidate(knownToBeNonNullValue)) {
+            knownToBeNonNullValues.add(knownToBeNonNullValue);
           }
         }
-        for (Phi user : knownToBeNonNullValue.uniquePhiUsers()) {
-          IntList dominatedPredecessorIndexes =
-              findDominatedPredecessorIndexesInPhi(user, knownToBeNonNullValue, dominatedBlocks);
-          if (!dominatedPredecessorIndexes.isEmpty()) {
-            dominatedPhiUsersWithPositions.put(user, dominatedPredecessorIndexes);
+        if (throwsOnNullInput(current)) {
+          Value knownToBeNonNullValue = getNonNullInput(current);
+          if (isNonNullCandidate(knownToBeNonNullValue)) {
+            knownToBeNonNullValues.add(knownToBeNonNullValue);
           }
         }
-
-        // Only insert non-null instruction if it is ever used.
-        if (!dominatedUsers.isEmpty() || !dominatedPhiUsersWithPositions.isEmpty()) {
-          // Add non-null fake IR, e.g.,
-          // ...x
-          // invoke(rcv, ...)
-          // goto A
-          // ...
-          // A: non_null_rcv <- non-null(rcv)
-          // ...y
-          Value nonNullValue = code.createValue(
-              typeLattice.asNonNullable(), knownToBeNonNullValue.getLocalInfo());
-          affectedValues.addAll(knownToBeNonNullValue.affectedValues());
-          NonNull nonNull = new NonNull(nonNullValue, knownToBeNonNullValue, current);
-          nonNull.setPosition(current.getPosition());
-          if (blockWithNonNullInstruction != block) {
-            // If we split, add non-null IR on top of the new split block.
-            blockWithNonNullInstruction.listIterator().add(nonNull);
-          } else {
-            // Otherwise, just add it to the current block at the position of the iterator.
-            iterator.add(nonNull);
-          }
-
-          // Replace all users of the original value that are dominated by either the current
-          // block or the new split-off block.
-          knownToBeNonNullValue.replaceSelectiveUsers(
-              nonNullValue, dominatedUsers, dominatedPhiUsersWithPositions);
+        if (!knownToBeNonNullValues.isEmpty()) {
+          addNonNullForValues(
+              code,
+              blockIterator,
+              block,
+              iterator,
+              current,
+              knownToBeNonNullValues,
+              affectedValues);
+          knownToBeNonNullValues.clear();
         }
       }
 
@@ -200,9 +149,8 @@
         // ...
         If theIf = block.exit().asIf();
         Value knownToBeNonNullValue = theIf.inValues().get(0);
-        TypeLatticeElement typeLattice = knownToBeNonNullValue.getTypeLattice();
-        // Avoid adding redundant non-null instruction (or non-null of non-object types).
-        if (!knownToBeNonNullValue.isNeverNull() && isNonNullCandidate(typeLattice)) {
+        // Avoid adding redundant non-null instruction.
+        if (isNonNullCandidate(knownToBeNonNullValue)) {
           BasicBlock target = theIf.targetFromNonNullObject();
           // Ignore uncommon empty blocks.
           if (!target.isEmpty()) {
@@ -228,6 +176,7 @@
               }
               // Avoid adding a non-null for the value without meaningful users.
               if (!dominatedUsers.isEmpty() || !dominatedPhiUsersWithPositions.isEmpty()) {
+                TypeLatticeElement typeLattice = knownToBeNonNullValue.getTypeLattice();
                 Value nonNullValue = code.createValue(
                     typeLattice.asNonNullable(), knownToBeNonNullValue.getLocalInfo());
                 affectedValues.addAll(knownToBeNonNullValue.affectedValues());
@@ -249,6 +198,93 @@
     }
   }
 
+  private void addNonNullForValues(
+      IRCode code,
+      ListIterator<BasicBlock> blockIterator,
+      BasicBlock block,
+      InstructionListIterator iterator,
+      Instruction current,
+      Set<Value> knownToBeNonNullValues,
+      Set<Value> affectedValues) {
+    // First, if the current block has catch handler, split into two blocks, e.g.,
+    //
+    // ...x
+    // invoke(rcv, ...)
+    // ...y
+    //
+    //   ~>
+    //
+    // ...x
+    // invoke(rcv, ...)
+    // goto A
+    //
+    // A: ...y // blockWithNonNullInstruction
+    boolean split = block.hasCatchHandlers();
+    BasicBlock blockWithNonNullInstruction = split ? iterator.split(code, blockIterator) : block;
+    DominatorTree dominatorTree = new DominatorTree(code, MAY_HAVE_UNREACHABLE_BLOCKS);
+
+    for (Value knownToBeNonNullValue : knownToBeNonNullValues) {
+      // Find all users of the original value that are dominated by either the current block
+      // or the new split-off block. Since NPE can be explicitly caught, nullness should be
+      // propagated through dominance.
+      Set<Instruction> users = knownToBeNonNullValue.uniqueUsers();
+      Set<Instruction> dominatedUsers = Sets.newIdentityHashSet();
+      Map<Phi, IntList> dominatedPhiUsersWithPositions = new IdentityHashMap<>();
+      Set<BasicBlock> dominatedBlocks = Sets.newIdentityHashSet();
+      for (BasicBlock dominatee : dominatorTree.dominatedBlocks(blockWithNonNullInstruction)) {
+        dominatedBlocks.add(dominatee);
+        InstructionListIterator dominateeIterator = dominatee.listIterator();
+        if (dominatee == blockWithNonNullInstruction && !split) {
+          // In the block where the non null instruction will be inserted, skip instructions up to
+          // and including the insertion point.
+          dominateeIterator.nextUntil(instruction -> instruction == current);
+        }
+        while (dominateeIterator.hasNext()) {
+          Instruction potentialUser = dominateeIterator.next();
+          if (users.contains(potentialUser)) {
+            dominatedUsers.add(potentialUser);
+          }
+        }
+      }
+      for (Phi user : knownToBeNonNullValue.uniquePhiUsers()) {
+        IntList dominatedPredecessorIndexes =
+            findDominatedPredecessorIndexesInPhi(user, knownToBeNonNullValue, dominatedBlocks);
+        if (!dominatedPredecessorIndexes.isEmpty()) {
+          dominatedPhiUsersWithPositions.put(user, dominatedPredecessorIndexes);
+        }
+      }
+
+      // Only insert non-null instruction if it is ever used.
+      if (!dominatedUsers.isEmpty() || !dominatedPhiUsersWithPositions.isEmpty()) {
+        // Add non-null fake IR, e.g.,
+        // ...x
+        // invoke(rcv, ...)
+        // goto A
+        // ...
+        // A: non_null_rcv <- non-null(rcv)
+        // ...y
+        TypeLatticeElement typeLattice = knownToBeNonNullValue.getTypeLattice();
+        Value nonNullValue =
+            code.createValue(typeLattice.asNonNullable(), knownToBeNonNullValue.getLocalInfo());
+        affectedValues.addAll(knownToBeNonNullValue.affectedValues());
+        NonNull nonNull = new NonNull(nonNullValue, knownToBeNonNullValue, current);
+        nonNull.setPosition(current.getPosition());
+        if (blockWithNonNullInstruction != block) {
+          // If we split, add non-null IR on top of the new split block.
+          blockWithNonNullInstruction.listIterator().add(nonNull);
+        } else {
+          // Otherwise, just add it to the current block at the position of the iterator.
+          iterator.add(nonNull);
+        }
+
+        // Replace all users of the original value that are dominated by either the current block
+        // or the new split-off block.
+        knownToBeNonNullValue.replaceSelectiveUsers(
+            nonNullValue, dominatedUsers, dominatedPhiUsersWithPositions);
+      }
+    }
+  }
+
   private IntList findDominatedPredecessorIndexesInPhi(
       Phi user, Value knownToBeNonNullValue, Set<BasicBlock> dominatedBlocks) {
     assert user.getOperands().contains(knownToBeNonNullValue);
@@ -274,10 +310,13 @@
     return predecessorIndexes;
   }
 
-  private boolean isNonNullCandidate(TypeLatticeElement typeLattice) {
+  private boolean isNonNullCandidate(Value knownToBeNonNullValue) {
+    TypeLatticeElement typeLattice = knownToBeNonNullValue.getTypeLattice();
     return
+        // redundant
+        !knownToBeNonNullValue.isNeverNull()
         // v <- non-null NULL ?!
-        !typeLattice.isNull()
+        && !typeLattice.isConstantNull()
         // v <- non-null known-to-be-non-null // redundant
         && typeLattice.isNullable()
         // e.g., v <- non-null INT ?!
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
new file mode 100644
index 0000000..496e113
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/optimize/ReflectionOptimizer.java
@@ -0,0 +1,189 @@
+// 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.optimize;
+
+import static com.android.tools.r8.utils.DescriptorUtils.getCanonicalNameFromDescriptor;
+import static com.android.tools.r8.utils.DescriptorUtils.getClassNameFromDescriptor;
+import static com.android.tools.r8.utils.DescriptorUtils.getSimpleClassNameFromDescriptor;
+
+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 {
+
+  public static class ClassNameComputationInfo {
+    public enum ClassNameComputationOption {
+      NONE,
+      NAME,           // getName()
+      TYPE_NAME,      // getTypeName()
+      CANONICAL_NAME, // getCanonicalName()
+      SIMPLE_NAME;    // getSimpleName()
+
+      boolean needsToComputeClassName() {
+        return this != NONE;
+      }
+
+      boolean needsToRegisterTypeReference() {
+        return this == SIMPLE_NAME;
+      }
+    }
+
+    private static final ClassNameComputationInfo DEFAULT_INSTANCE =
+        new ClassNameComputationInfo(ClassNameComputationOption.NONE, 0);
+
+    final ClassNameComputationOption classNameComputationOption;
+    final int arrayDepth;
+
+    public ClassNameComputationInfo(
+        ClassNameComputationOption classNameComputationOption, int arrayDepth) {
+      this.classNameComputationOption = classNameComputationOption;
+      this.arrayDepth = arrayDepth;
+    }
+
+    public static ClassNameComputationInfo none() {
+      return DEFAULT_INSTANCE;
+    }
+
+    public boolean needsToComputeClassName() {
+      return classNameComputationOption.needsToComputeClassName();
+    }
+
+    public boolean needsToRegisterTypeReference() {
+      return classNameComputationOption.needsToRegisterTypeReference();
+    }
+  }
+
+  // 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(
+        descriptor.toString(),
+        holder,
+        classNameComputationInfo.classNameComputationOption,
+        classNameComputationInfo.arrayDepth);
+  }
+
+  public static String computeClassName(
+      String descriptor,
+      DexClass holder,
+      ClassNameComputationOption classNameComputationOption,
+      int arrayDepth) {
+    String name;
+    switch (classNameComputationOption) {
+      case NAME:
+        name = getClassNameFromDescriptor(descriptor);
+        if (arrayDepth > 0) {
+          name = Strings.repeat("[", arrayDepth) + "L" + name + ";";
+        }
+        break;
+      case TYPE_NAME:
+        // TODO(b/119426668): desugar Type#getTypeName
+        throw new Unreachable("Type#getTypeName not supported yet");
+        // name = getClassNameFromDescriptor(descriptor);
+        // if (arrayDepth > 0) {
+        //   name = name + Strings.repeat("[]", arrayDepth);
+        // }
+        // break;
+      case CANONICAL_NAME:
+        name = getCanonicalNameFromDescriptor(descriptor);
+        if (arrayDepth > 0) {
+          name = name + Strings.repeat("[]", arrayDepth);
+        }
+        break;
+      case SIMPLE_NAME:
+        assert holder != null;
+        boolean renamed = !descriptor.equals(holder.type.toDescriptorString());
+        boolean needsToRetrieveInnerName = holder.isMemberClass() || holder.isLocalClass();
+        if (!renamed && needsToRetrieveInnerName) {
+          name = holder.getInnerClassAttributeForThisClass().getInnerName().toString();
+        } else {
+          name = getSimpleClassNameFromDescriptor(descriptor);
+        }
+        if (arrayDepth > 0) {
+          name = name + Strings.repeat("[]", arrayDepth);
+        }
+        break;
+      default:
+        throw new Unreachable(
+            "Unexpected ClassNameComputationOption: '" + classNameComputationOption + "'");
+    }
+    return name;
+  }
+
+
+}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/UninstantiatedTypeOptimization.java b/src/main/java/com/android/tools/r8/ir/optimize/UninstantiatedTypeOptimization.java
index a55015d..3ba9289 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/UninstantiatedTypeOptimization.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/UninstantiatedTypeOptimization.java
@@ -249,8 +249,10 @@
     instructionIterator.previous();
 
     // Unlink all blocks that are dominated by successor.
-    DominatorTree dominatorTree = new DominatorTree(code, MAY_HAVE_UNREACHABLE_BLOCKS);
-    blocksToBeRemoved.addAll(block.unlink(normalSuccessorBlock, dominatorTree));
+    {
+      DominatorTree dominatorTree = new DominatorTree(code, MAY_HAVE_UNREACHABLE_BLOCKS);
+      blocksToBeRemoved.addAll(block.unlink(normalSuccessorBlock, dominatorTree));
+    }
 
     // Insert constant null before the instruction.
     instructionIterator.previous();
@@ -284,6 +286,9 @@
               return;
             }
             if (!appView.dexItemFactory().npeType.isSubtypeOf(guard, appView.appInfo())) {
+              // TODO(christofferqa): Consider updating previous dominator tree instead of
+              // rebuilding it from scratch.
+              DominatorTree dominatorTree = new DominatorTree(code, MAY_HAVE_UNREACHABLE_BLOCKS);
               blocksToBeRemoved.addAll(block.unlink(target, dominatorTree));
             }
           });
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/classinliner/InlineCandidateProcessor.java b/src/main/java/com/android/tools/r8/ir/optimize/classinliner/InlineCandidateProcessor.java
index 35cc716..ade48f3 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/classinliner/InlineCandidateProcessor.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/classinliner/InlineCandidateProcessor.java
@@ -399,7 +399,11 @@
         continue;
       }
 
-      throw new Unreachable("Unexpected usage left after method inlining: " + user);
+      throw new Unreachable(
+          "Unexpected usage left in method `"
+              + method.method.toSourceString()
+              + "` after inlining: "
+              + user);
     }
 
     if (needToRemoveUnreachableBlocks) {
@@ -423,7 +427,11 @@
         continue;
       }
 
-      throw new Unreachable("Unexpected usage left after method inlining: " + user);
+      throw new Unreachable(
+          "Unexpected usage left in method `"
+              + method.method.toSourceString()
+              + "` after inlining: "
+              + user);
     }
   }
 
@@ -448,10 +456,18 @@
   private void removeFieldWrites() {
     for (Instruction user : eligibleInstance.uniqueUsers()) {
       if (!user.isInstancePut()) {
-        throw new Unreachable("Unexpected usage left after field reads removed: " + user);
+        throw new Unreachable(
+            "Unexpected usage left in method `"
+                + method.method.toSourceString()
+                + "` after field reads removed: "
+                + user);
       }
       if (user.asInstancePut().getField().clazz != eligibleClass) {
-        throw new Unreachable("Unexpected field write left after field reads removed: " + user);
+        throw new Unreachable(
+            "Unexpected field write left in method `"
+                + method.method.toSourceString()
+                + "` after field reads removed: "
+                + user);
       }
       removeInstruction(user);
     }
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/ir/optimize/string/StringOptimizer.java b/src/main/java/com/android/tools/r8/ir/optimize/string/StringOptimizer.java
index 9fec63a..2e19475 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/string/StringOptimizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/string/StringOptimizer.java
@@ -4,9 +4,11 @@
 package com.android.tools.r8.ir.optimize.string;
 
 import static com.android.tools.r8.ir.optimize.CodeRewriter.removeOrReplaceByDebugLocalWrite;
-import static com.android.tools.r8.utils.DescriptorUtils.getCanonicalNameFromDescriptor;
-import static com.android.tools.r8.utils.DescriptorUtils.getClassNameFromDescriptor;
-import static com.android.tools.r8.utils.DescriptorUtils.getSimpleClassNameFromDescriptor;
+import static com.android.tools.r8.ir.optimize.ReflectionOptimizer.ClassNameComputationInfo.ClassNameComputationOption.CANONICAL_NAME;
+import static com.android.tools.r8.ir.optimize.ReflectionOptimizer.ClassNameComputationInfo.ClassNameComputationOption.NAME;
+import static com.android.tools.r8.ir.optimize.ReflectionOptimizer.ClassNameComputationInfo.ClassNameComputationOption.SIMPLE_NAME;
+import static com.android.tools.r8.ir.optimize.ReflectionOptimizer.computeClassName;
+import static com.android.tools.r8.utils.DescriptorUtils.INNER_CLASS_SEPARATOR;
 
 import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.graph.DexClass;
@@ -18,20 +20,21 @@
 import com.android.tools.r8.ir.code.ConstClass;
 import com.android.tools.r8.ir.code.ConstNumber;
 import com.android.tools.r8.ir.code.ConstString;
+import com.android.tools.r8.ir.code.DexItemBasedConstString;
 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.InvokeStatic;
 import com.android.tools.r8.ir.code.InvokeVirtual;
 import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.ir.optimize.ReflectionOptimizer.ClassNameComputationInfo;
 import com.android.tools.r8.utils.InternalOptions;
-import com.google.common.base.Strings;
 import java.util.function.BiFunction;
 import java.util.function.Function;
 
 public class StringOptimizer {
 
-  final ThrowingInfo throwingInfo;
+  private final ThrowingInfo throwingInfo;
 
   public StringOptimizer(InternalOptions options) {
     throwingInfo = options.isGeneratingClassFiles()
@@ -43,6 +46,9 @@
   // boolean String#startsWith(str)
   // boolean String#endsWith(str)
   // boolean String#contains(str)
+  // boolean String#equals(str)
+  // boolean String#equalsIgnoreCase(str)
+  // boolean String#contentEquals(str)
   public void computeTrivialOperationsOnConstString(IRCode code, DexItemFactory factory) {
     if (!code.hasConstString) {
       return;
@@ -67,6 +73,12 @@
         operatorWithString = (rcv, arg) -> rcv.startsWith(arg) ? 1 : 0;
       } else if (invokedMethod == factory.stringMethods.endsWith) {
         operatorWithString = (rcv, arg) -> rcv.endsWith(arg) ? 1 : 0;
+      } else if (invokedMethod == factory.stringMethods.equals) {
+        operatorWithString = (rcv, arg) -> rcv.equals(arg) ? 1 : 0;
+      } else if (invokedMethod == factory.stringMethods.equalsIgnoreCase) {
+        operatorWithString = (rcv, arg) -> rcv.equalsIgnoreCase(arg) ? 1 : 0;
+      } else if (invokedMethod == factory.stringMethods.contentEqualsCharSequence) {
+        operatorWithString = (rcv, arg) -> rcv.contentEquals(arg) ? 1 : 0;
       }
       if (operatorWithNoArg == null && operatorWithString == null) {
         continue;
@@ -104,6 +116,11 @@
 
   // Find Class#get*Name() with a constant-class and replace it with a const-string if possible.
   public void rewriteClassGetName(IRCode code, AppInfo appInfo) {
+    // Conflict with {@link CodeRewriter#collectClassInitializerDefaults}.
+    if (code.method.isClassInitializer()) {
+      return;
+    }
+    boolean markUseIdentifierNameString = false;
     InstructionIterator it = code.instructionIterator();
     while (it.hasNext()) {
       Instruction instr = it.next();
@@ -147,42 +164,39 @@
         continue;
       }
 
+      String descriptor = baseType.toDescriptorString();
+      boolean assumeTopLevel = descriptor.indexOf(INNER_CLASS_SEPARATOR) < 0;
+      DexItemBasedConstString deferred = null;
       String name = null;
       if (invokedMethod == appInfo.dexItemFactory.classMethods.getName) {
         if (code.options.enableMinification) {
-          // TODO(b/118536394): Add support minification and pinning.
-          //   May need store array depth on DexItemBasedConstString.
-          //   May need enum on DexItemBasedConstString to distinguish name computation.
-          continue;
-        }
-        name = getClassNameFromDescriptor(baseType.toDescriptorString());
-        if (arrayDepth > 0) {
-          name = Strings.repeat("[", arrayDepth) + "L" + name + ";";
+          deferred = new DexItemBasedConstString(
+              invoke.outValue(), baseType, new ClassNameComputationInfo(NAME, arrayDepth));
+        } else {
+          name = computeClassName(descriptor, holder, NAME, arrayDepth);
         }
       } else if (invokedMethod == appInfo.dexItemFactory.classMethods.getTypeName) {
         // TODO(b/119426668): desugar Type#getTypeName
         continue;
-        // if (code.options.enableMinification) {
-        //   // TODO(b/118536394): Add support minification and pinning.
-        //   continue;
-        // }
-        // name = getClassNameFromDescriptor(baseType.toDescriptorString());
-        // if (arrayDepth > 0) {
-        //   name = name + Strings.repeat("[]", arrayDepth);
-        // }
       } else if (invokedMethod == appInfo.dexItemFactory.classMethods.getCanonicalName) {
         // Always returns null if the target type is local or anonymous class.
         if (holder.isLocalClass() || holder.isAnonymousClass()) {
           ConstNumber constNull = code.createConstNull();
           it.replaceCurrentInstruction(constNull);
         } else {
-          if (code.options.enableMinification) {
-            // TODO(b/118536394): Add support minification and pinning.
+          // b/119471127: If an outer class is shrunk, we may compute a wrong canonical name.
+          // Leave it as-is so that the class's canonical name is consistent across the app.
+          if (!assumeTopLevel) {
             continue;
           }
-          name = getCanonicalNameFromDescriptor(baseType.toDescriptorString());
-          if (arrayDepth > 0) {
-            name = name + Strings.repeat("[]", arrayDepth);
+          if (code.options.enableMinification) {
+            deferred =
+                new DexItemBasedConstString(
+                    invoke.outValue(),
+                    baseType,
+                    new ClassNameComputationInfo(CANONICAL_NAME, arrayDepth));
+          } else {
+            name = computeClassName(descriptor, holder, CANONICAL_NAME, arrayDepth);
           }
         }
       } else if (invokedMethod == appInfo.dexItemFactory.classMethods.getSimpleName) {
@@ -190,17 +204,16 @@
         if (holder.isAnonymousClass()) {
           name = "";
         } else {
-          if (code.options.enableMinification) {
-            // TODO(b/118536394): Add support minification and pinning.
+          // b/120130435: If an outer class is shrunk, we may compute a wrong simple name.
+          // Leave it as-is so that the class's simple name is consistent across the app.
+          if (!assumeTopLevel) {
             continue;
           }
-          if (holder.isMemberClass() || holder.isLocalClass()) {
-            name = holder.getInnerClassAttributeForThisClass().getInnerName().toString();
+          if (code.options.enableMinification) {
+            deferred = new DexItemBasedConstString(
+                invoke.outValue(), baseType, new ClassNameComputationInfo(SIMPLE_NAME, arrayDepth));
           } else {
-            name = getSimpleClassNameFromDescriptor(baseType.toDescriptorString());
-          }
-          if (arrayDepth > 0) {
-            name = name + Strings.repeat("[]", arrayDepth);
+            name = computeClassName(descriptor, holder, SIMPLE_NAME, arrayDepth);
           }
         }
       }
@@ -210,8 +223,14 @@
         ConstString constString =
             new ConstString(stringValue, appInfo.dexItemFactory.createString(name), throwingInfo);
         it.replaceCurrentInstruction(constString);
+      } else if (deferred != null) {
+        it.replaceCurrentInstruction(deferred);
+        markUseIdentifierNameString = true;
       }
     }
+    if (markUseIdentifierNameString) {
+      code.method.getMutableOptimizationInfo().markUseIdentifierNameString();
+    }
   }
 
   // String#valueOf(null) -> "null"
diff --git a/src/main/java/com/android/tools/r8/naming/IdentifierMinifier.java b/src/main/java/com/android/tools/r8/naming/IdentifierMinifier.java
index 6928d3e..61695f1 100644
--- a/src/main/java/com/android/tools/r8/naming/IdentifierMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/IdentifierMinifier.java
@@ -3,6 +3,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.naming;
 
+import static com.android.tools.r8.ir.optimize.ReflectionOptimizer.computeClassName;
 import static com.android.tools.r8.utils.DescriptorUtils.descriptorToJavaType;
 
 import com.android.tools.r8.cf.code.CfConstString;
@@ -23,7 +24,6 @@
 import com.android.tools.r8.graph.DexValue.DexValueString;
 import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
 import com.android.tools.r8.shaking.ProguardClassFilter;
-import it.unimi.dsi.fastutil.objects.Object2BooleanMap;
 import java.util.List;
 import java.util.Map;
 
@@ -36,23 +36,19 @@
   private final AppInfoWithLiveness appInfo;
   private final ProguardClassFilter adaptClassStrings;
   private final NamingLens lens;
-  private final Object2BooleanMap<DexReference> identifierNameStrings;
 
   IdentifierMinifier(
       AppInfoWithLiveness appInfo, ProguardClassFilter adaptClassStrings, NamingLens lens) {
     this.appInfo = appInfo;
     this.adaptClassStrings = adaptClassStrings;
     this.lens = lens;
-    this.identifierNameStrings = appInfo.identifierNameStrings;
   }
 
   void run() {
     if (!adaptClassStrings.isEmpty()) {
       adaptClassStrings();
     }
-    if (!identifierNameStrings.isEmpty()) {
-      replaceIdentifierNameString();
-    }
+    replaceDexItemBasedConstString();
   }
 
   private void adaptClassStrings() {
@@ -120,28 +116,35 @@
     return originalLiteral;
   }
 
-  // TODO(christofferqa): Rename to replaceDexItemBasedConstString.
-  private void replaceIdentifierNameString() {
+  private void replaceDexItemBasedConstString() {
     for (DexProgramClass clazz : appInfo.classes()) {
       // Some const strings could be moved to field's static value (from <clinit>).
       for (DexEncodedField field : clazz.staticFields()) {
-        replaceIdentifierNameStringInStaticField(field);
+        replaceDexItemBasedConstStringInStaticField(field);
       }
-      clazz.forEachMethod(this::replaceIdentifierNameStringInMethod);
+      clazz.forEachMethod(this::replaceDexItemBasedConstStringInMethod);
     }
   }
 
-  private void replaceIdentifierNameStringInStaticField(DexEncodedField encodedField) {
+  private void replaceDexItemBasedConstStringInStaticField(DexEncodedField encodedField) {
     assert encodedField.accessFlags.isStatic();
     DexValue staticValue = encodedField.getStaticValue();
     if (staticValue instanceof DexItemBasedValueString) {
-      DexReference original = ((DexItemBasedValueString) staticValue).getValue();
-      encodedField.setStaticValue(
-          new DexValueString(lens.lookupName(original, appInfo.dexItemFactory)));
+      DexItemBasedValueString dexItemBasedValueString = (DexItemBasedValueString) staticValue;
+      DexReference original = dexItemBasedValueString.getValue();
+      DexString replacement =
+          dexItemBasedValueString.getClassNameComputationInfo().needsToComputeClassName()
+              ? appInfo.dexItemFactory.createString(
+                  computeClassName(
+                      lens.lookupDescriptor(original.asDexType()),
+                      appInfo.definitionFor(original.asDexType()),
+                      dexItemBasedValueString.getClassNameComputationInfo()))
+              : lens.lookupName(original, appInfo.dexItemFactory);
+      encodedField.setStaticValue(new DexValueString(replacement));
     }
   }
 
-  private void replaceIdentifierNameStringInMethod(DexEncodedMethod encodedMethod) {
+  private void replaceDexItemBasedConstStringInMethod(DexEncodedMethod encodedMethod) {
     if (!encodedMethod.getOptimizationInfo().useIdentifierNameString()) {
       return;
     }
@@ -159,8 +162,15 @@
         Instruction instruction = instructions[i];
         if (instruction instanceof DexItemBasedConstString) {
           DexItemBasedConstString cnst = instruction.asDexItemBasedConstString();
-          instructions[i] =
-              new ConstString(cnst.AA, lens.lookupName(cnst.getItem(), appInfo.dexItemFactory));
+          DexString replacement =
+              cnst.getClassNameComputationInfo().needsToComputeClassName()
+                  ? appInfo.dexItemFactory.createString(
+                      computeClassName(
+                          lens.lookupDescriptor(cnst.getItem().asDexType()),
+                          appInfo.definitionFor(cnst.getItem().asDexType()),
+                          cnst.getClassNameComputationInfo()))
+                  : lens.lookupName(cnst.getItem(), appInfo.dexItemFactory);
+          instructions[i] = new ConstString(cnst.AA, replacement);
         }
       }
     } else {
@@ -170,8 +180,15 @@
         CfInstruction instruction = instructions.get(i);
         if (instruction.isDexItemBasedConstString()) {
           CfDexItemBasedConstString cnst = instruction.asDexItemBasedConstString();
-          instructions.set(
-              i, new CfConstString(lens.lookupName(cnst.getItem(), appInfo.dexItemFactory)));
+          DexString replacement =
+              cnst.getClassNameComputationInfo().needsToComputeClassName()
+                  ? appInfo.dexItemFactory.createString(
+                      computeClassName(
+                          lens.lookupDescriptor(cnst.getItem().asDexType()),
+                          appInfo.definitionFor(cnst.getItem().asDexType()),
+                          cnst.getClassNameComputationInfo()))
+                  : lens.lookupName(cnst.getItem(), appInfo.dexItemFactory);
+          instructions.set(i, new CfConstString(replacement));
         }
       }
     }
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 fc10fe9..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);
       }
     }
   }
@@ -1392,6 +1396,7 @@
           ConsequentRootSet consequentRootSet = ifRuleEvaluator.run(liveTypes);
           enqueueRootItems(consequentRootSet.noShrinking);
           rootSet.neverInline.addAll(consequentRootSet.neverInline);
+          rootSet.neverClassInline.addAll(consequentRootSet.neverClassInline);
           rootSet.noOptimization.addAll(consequentRootSet.noOptimization);
           rootSet.noObfuscation.addAll(consequentRootSet.noObfuscation);
           rootSet.addDependentItems(consequentRootSet.dependentNoShrinking);
diff --git a/src/main/java/com/android/tools/r8/shaking/ProguardIfRule.java b/src/main/java/com/android/tools/r8/shaking/ProguardIfRule.java
index 3011951..8d68d2e 100644
--- a/src/main/java/com/android/tools/r8/shaking/ProguardIfRule.java
+++ b/src/main/java/com/android/tools/r8/shaking/ProguardIfRule.java
@@ -5,6 +5,7 @@
 
 import com.android.tools.r8.origin.Origin;
 import com.android.tools.r8.position.Position;
+import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Iterables;
 import java.util.List;
 import java.util.stream.Collectors;
@@ -87,6 +88,24 @@
         subsequentRule.materialize());
   }
 
+  protected ClassInlineRule neverClassInlineRuleForCondition() {
+    return new ClassInlineRule(
+        Origin.unknown(),
+        Position.UNKNOWN,
+        null,
+        getClassAnnotation() == null ? null : getClassAnnotation().materialize(),
+        getClassAccessFlags(),
+        getNegatedClassAccessFlags(),
+        getClassTypeNegated(),
+        getClassType(),
+        getClassNames().materialize(),
+        getInheritanceAnnotation() == null ? null : getInheritanceAnnotation().materialize(),
+        getInheritanceClassName() == null ? null : getInheritanceClassName().materialize(),
+        getInheritanceIsExtends(),
+        ImmutableList.of(),
+        ClassInlineRule.Type.NEVER);
+  }
+
   /**
    * Consider the following rule, which requests that class Y should be kept if the method X.m() is
    * in the final output.
diff --git a/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java b/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java
index c59081e..de0537f 100644
--- a/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java
+++ b/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java
@@ -327,7 +327,12 @@
         application.timing.end();
       }
       return new ConsequentRootSet(
-          neverInline, noShrinking, noOptimization, noObfuscation, dependentNoShrinking);
+          neverInline,
+          neverClassInline,
+          noShrinking,
+          noOptimization,
+          noObfuscation,
+          dependentNoShrinking);
     }
 
     /**
@@ -413,6 +418,14 @@
     private void materializeIfRule(ProguardIfRule rule) {
       ProguardIfRule materializedRule = rule.materialize();
 
+      // We need to abort class inlining of classes that could be matched by the condition of this
+      // -if rule.
+      ClassInlineRule neverClassInlineRuleForCondition =
+          materializedRule.neverClassInlineRuleForCondition();
+      if (neverClassInlineRuleForCondition != null) {
+        runPerRule(executorService, futures, neverClassInlineRuleForCondition, materializedRule);
+      }
+
       // If the condition of the -if rule has any members, then we need to keep these members to
       // ensure that the subsequent rule will be applied again in the second round of tree
       // shaking.
@@ -957,7 +970,7 @@
       this.alwaysInline = Collections.unmodifiableSet(alwaysInline);
       this.forceInline = Collections.unmodifiableSet(forceInline);
       this.neverInline = neverInline;
-      this.neverClassInline = Collections.unmodifiableSet(neverClassInline);
+      this.neverClassInline = neverClassInline;
       this.neverMerge = Collections.unmodifiableSet(neverMerge);
       this.noSideEffects = Collections.unmodifiableMap(noSideEffects);
       this.assumedValues = Collections.unmodifiableMap(assumedValues);
@@ -1010,6 +1023,7 @@
   // A partial RootSet that becomes live due to the enabled -if rule.
   static class ConsequentRootSet {
     final Set<DexMethod> neverInline;
+    final Set<DexType> neverClassInline;
     final Map<DexDefinition, ProguardKeepRule> noShrinking;
     final Set<DexDefinition> noOptimization;
     final Set<DexDefinition> noObfuscation;
@@ -1017,11 +1031,13 @@
 
     private ConsequentRootSet(
         Set<DexMethod> neverInline,
+        Set<DexType> neverClassInline,
         Map<DexDefinition, ProguardKeepRule> noShrinking,
         Set<DexDefinition> noOptimization,
         Set<DexDefinition> noObfuscation,
         Map<DexDefinition, Map<DexDefinition, ProguardKeepRule>> dependentNoShrinking) {
       this.neverInline = Collections.unmodifiableSet(neverInline);
+      this.neverClassInline = Collections.unmodifiableSet(neverClassInline);
       this.noShrinking = Collections.unmodifiableMap(noShrinking);
       this.noOptimization = Collections.unmodifiableSet(noOptimization);
       this.noObfuscation = Collections.unmodifiableSet(noObfuscation);
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/ExceptionUtils.java b/src/main/java/com/android/tools/r8/utils/ExceptionUtils.java
index 8fa85bf..ee11bcf 100644
--- a/src/main/java/com/android/tools/r8/utils/ExceptionUtils.java
+++ b/src/main/java/com/android/tools/r8/utils/ExceptionUtils.java
@@ -11,6 +11,8 @@
 import com.android.tools.r8.origin.Origin;
 import com.android.tools.r8.origin.PathOrigin;
 import java.io.IOException;
+import java.io.PrintWriter;
+import java.io.StringWriter;
 import java.nio.file.FileSystemException;
 import java.nio.file.Paths;
 import java.util.function.Consumer;
@@ -65,6 +67,13 @@
       } catch (ResourceException e) {
         throw reporter.fatalError(new ExceptionDiagnostic(e, e.getOrigin()));
       } catch (AssertionError e) {
+        // Most of our assertions don't have a message, create a wrapper that has the stack as the
+        // message.
+        if (e.getMessage() == null) {
+          StringWriter stack = new StringWriter();
+          e.printStackTrace(new PrintWriter(stack));
+          e = new AssertionError(stack.toString(), e);
+        }
         throw reporter.fatalError(new ExceptionDiagnostic(e, Origin.unknown()), e);
       }
       reporter.failIfPendingErrors();
diff --git a/src/main/java/com/android/tools/r8/utils/InternalOptions.java b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
index 7c27264..d8f4dba 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -109,6 +109,8 @@
       !Version.isDev() || System.getProperty("com.android.tools.r8.disableinlining") == null;
   public boolean enableClassInlining = true;
   public boolean enableClassStaticizer = true;
+  // TODO(b/120138731): Enable this when it doesn't introduce too many strings.
+  public boolean enableNameReflectionOptimization = false;
   public int classInliningInstructionLimit = 50;
   // This defines the limit of instructions in the inlinee
   public int inliningInstructionLimit = 3;
diff --git a/src/test/java/com/android/tools/r8/DXTestBuilder.java b/src/test/java/com/android/tools/r8/DXTestBuilder.java
index 8312729..190db23 100644
--- a/src/test/java/com/android/tools/r8/DXTestBuilder.java
+++ b/src/test/java/com/android/tools/r8/DXTestBuilder.java
@@ -67,6 +67,11 @@
   }
 
   @Override
+  public DXTestBuilder addProgramClassFileData(Collection<byte[]> classes) {
+    throw new Unimplemented("No support for adding classfile data directly");
+  }
+
+  @Override
   public DXTestBuilder addProgramFiles(Collection<Path> files) {
     injars.addAll(files);
     return self();
diff --git a/src/test/java/com/android/tools/r8/Dex2OatTestRunResult.java b/src/test/java/com/android/tools/r8/Dex2OatTestRunResult.java
new file mode 100644
index 0000000..c4425b1
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/Dex2OatTestRunResult.java
@@ -0,0 +1,20 @@
+// 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;
+
+import com.android.tools.r8.ToolHelper.ProcessResult;
+import com.android.tools.r8.utils.AndroidApp;
+
+public class Dex2OatTestRunResult extends TestRunResult<Dex2OatTestRunResult> {
+
+  public Dex2OatTestRunResult(AndroidApp app, ProcessResult result) {
+    super(app, result);
+  }
+
+  @Override
+  protected Dex2OatTestRunResult self() {
+    return this;
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/JctfTestSpecifications.java b/src/test/java/com/android/tools/r8/JctfTestSpecifications.java
index 2c2c5a6..cebfc53 100644
--- a/src/test/java/com/android/tools/r8/JctfTestSpecifications.java
+++ b/src/test/java/com/android/tools/r8/JctfTestSpecifications.java
@@ -40,7 +40,9 @@
           .put("math.BigInteger.ConstructorLjava_lang_String.BigInteger_Constructor_A02", any())
           .put(
               "lang.StringBuffer.insertILjava_lang_Object.StringBuffer_insert_A01",
-              match(runtimes(Runtime.ART_DEFAULT, Runtime.ART_V8_1_0, Runtime.JAVA)))
+              match(
+                  runtimes(
+                      Runtime.ART_DEFAULT, Runtime.ART_V9_0_0, Runtime.ART_V8_1_0, Runtime.JAVA)))
           .put("lang.StringBuffer.serialization.StringBuffer_serialization_A01", anyDexVm())
           .put(
               "lang.CloneNotSupportedException.serialization.CloneNotSupportedException_serialization_A01",
@@ -52,12 +54,20 @@
               "lang.StrictMath.roundF.StrictMath_round_A01",
               match(
                   runtimes(
-                      Runtime.ART_DEFAULT, Runtime.ART_V8_1_0, Runtime.ART_V7_0_0, Runtime.JAVA)))
+                      Runtime.ART_DEFAULT,
+                      Runtime.ART_V9_0_0,
+                      Runtime.ART_V8_1_0,
+                      Runtime.ART_V7_0_0,
+                      Runtime.JAVA)))
           .put(
               "lang.StrictMath.roundD.StrictMath_round_A01",
               match(
                   runtimes(
-                      Runtime.ART_DEFAULT, Runtime.ART_V8_1_0, Runtime.ART_V7_0_0, Runtime.JAVA)))
+                      Runtime.ART_DEFAULT,
+                      Runtime.ART_V9_0_0,
+                      Runtime.ART_V8_1_0,
+                      Runtime.ART_V7_0_0,
+                      Runtime.JAVA)))
           .put("lang.StrictMath.atan2DD.StrictMath_atan2_A01", any())
           .put("lang.Thread.stop.Thread_stop_A05", any())
           .put("lang.Thread.resume.Thread_resume_A02", anyDexVm())
@@ -70,6 +80,7 @@
               match(
                   runtimes(
                       Runtime.ART_DEFAULT,
+                      Runtime.ART_V9_0_0,
                       Runtime.ART_V8_1_0,
                       Runtime.ART_V7_0_0,
                       Runtime.ART_V6_0_1)))
@@ -199,7 +210,12 @@
               anyDexVm())
           .put(
               "lang.ClassLoader.defineClassLjava_lang_StringLjava_nio_ByteBufferLjava_security_ProtectionDomain.ClassLoader_defineClass_A07",
-              match(runtimes(Runtime.ART_DEFAULT, Runtime.ART_V8_1_0, Runtime.ART_V7_0_0)))
+              match(
+                  runtimes(
+                      Runtime.ART_DEFAULT,
+                      Runtime.ART_V9_0_0,
+                      Runtime.ART_V8_1_0,
+                      Runtime.ART_V7_0_0)))
           .put(
               "lang.ClassLoader.defineClassLjava_lang_StringLjava_nio_ByteBufferLjava_security_ProtectionDomain.ClassLoader_defineClass_A04",
               anyDexVm())
@@ -421,6 +437,7 @@
               match(
                   runtimes(
                       Runtime.ART_DEFAULT,
+                      Runtime.ART_V9_0_0,
                       Runtime.ART_V8_1_0,
                       Runtime.ART_V7_0_0,
                       Runtime.ART_V6_0_1,
@@ -431,6 +448,7 @@
               match(
                   runtimes(
                       Runtime.ART_DEFAULT,
+                      Runtime.ART_V9_0_0,
                       Runtime.ART_V8_1_0,
                       Runtime.ART_V7_0_0,
                       Runtime.ART_V6_0_1,
@@ -441,6 +459,7 @@
               match(
                   runtimes(
                       Runtime.ART_DEFAULT,
+                      Runtime.ART_V9_0_0,
                       Runtime.ART_V8_1_0,
                       Runtime.ART_V7_0_0,
                       Runtime.ART_V6_0_1,
@@ -451,6 +470,7 @@
               match(
                   runtimes(
                       Runtime.ART_DEFAULT,
+                      Runtime.ART_V9_0_0,
                       Runtime.ART_V8_1_0,
                       Runtime.ART_V7_0_0,
                       Runtime.ART_V6_0_1,
@@ -465,6 +485,7 @@
               match(
                   runtimes(
                       Runtime.ART_DEFAULT,
+                      Runtime.ART_V9_0_0,
                       Runtime.ART_V8_1_0,
                       Runtime.ART_V7_0_0,
                       Runtime.ART_V6_0_1,
@@ -475,6 +496,7 @@
               match(
                   runtimes(
                       Runtime.ART_DEFAULT,
+                      Runtime.ART_V9_0_0,
                       Runtime.ART_V8_1_0,
                       Runtime.ART_V7_0_0,
                       Runtime.ART_V6_0_1,
@@ -509,6 +531,7 @@
               match(
                   runtimes(
                       Runtime.ART_DEFAULT,
+                      Runtime.ART_V9_0_0,
                       Runtime.ART_V8_1_0,
                       Runtime.ART_V7_0_0,
                       Runtime.ART_V6_0_1,
@@ -520,6 +543,7 @@
               match(
                   runtimes(
                       Runtime.ART_DEFAULT,
+                      Runtime.ART_V9_0_0,
                       Runtime.ART_V8_1_0,
                       Runtime.ART_V7_0_0,
                       Runtime.ART_V6_0_1,
@@ -530,6 +554,7 @@
               match(
                   runtimes(
                       Runtime.ART_DEFAULT,
+                      Runtime.ART_V9_0_0,
                       Runtime.ART_V8_1_0,
                       Runtime.ART_V7_0_0,
                       Runtime.ART_V6_0_1,
@@ -540,6 +565,7 @@
               match(
                   runtimes(
                       Runtime.ART_DEFAULT,
+                      Runtime.ART_V9_0_0,
                       Runtime.ART_V8_1_0,
                       Runtime.ART_V7_0_0,
                       Runtime.ART_V6_0_1,
@@ -550,6 +576,7 @@
               match(
                   runtimes(
                       Runtime.ART_DEFAULT,
+                      Runtime.ART_V9_0_0,
                       Runtime.ART_V8_1_0,
                       Runtime.ART_V7_0_0,
                       Runtime.ART_V6_0_1,
@@ -560,6 +587,7 @@
               match(
                   runtimes(
                       Runtime.ART_DEFAULT,
+                      Runtime.ART_V9_0_0,
                       Runtime.ART_V8_1_0,
                       Runtime.ART_V7_0_0,
                       Runtime.ART_V6_0_1,
@@ -570,6 +598,7 @@
               match(
                   runtimes(
                       Runtime.ART_DEFAULT,
+                      Runtime.ART_V9_0_0,
                       Runtime.ART_V8_1_0,
                       Runtime.ART_V7_0_0,
                       Runtime.ART_V6_0_1,
@@ -580,6 +609,7 @@
               match(
                   runtimes(
                       Runtime.ART_DEFAULT,
+                      Runtime.ART_V9_0_0,
                       Runtime.ART_V8_1_0,
                       Runtime.ART_V7_0_0,
                       Runtime.ART_V6_0_1,
@@ -590,6 +620,7 @@
               match(
                   runtimes(
                       Runtime.ART_DEFAULT,
+                      Runtime.ART_V9_0_0,
                       Runtime.ART_V8_1_0,
                       Runtime.ART_V7_0_0,
                       Runtime.ART_V6_0_1,
@@ -619,6 +650,7 @@
               match(
                   runtimes(
                       Runtime.ART_DEFAULT,
+                      Runtime.ART_V9_0_0,
                       Runtime.ART_V8_1_0,
                       Runtime.ART_V7_0_0,
                       Runtime.ART_V6_0_1,
@@ -630,7 +662,7 @@
           .put("lang.ref.WeakReference.get.WeakReference_get_A01", any())
           .put(
               "lang.StackTraceElement.toString.StackTraceElement_toString_A01",
-              match(runtimes(Runtime.ART_DEFAULT, Runtime.ART_V8_1_0)))
+              match(runtimes(Runtime.ART_DEFAULT, Runtime.ART_V9_0_0, Runtime.ART_V8_1_0)))
           .put(
               "lang.NullPointerException.serialization.NullPointerException_serialization_A01",
               anyDexVm())
@@ -686,7 +718,9 @@
               match(artRuntimesFromAndJava(Runtime.ART_V5_1_1)))
           .put(
               "lang.annotation.IncompleteAnnotationException.ConstructorLjava_lang_ClassLjava_lang_String.IncompleteAnnotationException_Constructor_A01",
-              match(runtimes(Runtime.ART_DEFAULT, Runtime.ART_V8_1_0, Runtime.JAVA)))
+              match(
+                  runtimes(
+                      Runtime.ART_DEFAULT, Runtime.ART_V9_0_0, Runtime.ART_V8_1_0, Runtime.JAVA)))
           .put(
               "lang.InterruptedException.serialization.InterruptedException_serialization_A01",
               anyDexVm())
@@ -774,6 +808,7 @@
               match(
                   runtimes(
                       Runtime.ART_DEFAULT,
+                      Runtime.ART_V9_0_0,
                       Runtime.ART_V8_1_0,
                       Runtime.ART_V7_0_0,
                       Runtime.ART_V4_4_4,
@@ -814,6 +849,7 @@
               match(
                   runtimes(
                       Runtime.ART_DEFAULT,
+                      Runtime.ART_V9_0_0,
                       Runtime.ART_V8_1_0,
                       Runtime.ART_V7_0_0,
                       Runtime.ART_V4_4_4,
@@ -1167,7 +1203,9 @@
               anyDexVm())
           .put(
               "lang.reflect.Proxy.h.Proxy_h_A01",
-              match(runtimes(Runtime.ART_DEFAULT, Runtime.ART_V8_1_0, Runtime.JAVA)))
+              match(
+                  runtimes(
+                      Runtime.ART_DEFAULT, Runtime.ART_V9_0_0, Runtime.ART_V8_1_0, Runtime.JAVA)))
           .put("lang.reflect.Proxy.serialization.Proxy_serialization_A02", any())
           .put(
               "lang.reflect.GenericSignatureFormatError.serialization.GenericSignatureFormatError_serialization_A01",
@@ -1177,7 +1215,9 @@
               anyDexVm())
           .put(
               "lang.reflect.Proxy.ConstructorLjava_lang_reflect_InvocationHandler.Proxy_Constructor_A01",
-              match(runtimes(Runtime.ART_DEFAULT, Runtime.ART_V8_1_0, Runtime.JAVA)))
+              match(
+                  runtimes(
+                      Runtime.ART_DEFAULT, Runtime.ART_V9_0_0, Runtime.ART_V8_1_0, Runtime.JAVA)))
           .put(
               "lang.reflect.Proxy.newProxyInstanceLjava_lang_ClassLoader_Ljava_lang_ClassLjava_lang_reflect_InvocationHandler.Proxy_newProxyInstance_A01",
               anyDexVm())
@@ -1694,14 +1734,20 @@
               match(artRuntimesUpTo(Runtime.ART_V4_4_4)))
           .put(
               "lang.ref.PhantomReference.isEnqueued.PhantomReference_isEnqueued_A01",
-              match(and(runtimes(Runtime.ART_V8_1_0), artRuntimesUpTo(Runtime.ART_V4_4_4))))
+              match(
+                  and(
+                      runtimes(Runtime.ART_V9_0_0, Runtime.ART_V8_1_0),
+                      artRuntimesUpTo(Runtime.ART_V4_4_4))))
           .put("lang.ref.WeakReference.isEnqueued.WeakReference_isEnqueued_A01", anyDexVm())
           .put(
               "lang.ref.WeakReference.enqueue.WeakReference_enqueue_A01",
               match(artRuntimesUpTo(Runtime.ART_V4_4_4)))
           .put(
               "lang.ref.SoftReference.isEnqueued.SoftReference_isEnqueued_A01",
-              match(and(runtimes(Runtime.ART_V8_1_0), artRuntimesUpTo(Runtime.ART_V4_4_4))))
+              match(
+                  and(
+                      runtimes(Runtime.ART_V9_0_0, Runtime.ART_V8_1_0),
+                      artRuntimesUpTo(Runtime.ART_V4_4_4))))
           .put(
               "lang.ref.SoftReference.enqueue.SoftReference_enqueue_A01",
               match(artRuntimesUpTo(Runtime.ART_V4_4_4)))
@@ -1712,7 +1758,6 @@
           .put(
               "util.concurrent.AbstractExecutorService.invokeAllLjava_util_CollectionJLjava_util_concurrent_TimeUnit.AbstractExecutorService_invokeAll_A06",
               match(runtimes(Runtime.ART_V4_0_4)))
-
           .build(); // end of flakyWhenRun
 
   public static final Multimap<String, TestCondition> timeoutsWhenRun =
diff --git a/src/test/java/com/android/tools/r8/JvmTestBuilder.java b/src/test/java/com/android/tools/r8/JvmTestBuilder.java
index 44a3bed..f95e666 100644
--- a/src/test/java/com/android/tools/r8/JvmTestBuilder.java
+++ b/src/test/java/com/android/tools/r8/JvmTestBuilder.java
@@ -147,6 +147,12 @@
         "No support for adding paths directly (we need to compute the descriptor)");
   }
 
+  @Override
+  public JvmTestBuilder addProgramClassFileData(Collection<byte[]> files) {
+    throw new Unimplemented(
+        "No support for adding classfile data directly (we need to compute the descriptor)");
+  }
+
   public JvmTestBuilder addClasspath(Path... paths) {
     return addClasspath(Arrays.asList(paths));
   }
diff --git a/src/test/java/com/android/tools/r8/ProguardTestBuilder.java b/src/test/java/com/android/tools/r8/ProguardTestBuilder.java
index 28ce1e6..fa4c41c 100644
--- a/src/test/java/com/android/tools/r8/ProguardTestBuilder.java
+++ b/src/test/java/com/android/tools/r8/ProguardTestBuilder.java
@@ -184,6 +184,12 @@
   }
 
   @Override
+  public ProguardTestBuilder addProgramClassFileData(Collection<byte[]> classes) {
+    throw new Unimplemented(
+        "No support for adding classfile data directly (we need to compute the descriptor)");
+  }
+
+  @Override
   public ProguardTestBuilder addKeepRules(Collection<String> rules) {
     config.addAll(rules);
     return self();
diff --git a/src/test/java/com/android/tools/r8/R8RunArtTestsTest.java b/src/test/java/com/android/tools/r8/R8RunArtTestsTest.java
index 5123c51..2a4977d 100644
--- a/src/test/java/com/android/tools/r8/R8RunArtTestsTest.java
+++ b/src/test/java/com/android/tools/r8/R8RunArtTestsTest.java
@@ -97,7 +97,8 @@
       DexVm.Version.V5_1_1,
       DexVm.Version.V6_0_1,
       DexVm.Version.V7_0_0,
-      DexVm.Version.V8_1_0);
+      DexVm.Version.V8_1_0,
+      DexVm.Version.V9_0_0);
 
   // Input jar for jctf tests.
   private static final String JCTF_COMMON_JAR = "build/libs/jctfCommon.jar";
@@ -463,6 +464,16 @@
   static {
     ImmutableMap.Builder<DexVm.Version, List<String>> builder = ImmutableMap.builder();
     builder
+        .put(DexVm.Version.V9_0_0, ImmutableList.of(
+            // TODO(120400625): Triage.
+            "454-get-vreg",
+            // TODO(120402198): Triage.
+            "457-regs",
+            // TODO(120401674): Triage.
+            "543-env-long-ref",
+            // TODO(120261858) Triage.
+            "518-null-array-get"
+        ))
         .put(DexVm.Version.V8_1_0, ImmutableList.of(
             // TODO(119938529): Triage.
             "709-checker-varhandles",
diff --git a/src/test/java/com/android/tools/r8/R8RunExamplesAndroidOTest.java b/src/test/java/com/android/tools/r8/R8RunExamplesAndroidOTest.java
index 101fbb8..1c949a4 100644
--- a/src/test/java/com/android/tools/r8/R8RunExamplesAndroidOTest.java
+++ b/src/test/java/com/android/tools/r8/R8RunExamplesAndroidOTest.java
@@ -69,6 +69,10 @@
           .put(
               Version.V7_0_0,
               ImmutableList.of("invokecustom-with-shrinking", "invokecustom2-with-shrinking"))
+          .put(
+              Version.V9_0_0,
+              // TODO(120402963) Triage.
+              ImmutableList.of("invokecustom-with-shrinking", "invokecustom2-with-shrinking"))
           .put(Version.DEFAULT, ImmutableList.of())
           .build();
 
diff --git a/src/test/java/com/android/tools/r8/R8RunExamplesTest.java b/src/test/java/com/android/tools/r8/R8RunExamplesTest.java
index 221d427..793df27 100644
--- a/src/test/java/com/android/tools/r8/R8RunExamplesTest.java
+++ b/src/test/java/com/android/tools/r8/R8RunExamplesTest.java
@@ -208,6 +208,9 @@
         // Early art versions incorrectly print doubles.
         .put("regress_72361252.Test",
             TestCondition.match(TestCondition.runtimesUpTo(Version.V6_0_1)))
+        // TODO(120402200): Triage.
+        .put("regress_62300145.Regress",
+            TestCondition.match(TestCondition.runtimesUpTo(Version.V9_0_0)))
         .build();
   }
 
diff --git a/src/test/java/com/android/tools/r8/RunExamplesAndroidOTest.java b/src/test/java/com/android/tools/r8/RunExamplesAndroidOTest.java
index 68aec3f..a7b7230 100644
--- a/src/test/java/com/android/tools/r8/RunExamplesAndroidOTest.java
+++ b/src/test/java/com/android/tools/r8/RunExamplesAndroidOTest.java
@@ -269,6 +269,12 @@
                 "testMissingSuperDesugaredAndroidO"
             ))
         .put(
+            DexVm.Version.V9_0_0, ImmutableList.of(
+                // TODO(120402963): Triage.
+                "invokecustom",
+                "invokecustom2"
+            ))
+        .put(
             DexVm.Version.DEFAULT, ImmutableList.of()
         );
     failsOn = builder.build();
@@ -577,9 +583,6 @@
       String qualifiedMainClass, Path[] jars, Path[] dexes, List<String> args) throws IOException {
 
     boolean expectedToFail = expectedToFail(testName);
-    if (expectedToFail && !ToolHelper.compareAgaintsGoldenFiles()) {
-      thrown.expect(Throwable.class);
-    }
     String output = ToolHelper.runArtNoVerificationErrors(
         Arrays.stream(dexes).map(path -> path.toString()).collect(Collectors.toList()),
         qualifiedMainClass,
@@ -588,18 +591,22 @@
             builder.appendProgramArgument(arg);
           }
         });
-    if (!expectedToFail && !skipRunningOnJvm(testName) && !ToolHelper.compareAgaintsGoldenFiles()) {
-      ArrayList<String> javaArgs = Lists.newArrayList(args);
-      javaArgs.add(0, qualifiedMainClass);
-      ToolHelper.ProcessResult javaResult =
-          ToolHelper.runJava(ImmutableList.copyOf(jars), javaArgs.toArray(new String[0]));
-      assertEquals("JVM run failed", javaResult.exitCode, 0);
-      assertTrue(
-          "JVM output does not match art output.\n\tjvm: "
-              + javaResult.stdout
-              + "\n\tart: "
-              + output,
-          output.replace("\r", "").equals(javaResult.stdout.replace("\r", "")));
+    try {
+      if (!skipRunningOnJvm(testName) && !ToolHelper.compareAgaintsGoldenFiles()) {
+        ArrayList<String> javaArgs = Lists.newArrayList(args);
+        javaArgs.add(0, qualifiedMainClass);
+        ToolHelper.ProcessResult javaResult =
+            ToolHelper.runJava(ImmutableList.copyOf(jars), javaArgs.toArray(new String[0]));
+        assertEquals("JVM run failed", javaResult.exitCode, 0);
+        assertTrue(
+            "JVM output does not match art output.\n\tjvm: "
+                + javaResult.stdout
+                + "\n\tart: "
+                + output,
+            output.replace("\r", "").equals(javaResult.stdout.replace("\r", "")));
+      }
+    } catch (Throwable t) {
+      assert expectedToFail;
     }
   }
 
diff --git a/src/test/java/com/android/tools/r8/RunExamplesAndroidPTest.java b/src/test/java/com/android/tools/r8/RunExamplesAndroidPTest.java
index e0981c4..2ab5e3e 100644
--- a/src/test/java/com/android/tools/r8/RunExamplesAndroidPTest.java
+++ b/src/test/java/com/android/tools/r8/RunExamplesAndroidPTest.java
@@ -186,7 +186,9 @@
           .put(DexVm.Version.V6_0_1, ImmutableList.of("invokecustom"))
           // Dex version not supported
           .put(DexVm.Version.V7_0_0, ImmutableList.of("invokecustom"))
+          // Dex version not supported
           .put(DexVm.Version.V8_1_0, ImmutableList.of("invokecustom"))
+          // Dex version not supported
           .put(DexVm.Version.DEFAULT, ImmutableList.of())
           .build();
 
diff --git a/src/test/java/com/android/tools/r8/RunExamplesJava9Test.java b/src/test/java/com/android/tools/r8/RunExamplesJava9Test.java
index 8a284ac..9c91282 100644
--- a/src/test/java/com/android/tools/r8/RunExamplesJava9Test.java
+++ b/src/test/java/com/android/tools/r8/RunExamplesJava9Test.java
@@ -231,7 +231,9 @@
               + "1: d>i>s>i>a\n"
               + "2: l>i>s>i>a\n"
               + "3: x>s\n"
-              + "4: c>d>i>s>i>a\n"
+              + "4: c>d>i>s>i>a\n",
+          "varhandle",
+          "true\nfalse\n"
       );
 
   @Rule
diff --git a/src/test/java/com/android/tools/r8/TestBuilder.java b/src/test/java/com/android/tools/r8/TestBuilder.java
index 0675118..61bf1b3 100644
--- a/src/test/java/com/android/tools/r8/TestBuilder.java
+++ b/src/test/java/com/android/tools/r8/TestBuilder.java
@@ -39,6 +39,12 @@
 
   public abstract T addProgramFiles(Collection<Path> files);
 
+  public abstract T addProgramClassFileData(Collection<byte[]> classes);
+
+  public T addProgramClassFileData(byte[]... classes) {
+    return addProgramClassFileData(Arrays.asList(classes));
+  }
+
   public T addProgramClasses(Class<?>... classes) {
     return addProgramClasses(Arrays.asList(classes));
   }
diff --git a/src/test/java/com/android/tools/r8/TestCompileResult.java b/src/test/java/com/android/tools/r8/TestCompileResult.java
index 12d1990..61f9def 100644
--- a/src/test/java/com/android/tools/r8/TestCompileResult.java
+++ b/src/test/java/com/android/tools/r8/TestCompileResult.java
@@ -6,6 +6,7 @@
 import static com.android.tools.r8.TestBase.Backend.DEX;
 
 import com.android.tools.r8.TestBase.Backend;
+import com.android.tools.r8.ToolHelper.DexVm;
 import com.android.tools.r8.ToolHelper.ProcessResult;
 import com.android.tools.r8.debug.CfDebugTestConfig;
 import com.android.tools.r8.debug.DebugTestConfig;
@@ -98,4 +99,17 @@
     ProcessResult result = ToolHelper.runArtRaw(out.toString(), mainClass);
     return createRunResult(app, result);
   }
+
+  public Dex2OatTestRunResult runDex2Oat() throws IOException {
+    return runDex2Oat(ToolHelper.getDexVm());
+  }
+
+  public Dex2OatTestRunResult runDex2Oat(DexVm vm) throws IOException {
+    assert getBackend() == DEX;
+    Path tmp = state.getNewTempFolder();
+    Path jarFile = tmp.resolve("out.jar");
+    Path oatFile = tmp.resolve("out.oat");
+    app.writeToZip(jarFile, OutputMode.DexIndexed);
+    return new Dex2OatTestRunResult(app, ToolHelper.runDex2OatRaw(jarFile, oatFile, vm));
+  }
 }
diff --git a/src/test/java/com/android/tools/r8/TestCompilerBuilder.java b/src/test/java/com/android/tools/r8/TestCompilerBuilder.java
index f60db7f..9425df9 100644
--- a/src/test/java/com/android/tools/r8/TestCompilerBuilder.java
+++ b/src/test/java/com/android/tools/r8/TestCompilerBuilder.java
@@ -5,6 +5,7 @@
 
 import com.android.tools.r8.TestBase.Backend;
 import com.android.tools.r8.debug.DebugTestConfig;
+import com.android.tools.r8.origin.Origin;
 import com.android.tools.r8.utils.AndroidApiLevel;
 import com.android.tools.r8.utils.AndroidApp;
 import com.android.tools.r8.utils.AndroidAppConsumers;
@@ -36,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;
 
@@ -61,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);
     }
@@ -112,6 +115,25 @@
     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) {
+      builder.addClassProgramData(clazz, Origin.unknown());
+    }
+    return self();
+  }
+
   @Override
   public T addProgramFiles(Collection<Path> files) {
     builder.addProgramFiles(files);
@@ -124,4 +146,9 @@
     builder.addLibraryFiles(files);
     return self();
   }
+
+  public T noDesugaring() {
+    builder.setDisableDesugaring(true);
+    return self();
+  }
 }
diff --git a/src/test/java/com/android/tools/r8/TestCondition.java b/src/test/java/com/android/tools/r8/TestCondition.java
index 439b9e9..52d7f93 100644
--- a/src/test/java/com/android/tools/r8/TestCondition.java
+++ b/src/test/java/com/android/tools/r8/TestCondition.java
@@ -23,6 +23,7 @@
     ART_V6_0_1,
     ART_V7_0_0,
     ART_V8_1_0,
+    ART_V9_0_0,
     ART_DEFAULT,
     JAVA;
 
@@ -43,6 +44,8 @@
           return ART_V7_0_0;
         case V8_1_0:
           return ART_V8_1_0;
+        case V9_0_0:
+          return ART_V9_0_0;
         case DEFAULT:
           return ART_DEFAULT;
         default:
diff --git a/src/test/java/com/android/tools/r8/TestRunResult.java b/src/test/java/com/android/tools/r8/TestRunResult.java
index f3ec339..a193bdb 100644
--- a/src/test/java/com/android/tools/r8/TestRunResult.java
+++ b/src/test/java/com/android/tools/r8/TestRunResult.java
@@ -88,6 +88,13 @@
     return self();
   }
 
+  @Override
+  public String toString() {
+    StringBuilder builder = new StringBuilder();
+    appendInfo(builder);
+    return builder.toString();
+  }
+
   private String errorMessage(String message) {
     return errorMessage(message, null);
   }
diff --git a/src/test/java/com/android/tools/r8/ToolHelper.java b/src/test/java/com/android/tools/r8/ToolHelper.java
index d4639a1..f73f198 100644
--- a/src/test/java/com/android/tools/r8/ToolHelper.java
+++ b/src/test/java/com/android/tools/r8/ToolHelper.java
@@ -126,6 +126,8 @@
     ART_7_0_0_HOST(Version.V7_0_0, Kind.HOST),
     ART_8_1_0_TARGET(Version.V8_1_0, Kind.TARGET),
     ART_8_1_0_HOST(Version.V8_1_0, Kind.HOST),
+    ART_9_0_0_TARGET(Version.V9_0_0, Kind.TARGET),
+    ART_9_0_0_HOST(Version.V9_0_0, Kind.HOST),
     ART_DEFAULT(Version.DEFAULT, Kind.HOST);
 
     private static final ImmutableMap<String, DexVm> SHORT_NAME_MAP =
@@ -140,6 +142,7 @@
       V6_0_1("6.0.1"),
       V7_0_0("7.0.0"),
       V8_1_0("8.1.0"),
+      V9_0_0("9.0.0"),
       DEFAULT("default");
 
       Version(String shortName) {
@@ -416,6 +419,7 @@
   private static final Map<DexVm, String> ART_DIRS =
       ImmutableMap.<DexVm, String>builder()
           .put(DexVm.ART_DEFAULT, "art")
+          .put(DexVm.ART_9_0_0_HOST, "art-9.0.0")
           .put(DexVm.ART_8_1_0_HOST, "art-8.1.0")
           .put(DexVm.ART_7_0_0_HOST, "art-7.0.0")
           .put(DexVm.ART_6_0_1_HOST, "art-6.0.1")
@@ -425,6 +429,7 @@
   private static final Map<DexVm, String> ART_BINARY_VERSIONS =
       ImmutableMap.<DexVm, String>builder()
           .put(DexVm.ART_DEFAULT, "bin/art")
+          .put(DexVm.ART_9_0_0_HOST, "bin/art")
           .put(DexVm.ART_8_1_0_HOST, "bin/art")
           .put(DexVm.ART_7_0_0_HOST, "bin/art")
           .put(DexVm.ART_6_0_1_HOST, "bin/art")
@@ -435,6 +440,7 @@
   private static final Map<DexVm, String> ART_BINARY_VERSIONS_X64 =
       ImmutableMap.of(
           DexVm.ART_DEFAULT, "bin/art",
+          DexVm.ART_9_0_0_HOST, "bin/art",
           DexVm.ART_8_1_0_HOST, "bin/art",
           DexVm.ART_7_0_0_HOST, "bin/art",
           DexVm.ART_6_0_1_HOST, "bin/art");
@@ -457,6 +463,7 @@
     ImmutableMap.Builder<DexVm, List<String>> builder = ImmutableMap.builder();
     builder
         .put(DexVm.ART_DEFAULT, ART_BOOT_LIBS)
+        .put(DexVm.ART_9_0_0_HOST, ART_BOOT_LIBS)
         .put(DexVm.ART_8_1_0_HOST, ART_BOOT_LIBS)
         .put(DexVm.ART_7_0_0_HOST, ART_BOOT_LIBS)
         .put(DexVm.ART_6_0_1_HOST, ART_BOOT_LIBS)
@@ -472,10 +479,11 @@
     ImmutableMap.Builder<DexVm, String> builder = ImmutableMap.builder();
     builder
         .put(DexVm.ART_DEFAULT, "angler")
+        .put(DexVm.ART_9_0_0_HOST, "marlin")
         .put(DexVm.ART_8_1_0_HOST, "marlin")
         .put(DexVm.ART_7_0_0_HOST, "angler")
         .put(DexVm.ART_6_0_1_HOST, "angler")
-        .put(DexVm.ART_5_1_1_HOST, "<missing>")
+        .put(DexVm.ART_5_1_1_HOST, "mako")
         .put(DexVm.ART_4_4_4_HOST, "<missing>")
         .put(DexVm.ART_4_0_4_HOST, "<missing>");
     PRODUCT = builder.build();
@@ -504,6 +512,10 @@
     return getDexVmPath(vm).resolve("product").resolve(PRODUCT.get(vm));
   }
 
+  private static String getArchString(DexVm vm) {
+    return vm.isOlderThanOrEqual(DexVm.ART_5_1_1_HOST) ? "arm" : "arm64";
+  }
+
   private static Path getProductBootImagePath(DexVm vm) {
     return getProductPath(vm).resolve("system").resolve("framework").resolve("boot.art");
   }
@@ -717,6 +729,8 @@
     switch (dexVm.version) {
       case DEFAULT:
         return AndroidApiLevel.O;
+      case V9_0_0:
+        return AndroidApiLevel.P;
       case V8_1_0:
         return AndroidApiLevel.O;
       case V7_0_0:
@@ -1438,39 +1452,40 @@
   }
 
   public static void runDex2Oat(Path file, Path outFile) throws IOException {
-    DexVm vm = getDexVm();
-    if (vm.isOlderThanOrEqual(DexVm.ART_5_1_1_HOST)) {
-      // TODO(b/79191363): Support running dex2oat for past android versions.
-      // Run default dex2oat for tests on old runtimes.
-      vm = DexVm.ART_DEFAULT;
-    }
-    runDex2Oat(file, outFile, vm);
+    runDex2Oat(file, outFile, getDexVm());
   }
 
   public static void runDex2Oat(Path file, Path outFile, DexVm vm) throws IOException {
-    Assume.assumeTrue(ToolHelper.isDex2OatSupported());
+    ProcessResult result = runDex2OatRaw(file, outFile, vm);
+    if (result.exitCode != 0) {
+      fail("dex2oat failed, exit code " + result.exitCode + ", stderr:\n" + result.stderr);
+    }
+    if (result.stderr != null && result.stderr.contains("Verification error")) {
+      fail("Verification error: \n" + result.stderr);
+    }
+  }
+
+  public static ProcessResult runDex2OatRaw(Path file, Path outFile, DexVm vm) throws IOException {
     // TODO(jmhenaff): find a way to run this on windows (push dex and run on device/emulator?)
-    Assume.assumeTrue(!ToolHelper.isWindows());
+    Assume.assumeTrue(ToolHelper.isDex2OatSupported());
+    if (vm.isOlderThanOrEqual(DexVm.ART_4_4_4_HOST)) {
+      // Run default dex2oat for tests on dalvik runtimes.
+      vm = DexVm.ART_DEFAULT;
+    }
     assert Files.exists(file);
     assert ByteStreams.toByteArray(Files.newInputStream(file)).length > 0;
     List<String> command = new ArrayList<>();
     command.add(getDex2OatPath(vm).toString());
-    command.add("--android-root=" + getProductPath(vm));
+    command.add("--android-root=" + getProductPath(vm) + "/system");
     command.add("--runtime-arg");
     command.add("-Xnorelocate");
-    command.add("--boot-image=" + getProductBootImagePath(vm));
     command.add("--dex-file=" + file.toAbsolutePath());
     command.add("--oat-file=" + outFile.toAbsolutePath());
-    command.add("--instruction-set=arm64");
+    // TODO(zerny): Create a proper interface for invoking dex2oat. Hardcoding arch here is a hack!
+    command.add("--instruction-set=" + getArchString(vm));
     ProcessBuilder builder = new ProcessBuilder(command);
     builder.environment().put("LD_LIBRARY_PATH", getDexVmLibPath(vm).toString());
-    ProcessResult result = runProcess(builder);
-    if (result.exitCode != 0) {
-      fail("dex2oat failed, exit code " + result.exitCode + ", stderr:\n" + result.stderr);
-    }
-    if (result.stderr.contains("Verification error")) {
-      fail("Verification error: \n" + result.stderr);
-    }
+    return runProcess(builder);
   }
 
   public static ProcessResult runProguardRaw(
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/debug/DebugTestBase.java b/src/test/java/com/android/tools/r8/debug/DebugTestBase.java
index a7b2b223..e6a1fcd 100644
--- a/src/test/java/com/android/tools/r8/debug/DebugTestBase.java
+++ b/src/test/java/com/android/tools/r8/debug/DebugTestBase.java
@@ -1019,6 +1019,10 @@
               artCommandBuilder.appendArtOption("-Xcompiler-option");
               artCommandBuilder.appendArtOption("--debuggable");
             }
+            if (ToolHelper.getDexVm().getVersion().isAtLeast(DexVm.Version.V9_0_0) &&
+                ToolHelper.getDexVm().getVersion() != DexVm.Version.DEFAULT) {
+              artCommandBuilder.appendArtOption("-XjdwpProvider:internal");
+            }
             if (DEBUG_TESTS && ToolHelper.getDexVm().getVersion().isNewerThan(Version.V4_4_4)) {
               artCommandBuilder.appendArtOption("-verbose:jdwp");
             }
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 bd0f8fb..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
@@ -34,6 +34,7 @@
 import com.android.tools.r8.utils.DescriptorUtils;
 import com.android.tools.r8.utils.codeinspector.CodeInspector;
 import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSet;
 import java.util.Map;
 import java.util.function.BiConsumer;
 import org.junit.Test;
@@ -50,7 +51,7 @@
     DexEncodedMethod foo = codeInspector.clazz(mainClass.getName()).method(signature).getMethod();
     IRCode irCode =
         foo.buildIR(appInfo, GraphLense.getIdentityLense(), TEST_OPTIONS, Origin.unknown());
-    NonNullTracker nonNullTracker = new NonNullTracker(appInfo);
+    NonNullTracker nonNullTracker = new NonNullTracker(appInfo, ImmutableSet.of());
     nonNullTracker.addNonNull(irCode);
     TypeAnalysis analysis = new TypeAnalysis(appInfo, foo);
     analysis.widening(foo, irCode);
@@ -158,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);
@@ -184,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/ir/optimize/NonNullTrackerTest.java b/src/test/java/com/android/tools/r8/ir/optimize/NonNullTrackerTest.java
index e569ad2..0ada569 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/NonNullTrackerTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/NonNullTrackerTest.java
@@ -23,6 +23,7 @@
 import com.android.tools.r8.naming.MemberNaming.MethodSignature;
 import com.android.tools.r8.origin.Origin;
 import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import com.google.common.collect.ImmutableSet;
 import java.util.function.Consumer;
 import org.junit.Test;
 
@@ -41,7 +42,7 @@
         foo.buildIR(appInfo, GraphLense.getIdentityLense(), TEST_OPTIONS, Origin.unknown());
     checkCountOfNonNull(irCode, 0);
 
-    NonNullTracker nonNullTracker = new NonNullTracker(appInfo);
+    NonNullTracker nonNullTracker = new NonNullTracker(appInfo, ImmutableSet.of());
 
     nonNullTracker.addNonNull(irCode);
     assertTrue(irCode.isConsistentSSA());
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/classinliner/ClassInlinerTest.java b/src/test/java/com/android/tools/r8/ir/optimize/classinliner/ClassInlinerTest.java
index 4e6bb21..592aeae 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/classinliner/ClassInlinerTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/classinliner/ClassInlinerTest.java
@@ -12,7 +12,10 @@
 import static org.junit.Assert.assertTrue;
 import static org.junit.Assert.fail;
 
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.R8Command;
 import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestRunResult;
 import com.android.tools.r8.ToolHelper;
 import com.android.tools.r8.ToolHelper.ProcessResult;
 import com.android.tools.r8.ir.optimize.classinliner.builders.BuildersTestClass;
@@ -38,6 +41,7 @@
 import com.android.tools.r8.jasmin.JasminBuilder;
 import com.android.tools.r8.jasmin.JasminBuilder.ClassBuilder;
 import com.android.tools.r8.naming.MemberNaming.MethodSignature;
+import com.android.tools.r8.origin.Origin;
 import com.android.tools.r8.utils.AndroidApp;
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.StringUtils;
@@ -46,9 +50,9 @@
 import com.android.tools.r8.utils.codeinspector.FieldAccessInstructionSubject;
 import com.android.tools.r8.utils.codeinspector.InstructionSubject;
 import com.android.tools.r8.utils.codeinspector.NewInstanceInstructionSubject;
+import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Sets;
 import com.google.common.collect.Streams;
-import java.io.IOException;
 import java.nio.file.Path;
 import java.util.Collections;
 import java.util.Iterator;
@@ -73,39 +77,35 @@
     this.backend = backend;
   }
 
-  private String run(AndroidApp app, Class mainClass) throws IOException {
-    if (backend == Backend.DEX) {
-      return runOnArt(app, mainClass);
-    } else {
-      assert backend == Backend.CF;
-      return runOnJava(app, mainClass);
-    }
-  }
-
   @Test
   public void testTrivial() throws Exception {
-    byte[][] classes = {
-        ToolHelper.getClassAsBytes(TrivialTestClass.class),
-        ToolHelper.getClassAsBytes(TrivialTestClass.Inner.class),
-        ToolHelper.getClassAsBytes(ReferencedFields.class),
-        ToolHelper.getClassAsBytes(EmptyClass.class),
-        ToolHelper.getClassAsBytes(EmptyClassWithInitializer.class),
-        ToolHelper.getClassAsBytes(Iface1.class),
-        ToolHelper.getClassAsBytes(Iface1Impl.class),
-        ToolHelper.getClassAsBytes(Iface2.class),
-        ToolHelper.getClassAsBytes(Iface2Impl.class),
-        ToolHelper.getClassAsBytes(CycleReferenceAB.class),
-        ToolHelper.getClassAsBytes(CycleReferenceBA.class),
-        ToolHelper.getClassAsBytes(ClassWithFinal.class)
+    Class<?> main = TrivialTestClass.class;
+    Class<?>[] classes = {
+        TrivialTestClass.class,
+        TrivialTestClass.Inner.class,
+        ReferencedFields.class,
+        EmptyClass.class,
+        EmptyClassWithInitializer.class,
+        Iface1.class,
+        Iface1Impl.class,
+        Iface2.class,
+        Iface2Impl.class,
+        CycleReferenceAB.class,
+        CycleReferenceBA.class,
+        ClassWithFinal.class
     };
-    AndroidApp app = runR8(buildAndroidApp(classes), TrivialTestClass.class);
+    String javaOutput = runOnJava(main);
+    TestRunResult result = testForR8(backend)
+        .addProgramClasses(classes)
+        .addKeepMainRule(main)
+        .addKeepRules(
+            "-dontobfuscate", "-allowaccessmodification", "-keepattributes LineNumberTable")
+        .addOptionsModification(this::configure)
+        .run(main)
+        .assertSuccessWithOutput(javaOutput);
 
-    String javaOutput = runOnJava(TrivialTestClass.class);
-    String output = run(app, TrivialTestClass.class);
-    assertEquals(javaOutput, output);
-
-    CodeInspector inspector = new CodeInspector(app);
-    ClassSubject clazz = inspector.clazz(TrivialTestClass.class);
+    CodeInspector inspector = result.inspector();
+    ClassSubject clazz = inspector.clazz(main);
 
     assertEquals(
         Collections.singleton("java.lang.StringBuilder"),
@@ -162,28 +162,44 @@
 
   @Test
   public void testBuilders() throws Exception {
-    byte[][] classes = {
-        ToolHelper.getClassAsBytes(BuildersTestClass.class),
-        ToolHelper.getClassAsBytes(BuildersTestClass.Pos.class),
-        ToolHelper.getClassAsBytes(Tuple.class),
-        ToolHelper.getClassAsBytes(Pair.class),
-        ToolHelper.getClassAsBytes(PairBuilder.class),
-        ToolHelper.getClassAsBytes(ControlFlow.class),
+    Class<?> main = BuildersTestClass.class;
+    Class<?>[] classes = {
+        NeverInline.class,
+        BuildersTestClass.class,
+        BuildersTestClass.Pos.class,
+        Tuple.class,
+        Pair.class,
+        PairBuilder.class,
+        ControlFlow.class,
     };
-    AndroidApp app = runR8(buildAndroidApp(classes), BuildersTestClass.class);
+    String javaOutput = runOnJava(main);
+    TestRunResult result = testForR8(backend)
+        .addProgramClasses(classes)
+        .enableProguardTestOptions()
+        .enableInliningAnnotations()
+        .addKeepMainRule(main)
+        .addKeepRules(
+            "-dontobfuscate", "-allowaccessmodification", "-keepattributes LineNumberTable")
+        .addOptionsModification(this::configure)
+        .run(main)
+        .assertSuccessWithOutput(javaOutput);
 
-    String javaOutput = runOnJava(BuildersTestClass.class);
-    String output = run(app, BuildersTestClass.class);
-    assertEquals(javaOutput, output);
+    CodeInspector inspector = result.inspector();
+    ClassSubject clazz = inspector.clazz(main);
 
-    CodeInspector inspector = new CodeInspector(app);
-    ClassSubject clazz = inspector.clazz(BuildersTestClass.class);
-
-    assertEquals(
-        Sets.newHashSet(
-            "com.android.tools.r8.ir.optimize.classinliner.builders.Pair",
-            "java.lang.StringBuilder"),
-        collectTypes(clazz, "testSimpleBuilder", "void"));
+    for (int i = 1; i <= 3; i++) {
+      Set<String> expected =
+          Sets.newHashSet(
+              "com.android.tools.r8.ir.optimize.classinliner.builders.Pair",
+              "java.lang.StringBuilder");
+      if (backend == Backend.CF && i < 3) {
+        // const-string canonicalization is disabled in CF, which helps ClassInliner identify
+        // PairBuilder as candidate. Concatenated builder calls in test #3 bother that again.
+        expected.add("com.android.tools.r8.ir.optimize.classinliner.builders.PairBuilder");
+      }
+      assertEquals(expected,
+          collectTypes(clazz, "testSimpleBuilder" + i, "void"));
+    }
 
     // Note that Pair created instances were also inlined in the following method since
     // we use 'System.out.println(pX.toString())', if we used 'System.out.println(pX)'
@@ -193,7 +209,9 @@
         Collections.singleton("java.lang.StringBuilder"),
         collectTypes(clazz, "testSimpleBuilderWithMultipleBuilds", "void"));
 
-    assertFalse(inspector.clazz(PairBuilder.class).isPresent());
+    if (backend == Backend.DEX) {
+      assertFalse(inspector.clazz(PairBuilder.class).isPresent());
+    }
 
     assertEquals(
         Collections.singleton("java.lang.StringBuilder"),
@@ -242,7 +260,6 @@
         runOnJavaRaw(mainClass.name, builder.buildClasses().toArray(new byte[2][]));
     assertThat(javaResult.stderr, containsString("IncompatibleClassChangeError"));
 
-    assert backend == Backend.DEX || backend == Backend.CF;
     // Check that the code fails with an IncompatibleClassChangeError with ART.
     ProcessResult result =
         backend == Backend.DEX
@@ -253,19 +270,24 @@
 
   @Test
   public void testCodeSample() throws Exception {
-    byte[][] classes = {
-        ToolHelper.getClassAsBytes(C.class),
-        ToolHelper.getClassAsBytes(C.L.class),
-        ToolHelper.getClassAsBytes(C.F.class),
-        ToolHelper.getClassAsBytes(CodeTestClass.class)
+    Class<?> main = CodeTestClass.class;
+    Class<?>[] classes = {
+        C.class,
+        C.L.class,
+        C.F.class,
+        CodeTestClass.class
     };
-    AndroidApp app = runR8(buildAndroidApp(classes), CodeTestClass.class);
+    String javaOutput = runOnJava(main);
+    TestRunResult result = testForR8(backend)
+        .addProgramClasses(classes)
+        .addKeepMainRule(main)
+        .addKeepRules(
+            "-dontobfuscate", "-allowaccessmodification", "-keepattributes LineNumberTable")
+        .addOptionsModification(this::configure)
+        .run(main)
+        .assertSuccessWithOutput(javaOutput);
 
-    String javaOutput = runOnJava(CodeTestClass.class);
-    String output = run(app, CodeTestClass.class);
-    assertEquals(javaOutput, output);
-
-    CodeInspector inspector = new CodeInspector(app);
+    CodeInspector inspector = result.inspector();
     ClassSubject clazz = inspector.clazz(C.class);
 
     assertEquals(
@@ -287,22 +309,26 @@
   @Test
   public void testInvalidatedRoot() throws Exception {
     String prefix = "com.android.tools.r8.ir.optimize.classinliner.invalidroot.";
-
-    byte[][] classes = {
-        ToolHelper.getClassAsBytes(InvalidRootsTestClass.class),
-        ToolHelper.getClassAsBytes(InvalidRootsTestClass.A.class),
-        ToolHelper.getClassAsBytes(InvalidRootsTestClass.B.class),
-        ToolHelper.getClassAsBytes(InvalidRootsTestClass.NeverReturnsNormally.class),
-        ToolHelper.getClassAsBytes(InvalidRootsTestClass.InitNeverReturnsNormally.class)
+    Class<?> main = InvalidRootsTestClass.class;
+    Class<?>[] classes = {
+        InvalidRootsTestClass.class,
+        InvalidRootsTestClass.A.class,
+        InvalidRootsTestClass.B.class,
+        InvalidRootsTestClass.NeverReturnsNormally.class,
+        InvalidRootsTestClass.InitNeverReturnsNormally.class
     };
-    AndroidApp app = runR8(buildAndroidApp(classes), InvalidRootsTestClass.class);
+    String javaOutput = runOnJava(main);
+    TestRunResult result = testForR8(backend)
+        .addProgramClasses(classes)
+        .addKeepMainRule(main)
+        .addKeepRules(
+            "-dontobfuscate", "-allowaccessmodification", "-keepattributes LineNumberTable")
+        .addOptionsModification(this::configure)
+        .run(main)
+        .assertSuccessWithOutput(javaOutput);
 
-    String javaOutput = runOnJava(InvalidRootsTestClass.class);
-    String output = run(app, InvalidRootsTestClass.class);
-    assertEquals(javaOutput, output);
-
-    CodeInspector inspector = new CodeInspector(app);
-    ClassSubject clazz = inspector.clazz(InvalidRootsTestClass.class);
+    CodeInspector inspector = result.inspector();
+    ClassSubject clazz = inspector.clazz(main);
 
     assertEquals(
         Sets.newHashSet(prefix + "InvalidRootsTestClass$NeverReturnsNormally"),
@@ -331,20 +357,25 @@
 
   @Test
   public void testDesugaredLambdas() throws Exception {
-    Assume.assumeFalse(backend == Backend.CF); // No desugaring with CF backend.
-    byte[][] classes = {
-        ToolHelper.getClassAsBytes(LambdasTestClass.class),
-        ToolHelper.getClassAsBytes(LambdasTestClass.Iface.class),
-        ToolHelper.getClassAsBytes(LambdasTestClass.IfaceUtil.class),
+    Assume.assumeFalse("No desugaring with CF backend", backend == Backend.CF);
+    Class<?> main = LambdasTestClass.class;
+    Class<?>[] classes = {
+        LambdasTestClass.class,
+        LambdasTestClass.Iface.class,
+        LambdasTestClass.IfaceUtil.class
     };
-    AndroidApp app = runR8(buildAndroidApp(classes), LambdasTestClass.class);
+    String javaOutput = runOnJava(main);
+    TestRunResult result = testForR8(backend)
+        .addProgramClasses(classes)
+        .addKeepMainRule(main)
+        .addKeepRules(
+            "-dontobfuscate", "-allowaccessmodification", "-keepattributes LineNumberTable")
+        .addOptionsModification(this::configure)
+        .run(main)
+        .assertSuccessWithOutput(javaOutput);
 
-    String javaOutput = runOnJava(LambdasTestClass.class);
-    String output = run(app, LambdasTestClass.class);
-    assertEquals(javaOutput, output);
-
-    CodeInspector inspector = new CodeInspector(app);
-    ClassSubject clazz = inspector.clazz(LambdasTestClass.class);
+    CodeInspector inspector = result.inspector();
+    ClassSubject clazz = inspector.clazz(main);
 
     assertEquals(
         Sets.newHashSet(
@@ -391,42 +422,6 @@
         .map(fais -> fais.holder().toString());
   }
 
-  private AndroidApp runR8(AndroidApp app, Class mainClass) throws Exception {
-    AndroidApp compiled =
-        compileWithR8(
-            app, getProguardConfig(mainClass.getCanonicalName()), this::configure, backend);
-
-    // Materialize file for execution.
-    Path generatedFile = temp.getRoot().toPath().resolve("classes.jar");
-    compiled.writeToZip(generatedFile, outputMode(backend));
-
-    assert backend == Backend.DEX || backend == Backend.CF;
-
-    String output =
-        backend == Backend.DEX
-            ? ToolHelper.runArtNoVerificationErrors(
-                generatedFile.toString(), mainClass.getCanonicalName())
-            : ToolHelper.runJava(generatedFile, mainClass.getCanonicalName()).stdout;
-
-    // Compare with Java.
-    ToolHelper.ProcessResult javaResult = ToolHelper.runJava(
-        ToolHelper.getClassPathForTests(), mainClass.getCanonicalName());
-
-    if (javaResult.exitCode != 0) {
-      System.out.println(javaResult.stdout);
-      System.err.println(javaResult.stderr);
-      fail("JVM on original program failed for: " + mainClass);
-    }
-    assertEquals(
-        backend == Backend.DEX
-            ? "JVM and ART output differ."
-            : "Output of original and processed program differ on JVM.",
-        javaResult.stdout,
-        output);
-
-    return compiled;
-  }
-
   private String getProguardConfig(String main) {
     return StringUtils.joinLines(
         keepMainProguardConfiguration(main),
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/classinliner/builders/BuildersTestClass.java b/src/test/java/com/android/tools/r8/ir/optimize/classinliner/builders/BuildersTestClass.java
index 1516e14..aa6d4dc 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/classinliner/builders/BuildersTestClass.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/classinliner/builders/BuildersTestClass.java
@@ -4,6 +4,8 @@
 
 package com.android.tools.r8.ir.optimize.classinliner.builders;
 
+import com.android.tools.r8.NeverInline;
+
 public class BuildersTestClass {
   private static int ID = 0;
 
@@ -17,31 +19,35 @@
 
   public static void main(String[] args) {
     BuildersTestClass test = new BuildersTestClass();
-    test.testSimpleBuilder();
+    test.testSimpleBuilder1();
     test.testSimpleBuilderWithMultipleBuilds();
     test.testBuilderConstructors();
     test.testWithControlFlow();
     test.testWithMoreControlFlow();
   }
 
-  private synchronized void testSimpleBuilder() {
+  @NeverInline
+  private void testSimpleBuilder1() {
     System.out.println(
-        new PairBuilder<String, String>().setFirst("f-" + next()).build().toString());
+        new PairBuilder<String, String>().setFirst("f-" + next()).build());
     testSimpleBuilder2();
     testSimpleBuilder3();
   }
 
-  private synchronized void testSimpleBuilder2() {
+  @NeverInline
+  private void testSimpleBuilder2() {
     System.out.println(
-        new PairBuilder<String, String>().setSecond("s-" + next()).build().toString());
+        new PairBuilder<String, String>().setSecond("s-" + next()).build());
   }
 
-  private synchronized void testSimpleBuilder3() {
+  @NeverInline
+  private void testSimpleBuilder3() {
     System.out.println(new PairBuilder<String, String>()
-        .setFirst("f-" + next()).setSecond("s-" + next()).build().toString());
+        .setFirst("f-" + next()).setSecond("s-" + next()).build());
   }
 
-  private synchronized void testSimpleBuilderWithMultipleBuilds() {
+  @NeverInline
+  private void testSimpleBuilderWithMultipleBuilds() {
     PairBuilder<String, String> builder = new PairBuilder<>();
     Pair p1 = builder.build();
     System.out.println(p1.toString());
@@ -53,13 +59,15 @@
     System.out.println(p3.toString());
   }
 
-  private synchronized void testBuilderConstructors() {
+  @NeverInline
+  private void testBuilderConstructors() {
     System.out.println(new Tuple().toString());
     System.out.println(new Tuple(true, (byte) 77, (short) 9977, '#', 42,
         987654321123456789L, -12.34f, 43210.98765, "s-" + next() + "-s").toString());
   }
 
-  private synchronized void testWithControlFlow() {
+  @NeverInline
+  private void testWithControlFlow() {
     ControlFlow flow = new ControlFlow(-1, 2, 7);
     for (int k = 0; k < 25; k++) {
       if (k % 3 == 0) {
@@ -71,7 +79,8 @@
     System.out.println("flow = " + flow.toString());
   }
 
-  private synchronized void testWithMoreControlFlow() {
+  @NeverInline
+  private void testWithMoreControlFlow() {
     String str = "1234567890";
     Pos pos = new Pos();
     while (pos.y < str.length()) {
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/instanceofremoval/InstanceOfRemovalTest.java b/src/test/java/com/android/tools/r8/ir/optimize/instanceofremoval/InstanceOfRemovalTest.java
index f078262..6fea6cd 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/instanceofremoval/InstanceOfRemovalTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/instanceofremoval/InstanceOfRemovalTest.java
@@ -134,6 +134,6 @@
         inspector.clazz(TestClass.class).method("void", "bar", ImmutableList.of());
     Iterator<InstructionSubject> barInstructionIterator =
         barMethodSubject.iterateInstructions(InstructionSubject::isInstanceOf);
-    assertEquals(6, Streams.stream(barInstructionIterator).count());
+    assertEquals(4, Streams.stream(barInstructionIterator).count());
   }
 }
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/reflection/GetNameTest.java b/src/test/java/com/android/tools/r8/ir/optimize/reflection/GetNameTest.java
index 09ab7f7..eb8f36f 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/reflection/GetNameTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/reflection/GetNameTest.java
@@ -153,6 +153,53 @@
       // getSimpleName, local
       "-Returned-empty-"
   );
+  private static final String RENAMED_OUTPUT = StringUtils.lines(
+      // getName
+      "com.android.tools.r8.ir.optimize.reflection.e",
+      // getTypeName
+      // TODO(b/119426668): desugar Type#getTypeName
+      // "com.android.tools.r8.ir.optimize.reflection.e",
+      // getCanonicalName
+      "com.android.tools.r8.ir.optimize.reflection.e",
+      // getSimpleName
+      "e",
+      // getName, inner
+      "com.android.tools.r8.ir.optimize.reflection.c",
+      // getTypeName, inner
+      // TODO(b/119426668): desugar Type#getTypeName
+      // "com.android.tools.r8.ir.optimize.reflection.c",
+      // getCanonicalName, inner
+      "com.android.tools.r8.ir.optimize.reflection.c",
+      // getSimpleName, inner
+      "c",
+      // getName, array
+      "[Lcom.android.tools.r8.ir.optimize.reflection.e;",
+      // getTypeName, array
+      // TODO(b/119426668): desugar Type#getTypeName
+      // "com.android.tools.r8.ir.optimize.reflection.e[]",
+      // getCanonicalName, array
+      "com.android.tools.r8.ir.optimize.reflection.e[]",
+      // getSimpleName, array
+      "e[]",
+      // getName, anonymous
+      "com.android.tools.r8.ir.optimize.reflection.a",
+      // getTypeName, anonymous
+      // TODO(b/119426668): desugar Type#getTypeName
+      // "com.android.tools.r8.ir.optimize.reflection.a",
+      // getCanonicalName, anonymous
+      "-Returned-null-",
+      // getSimpleName, anonymous
+      "-Returned-empty-",
+      // getName, local
+      "com.android.tools.r8.ir.optimize.reflection.b",
+      // getTypeName, local
+      // TODO(b/119426668): desugar Type#getTypeName
+      // "com.android.tools.r8.ir.optimize.reflection.b,
+      // getCanonicalName, local
+      "-Returned-null-",
+      // getSimpleName, local
+      "-Returned-empty-"
+  );
   private static final Class<?> MAIN = GetName0Main.class;
 
   public GetNameTest(Backend backend, boolean enableMinification) throws Exception {
@@ -190,6 +237,7 @@
     TestRunResult result = testForD8()
         .debug()
         .addProgramFiles(classPaths)
+        .addOptionsModification(this::configure)
         .run(MAIN)
         .assertSuccessWithOutput(JAVA_OUTPUT);
     test(result, 15);
@@ -197,10 +245,11 @@
     result = testForD8()
         .release()
         .addProgramFiles(classPaths)
+        .addOptionsModification(this::configure)
         .run(MAIN)
         .assertSuccessWithOutput(JAVA_OUTPUT);
     // getClass() -> const-class is not available in D8.
-    test(result, 9);
+    test(result, 11);
   }
 
   @Test
@@ -212,18 +261,17 @@
         .enableInliningAnnotations()
         .addKeepMainRule(MAIN)
         .addKeepRules("-keep class **.GetName0*")
-        .addKeepRules("-keepattributes InnerClasses,EnclosingMethod");
+        .addKeepRules("-keepattributes InnerClasses,EnclosingMethod")
+        .addKeepRules("-printmapping " + createNewMappingPath().toAbsolutePath().toString());
     if (!enableMinification) {
       builder.addKeepRules("-dontobfuscate");
     }
-    TestRunResult result = builder.run(MAIN);
-    if (enableMinification) {
-      // TODO(b/118536394): Check even renamed names.
-      test(result, 11);
-    } else {
-      result.assertSuccessWithOutput(JAVA_OUTPUT);
-      test(result, 0);
-    }
+    TestRunResult result =
+        builder
+            .addOptionsModification(this::configure)
+            .run(MAIN)
+            .assertSuccessWithOutput(JAVA_OUTPUT);
+    test(result, 2);
   }
 
   @Test
@@ -235,22 +283,26 @@
         .enableInliningAnnotations()
         .addKeepMainRule(MAIN)
         .addKeepRules("-keep,allowobfuscation class **.GetName0*")
-        .addKeepRules("-keepattributes InnerClasses,EnclosingMethod");
+        .addKeepRules("-keepattributes InnerClasses,EnclosingMethod")
+        .addKeepRules("-printmapping " + createNewMappingPath().toAbsolutePath().toString());
     if (!enableMinification) {
       builder.addKeepRules("-dontobfuscate");
     }
-    TestRunResult result = builder.run(MAIN);
+    TestRunResult result =
+        builder
+            .addOptionsModification(this::configure)
+            .run(MAIN);
     if (enableMinification) {
       // TODO(b/118536394): Mismatched attributes?
       if (backend == Backend.CF) {
         return;
       }
-      // TODO(b/118536394): Check even renamed names.
-      test(result, 11);
+      // TODO(b/120185045): Short name of innerName is not renamed.
+      // result.assertSuccessWithOutput(RENAMED_OUTPUT);
     } else {
       result.assertSuccessWithOutput(JAVA_OUTPUT);
-      test(result, 0);
     }
+    test(result, 2);
   }
 
 }
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/reflection/GetNameTestBase.java b/src/test/java/com/android/tools/r8/ir/optimize/reflection/GetNameTestBase.java
index ef7a07b..2c09d18 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/reflection/GetNameTestBase.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/reflection/GetNameTestBase.java
@@ -4,10 +4,14 @@
 package com.android.tools.r8.ir.optimize.reflection;
 
 import com.android.tools.r8.TestBase;
+import com.android.tools.r8.ToolHelper;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.utils.BooleanUtils;
+import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.codeinspector.MethodSubject;
 import com.google.common.collect.Streams;
+import java.io.IOException;
+import java.nio.file.Path;
 import java.util.Collection;
 import org.junit.runner.RunWith;
 import org.junit.runners.Parameterized;
@@ -19,6 +23,7 @@
 
   final Backend backend;
   final boolean enableMinification;
+  Path mapping;
 
   @Parameterized.Parameters(name = "Backend: {0} minification: {1}")
   public static Collection<Object[]> data() {
@@ -30,6 +35,15 @@
     this.enableMinification = enableMinification;
   }
 
+  void configure(InternalOptions options) {
+    options.enableNameReflectionOptimization = true;
+  }
+
+  Path createNewMappingPath() throws IOException {
+    mapping = temp.newFile(ToolHelper.DEFAULT_PROGUARD_MAP_FILE).toPath();
+    return mapping;
+  }
+
   static boolean isNameReflection(DexMethod method) {
     return method.getHolder().toDescriptorString().equals(CLASS_DESCRIPTOR)
         && method.getArity() == 0
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/reflection/GetSimpleNameTest.java b/src/test/java/com/android/tools/r8/ir/optimize/reflection/GetSimpleNameTest.java
index 54015e3..6f2fb17 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/reflection/GetSimpleNameTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/reflection/GetSimpleNameTest.java
@@ -8,10 +8,12 @@
 import static org.junit.Assert.assertThat;
 import static org.junit.Assume.assumeTrue;
 
+import com.android.tools.r8.ForceInline;
 import com.android.tools.r8.NeverInline;
 import com.android.tools.r8.R8TestBuilder;
 import com.android.tools.r8.TestRunResult;
 import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.ToolHelper.DexVm;
 import com.android.tools.r8.utils.StringUtils;
 import com.android.tools.r8.utils.codeinspector.ClassSubject;
 import com.android.tools.r8.utils.codeinspector.CodeInspector;
@@ -71,10 +73,41 @@
     System.out.println(a2.getSimpleName());
   }
 
+  @NeverInline
+  static void b120130435() {
+    System.out.println(Outer.Inner.class.getSimpleName());
+    System.out.println(Outer.TestHelper.getHelper().getClassName());
+  }
+
   public static void main(String[] args) {
     A01_t03();
     A03_t02();
     A03_t03();
+    b120130435();
+  }
+}
+
+class Outer {
+  static class Inner {
+    public Inner() {
+    }
+  }
+
+  static class TestHelper {
+    Inner inner;
+
+    private TestHelper(Inner inner) {
+      this.inner = inner;
+    }
+
+    @ForceInline
+    String getClassName() {
+      return inner.getClass().getSimpleName();
+    }
+
+    static TestHelper getHelper() {
+      return new TestHelper(new Inner());
+    }
   }
 }
 
@@ -86,7 +119,39 @@
       "$",
       "$$",
       "Local[][][]",
-      "[][][]"
+      "[][][]",
+      "Inner",
+      "Inner"
+  );
+  private static final String OUTPUT_WITH_SHRUNK_ATTRIBUTE = StringUtils.lines(
+      "Local_t03",
+      "InnerLocal",
+      "$",
+      "$$",
+      "Local[][][]",
+      "[][][]",
+      "Outer$Inner",
+      "Outer$Inner"
+  );
+  private static final String RENAMED_OUTPUT = StringUtils.lines(
+      "f",
+      "InnerLocal",
+      "b",
+      "$$",
+      "d[][][]",
+      "[][][]",
+      "Inner",
+      "Inner"
+  );
+  private static final String RENAMED_OUTPUT_FOR_OLDER_VMS = StringUtils.lines(
+      "Local_t03",
+      "InnerLocal",
+      "$",
+      "$$",
+      "Local[][][]",
+      "[][][]",
+      "Inner",
+      "Inner"
   );
   private static final Class<?> MAIN = ClassGetSimpleName.class;
 
@@ -97,6 +162,10 @@
     builder.addAll(ToolHelper.getClassFilesForTestDirectory(
         ToolHelper.getPackageDirectoryForTestPackage(MAIN.getPackage()),
         path -> path.getFileName().toString().startsWith("ClassGetSimpleName")));
+    builder.add(ToolHelper.getClassFileForTestClass(Outer.class));
+    builder.add(ToolHelper.getClassFileForTestClass(Outer.Inner.class));
+    builder.add(ToolHelper.getClassFileForTestClass(Outer.TestHelper.class));
+    builder.add(ToolHelper.getClassFileForTestClass(ForceInline.class));
     builder.add(ToolHelper.getClassFileForTestClass(NeverInline.class));
     classPaths = builder.build();
   }
@@ -125,6 +194,7 @@
     TestRunResult result = testForD8()
         .debug()
         .addProgramFiles(classPaths)
+        .addOptionsModification(this::configure)
         .run(MAIN)
         .assertSuccessWithOutput(JAVA_OUTPUT);
     test(result, 0);
@@ -132,6 +202,7 @@
     result = testForD8()
         .release()
         .addProgramFiles(classPaths)
+        .addOptionsModification(this::configure)
         .run(MAIN)
         .assertSuccessWithOutput(JAVA_OUTPUT);
     test(result, 0);
@@ -146,16 +217,17 @@
         .enableInliningAnnotations()
         .addKeepMainRule(MAIN)
         .addKeepRules("-keep class **.ClassGetSimpleName*")
-        .addKeepRules("-keepattributes InnerClasses,EnclosingMethod");
+        .addKeepRules("-keep class **.Outer*")
+        .addKeepRules("-keepattributes InnerClasses,EnclosingMethod")
+        .addKeepRules("-printmapping " + createNewMappingPath().toAbsolutePath().toString());
     if (!enableMinification) {
       builder.addKeepRules("-dontobfuscate");
     }
-    TestRunResult result = builder.run(MAIN);
-    if (enableMinification) {
-      // TODO(b/118536394): Check even renamed simple name.
-    } else {
-      result.assertSuccessWithOutput(JAVA_OUTPUT);
-    }
+    TestRunResult result =
+        builder
+            .addOptionsModification(this::configure)
+            .run(MAIN)
+            .assertSuccessWithOutput(JAVA_OUTPUT);
     test(result, 0);
   }
 
@@ -168,17 +240,30 @@
         .enableInliningAnnotations()
         .addKeepMainRule(MAIN)
         .addKeepRules("-keep,allowobfuscation class **.ClassGetSimpleName*")
-        .addKeepRules("-keepattributes InnerClasses,EnclosingMethod");
+        // See b/119471127: some old VMs are not resilient to broken attributes.
+        // Comment out the following line to reproduce b/120130435
+        // then use OUTPUT_WITH_SHRUNK_ATTRIBUTE
+        .addKeepRules("-keep,allowobfuscation class **.Outer*")
+        .addKeepRules("-keepattributes InnerClasses,EnclosingMethod")
+        .addKeepRules("-printmapping " + createNewMappingPath().toAbsolutePath().toString());
     if (!enableMinification) {
       builder.addKeepRules("-dontobfuscate");
     }
-    TestRunResult result = builder.run(MAIN);
+    TestRunResult result =
+        builder
+            .addOptionsModification(this::configure)
+            .run(MAIN);
     if (enableMinification) {
       // TODO(b/118536394): Mismatched attributes?
       if (backend == Backend.CF) {
         return;
       }
-      // TODO(b/118536394): Check even renamed simple name.
+      // TODO(b/120185045): Short name of innerName is not renamed.
+      if (ToolHelper.getDexVm().isOlderThanOrEqual(DexVm.ART_4_4_4_HOST)) {
+        result.assertSuccessWithOutput(RENAMED_OUTPUT_FOR_OLDER_VMS);
+      } else {
+        result.assertSuccessWithOutput(RENAMED_OUTPUT);
+      }
     } else {
       result.assertSuccessWithOutput(JAVA_OUTPUT);
     }
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/string/StringContentCheckTest.java b/src/test/java/com/android/tools/r8/ir/optimize/string/StringContentCheckTest.java
index 353dd50..284af11 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/string/StringContentCheckTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/string/StringContentCheckTest.java
@@ -30,7 +30,10 @@
   static boolean argCouldBeNull(String arg) {
     return "CONST".contains(arg)
         && "prefix".startsWith(arg)
-        && "suffix".endsWith(arg);
+        && "suffix".endsWith(arg)
+        && "CONST".equals(arg)
+        && "CONST".equalsIgnoreCase(arg)
+        && "CONST".contentEquals(arg);
   }
 
   public static void main(String[] args) {
@@ -39,6 +42,10 @@
       System.out.println(s1.contains("CONST"));
       System.out.println(s1.startsWith("prefix"));
       System.out.println(s1.endsWith("suffix"));
+      System.out.println(s1.equals("prefix-CONST-suffix"));
+      System.out.println(s1.equalsIgnoreCase("PREFIX-const-SUFFIX"));
+      System.out.println(s1.contentEquals("prefix-CONST-suffix"));
+      System.out.println(s1.contentEquals(new StringBuffer("prefix-CONST-suffix")));
     }
 
     {
@@ -47,6 +54,10 @@
       System.out.println(s2.contains("CONST"));
       System.out.println(s2.startsWith("prefix"));
       System.out.println(s2.endsWith("suffix"));
+      System.out.println(s2.equals("prefix-CONST-suffix"));
+      System.out.println(s2.equalsIgnoreCase("pre-con-suf"));
+      System.out.println(s2.contentEquals("prefix-CONST-suffix"));
+      System.out.println(s2.contentEquals(new StringBuffer("prefix-CONST-suffix")));
     }
 
     {
@@ -75,12 +86,28 @@
       "true",
       // s1, endsWith
       "true",
+      // s1, equals
+      "true",
+      // s1, equalsIgnoreCase
+      "true",
+      // s1, contentEquals(CharSequence)
+      "true",
+      // s1, contentEquals(StringBuffer)
+      "true",
       // s2, contains
       "false",
       // s2, startsWith
       "false",
       // s2, endsWith
       "false",
+      // s2, equals
+      "false",
+      // s2, equalsIgnoreCase
+      "false",
+      // s2, contentEquals(CharSequence)
+      "false",
+      // s2, contentEquals(StringBuffer)
+      "false",
       // argCouldBeNull
       "false"
   );
@@ -107,7 +134,10 @@
         && method.proto.returnType.isBooleanType()
         && (method.name.toString().equals("contains")
             || method.name.toString().equals("startsWith")
-            || method.name.toString().equals("endsWith"));
+            || method.name.toString().equals("endsWith")
+            || method.name.toString().equals("equals")
+            || method.name.toString().equals("equalsIgnoreCase")
+            || method.name.toString().equals("contentEquals"));
   }
 
   private long countStringContentChecker(MethodSubject method) {
@@ -131,7 +161,7 @@
         "boolean", "argCouldBeNull", ImmutableList.of("java.lang.String"));
     assertThat(argCouldBeNull, isPresent());
     // Because of nullable argument, all checkers should remain.
-    assertEquals(3, countStringContentChecker(argCouldBeNull));
+    assertEquals(6, countStringContentChecker(argCouldBeNull));
   }
 
   @Test
@@ -143,14 +173,14 @@
         .addProgramClasses(CLASSES)
         .run(MAIN)
         .assertSuccessWithOutput(JAVA_OUTPUT);
-    test(result, 6);
+    test(result, 14);
 
     result = testForD8()
         .release()
         .addProgramClasses(CLASSES)
         .run(MAIN)
         .assertSuccessWithOutput(JAVA_OUTPUT);
-    test(result, 3);
+    test(result, 8);
   }
 
   @Test
@@ -162,6 +192,6 @@
         .addKeepMainRule(MAIN)
         .run(MAIN)
         .assertSuccessWithOutput(JAVA_OUTPUT);
-    test(result, 3);
+    test(result, 8);
   }
 }
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/string/StringValueOfTest.java b/src/test/java/com/android/tools/r8/ir/optimize/string/StringValueOfTest.java
index 6642619..09d4cc4 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/string/StringValueOfTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/string/StringValueOfTest.java
@@ -14,6 +14,7 @@
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.TestRunResult;
 import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.StringUtils;
 import com.android.tools.r8.utils.codeinspector.ClassSubject;
 import com.android.tools.r8.utils.codeinspector.CodeInspector;
@@ -54,13 +55,9 @@
 
   public static void main(String[] args) {
     Foo foo = new Foo();
-    // TODO(b/118536394): valueOf in getter() can be removed if combined with name reflection
-    // optimization, which will replace it with (definitely non-null) const-string.
     System.out.println(foo.getter());
     // Trivial, it's String.
     String str = foo.toString();
-    // TODO(b/119449728): But, it's still nullable.
-    // valueOf can be removed if the nullability of its return value is modeled.
     System.out.println(String.valueOf(str));
     if (str != null) {
       // With an explicit check, it's non-null String.
@@ -111,6 +108,9 @@
     this.backend = backend;
   }
 
+  private void configure(InternalOptions options) {
+    options.enableNameReflectionOptimization = true;
+  }
 
   @Test
   public void testJVMoutput() throws Exception {
@@ -193,8 +193,9 @@
         .enableInliningAnnotations()
         .addKeepMainRule(MAIN)
         .addKeepRules("-dontobfuscate")
+        .addOptionsModification(this::configure)
         .run(MAIN)
         .assertSuccessWithOutput(JAVA_OUTPUT);
-    test(result, 3, 1, 1);
+    test(result, 1, 1, 1);
   }
 }
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/regress/b118075510/Regress118075510Runner.java b/src/test/java/com/android/tools/r8/regress/b118075510/Regress118075510Runner.java
new file mode 100644
index 0000000..12bd452
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/regress/b118075510/Regress118075510Runner.java
@@ -0,0 +1,54 @@
+// 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.regress.b118075510;
+
+import com.android.tools.r8.AsmTestBase;
+import com.android.tools.r8.CompilationFailedException;
+import com.android.tools.r8.D8TestCompileResult;
+import com.android.tools.r8.utils.AndroidApiLevel;
+import com.android.tools.r8.utils.StringUtils;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import com.android.tools.r8.utils.codeinspector.MethodSubject;
+import java.io.IOException;
+import java.util.concurrent.ExecutionException;
+import org.junit.Assert;
+import org.junit.Test;
+
+public class Regress118075510Runner extends AsmTestBase {
+
+  public static final Class<?> CLASS = Regress118075510Test.class;
+  public static final String EXPECTED = StringUtils.lines("0", "0");
+
+  @Test
+  public void test()
+      throws CompilationFailedException, IOException, ExecutionException, NoSuchMethodException {
+    testForJvm().addTestClasspath().run(CLASS).assertSuccessWithOutput(EXPECTED);
+
+    D8TestCompileResult d8Result =
+        testForD8().addProgramClasses(CLASS).setMinApi(AndroidApiLevel.M).release().compile();
+
+    CodeInspector inspector = d8Result.inspector();
+    checkMethodContainsLongSignum(inspector, "fooNoTryCatch");
+    checkMethodContainsLongSignum(inspector, "fooWithTryCatch");
+    // Check the program runs on ART/Dalvik
+    d8Result.run(CLASS).assertSuccessWithOutput(EXPECTED);
+    // Check the program can be dex2oat compiled to arm64. This will diverge without the fixup.
+    d8Result.runDex2Oat().assertSuccess();
+  }
+
+  private void checkMethodContainsLongSignum(CodeInspector inspector, String methodName)
+      throws NoSuchMethodException {
+    MethodSubject method = inspector.method(CLASS.getMethod(methodName, long.class, long.class));
+    Assert.assertTrue(
+        "Did not contain Long.signum workaround in "
+            + methodName
+            + ":\n"
+            + method.getMethod().codeToString(),
+        method
+            .streamInstructions()
+            .anyMatch(
+                i ->
+                    i.isInvoke() && i.getMethod().qualifiedName().equals("java.lang.Long.signum")));
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/regress/b118075510/Regress118075510Test.java b/src/test/java/com/android/tools/r8/regress/b118075510/Regress118075510Test.java
new file mode 100644
index 0000000..cc4dece
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/regress/b118075510/Regress118075510Test.java
@@ -0,0 +1,38 @@
+// Copyright (c) 2018, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.regress.b118075510;
+
+public class Regress118075510Test {
+
+  public static void fooNoTryCatch(long a, long b) {
+    // Call a method on the runner class that will not be on the classpath at runtime.
+    // This causes the optimizing 6.0.1 compiler to delegate to the old quick compiler.
+    if (a == b) Regress118075510Runner.class.getMethods();
+    // The else branch of the conditional here ends up with an invalid previous pointer at its
+    // block header (ie, previous of mul-long (2addr) points to epilogue-end which is self-linked.
+    System.out.println(a < b ? 0 : a * b + b);
+  }
+
+  public static void fooWithTryCatch(long a, long b) {
+    // Call a method on the runner class that will not be on the classpath at runtime.
+    // This causes the optimizing 6.0.1 compiler to delegate to the old quick compiler.
+    if (a == b) Regress118075510Runner.class.getMethods();
+    // The else branch of the conditional here ends up with an invalid previous pointer at its
+    // block header (ie, previous of mul-long (2addr) points to epilogue-end which is self-linked.
+    try {
+      if (a < b) {
+        System.out.println((long) 0);
+      } else {
+        System.out.println(a * b + b);
+      }
+    } catch (RuntimeException e) {
+      e.printStackTrace();
+    }
+  }
+
+  public static void main(String[] args) {
+    fooNoTryCatch(args.length, 456);
+    fooWithTryCatch(456, args.length);
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/regress/b77842465/Regress77842465.java b/src/test/java/com/android/tools/r8/regress/b77842465/Regress77842465.java
index cbc6e1b..3ab3467 100644
--- a/src/test/java/com/android/tools/r8/regress/b77842465/Regress77842465.java
+++ b/src/test/java/com/android/tools/r8/regress/b77842465/Regress77842465.java
@@ -5,29 +5,20 @@
 
 import com.android.tools.r8.AsmTestBase;
 import com.android.tools.r8.CompilationFailedException;
-import com.android.tools.r8.D8;
-import com.android.tools.r8.D8Command;
-import com.android.tools.r8.OutputMode;
-import com.android.tools.r8.ToolHelper;
-import com.android.tools.r8.origin.Origin;
+import com.android.tools.r8.utils.AndroidApiLevel;
 import java.io.IOException;
-import java.nio.file.Path;
 import org.junit.Test;
 
 public class Regress77842465 extends AsmTestBase {
 
   @Test
   public void test() throws CompilationFailedException, IOException {
-
-    Path dexOut = temp.getRoot().toPath().resolve("out.jar");
-    Path oatOut = temp.getRoot().toPath().resolve("out.odex");
-
-    D8.run(D8Command.builder()
-        .addClassProgramData(Regress77842465Dump.dump(), Origin.unknown())
-        .setOutput(dexOut, OutputMode.DexIndexed)
-        .setDisableDesugaring(true)
-        .build());
-
-    ToolHelper.runDex2Oat(dexOut, oatOut);
+    testForD8()
+        .addProgramClassFileData(Regress77842465Dump.dump())
+        .noDesugaring()
+        .setMinApi(AndroidApiLevel.M)
+        .compile()
+        .runDex2Oat()
+        .assertSuccess();
   }
 }
diff --git a/src/test/java/com/android/tools/r8/regress/b78493232/Regress78493232_WithPhi.java b/src/test/java/com/android/tools/r8/regress/b78493232/Regress78493232_WithPhi.java
index 6ee7392..4bd0776 100644
--- a/src/test/java/com/android/tools/r8/regress/b78493232/Regress78493232_WithPhi.java
+++ b/src/test/java/com/android/tools/r8/regress/b78493232/Regress78493232_WithPhi.java
@@ -52,6 +52,7 @@
         case V4_4_4:
         case V7_0_0:
         case V8_1_0:
+        case V9_0_0:
         case DEFAULT:
           assertNotEquals(-1, d8Result.stderr.indexOf("java.lang.VerifyError"));
           assertNotEquals(-1, r8Result.stderr.indexOf("java.lang.VerifyError"));
diff --git a/src/test/java/com/android/tools/r8/shaking/EnclosingMethodTest.java b/src/test/java/com/android/tools/r8/shaking/EnclosingMethodTest.java
index afc319a..a4806f0 100644
--- a/src/test/java/com/android/tools/r8/shaking/EnclosingMethodTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/EnclosingMethodTest.java
@@ -8,6 +8,7 @@
 import com.android.tools.r8.R8TestBuilder;
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.ToolHelper.DexVm;
 import com.android.tools.r8.utils.BooleanUtils;
 import com.google.common.collect.ImmutableList;
 import java.nio.file.Path;
@@ -71,6 +72,9 @@
 
   @Test
   public void testR8() throws Exception {
+    DexVm vm = ToolHelper.getDexVm();
+    assumeTrue("Known to be broken at 5.1.1 and 6.0.1 due to access to fragile EnclosingMethod.",
+        vm.isOlderThanOrEqual(DexVm.ART_4_4_4_HOST) && vm.isNewerThan(DexVm.ART_6_0_1_HOST));
     R8TestBuilder builder = testForR8(backend)
         .addProgramFiles(classPaths)
         .enableProguardTestOptions()
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 {}
+}
diff --git a/src/test/java/com/android/tools/r8/shaking/ifrule/classinlining/IfRuleWithClassInlining.java b/src/test/java/com/android/tools/r8/shaking/ifrule/classinlining/IfRuleWithClassInlining.java
new file mode 100644
index 0000000..caa06d3
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/ifrule/classinlining/IfRuleWithClassInlining.java
@@ -0,0 +1,106 @@
+// 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.ifrule.classinlining;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.CoreMatchers.not;
+import static org.junit.Assert.assertThat;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.utils.BooleanUtils;
+import com.android.tools.r8.utils.StringUtils;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import java.util.List;
+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 IfRuleWithClassInlining extends TestBase {
+
+  private final Backend backend;
+  private final boolean enableClassInlining;
+  private final boolean enableIfRule;
+
+  public IfRuleWithClassInlining(
+      Backend backend, boolean enableClassInlining, boolean enableIfRule) {
+    this.backend = backend;
+    this.enableClassInlining = enableClassInlining;
+    this.enableIfRule = enableIfRule;
+  }
+
+  @Parameters(name = "Backend: {0}, class inlining: {1}, with if rule: {2}")
+  public static List<Object[]> data() {
+    return buildParameters(Backend.values(), BooleanUtils.values(), BooleanUtils.values());
+  }
+
+  @Test
+  public void r8Test() throws Exception {
+    String ifRule =
+        StringUtils.lines(
+            "-if class " + StringBox.Builder.class.getTypeName(),
+            "-keep class " + Unused.class.getTypeName());
+    CodeInspector inspector =
+        testForR8(backend)
+            .addInnerClasses(IfRuleWithClassInlining.class)
+            .addKeepMainRule(TestClass.class)
+            // TODO(b/120061431): Should not be needed for this example.
+            .addKeepRules("-allowaccessmodification")
+            .addKeepRules(enableIfRule ? ifRule : "")
+            .addOptionsModification(options -> options.enableClassInlining = enableClassInlining)
+            .compile()
+            .inspector();
+    if (enableIfRule || !enableClassInlining) {
+      assertThat(inspector.clazz(StringBox.Builder.class), isPresent());
+    } else {
+      assertThat(inspector.clazz(StringBox.Builder.class), not(isPresent()));
+    }
+    if (enableIfRule) {
+      assertThat(inspector.clazz(Unused.class), isPresent());
+    }
+  }
+
+  static class TestClass {
+
+    public static void main(String[] args) {
+      StringBox box = StringBox.builder().setString("Hello world").build();
+      System.out.println(box.getString());
+    }
+  }
+
+  static class StringBox {
+
+    static class Builder {
+
+      private String string = null;
+
+      public Builder setString(String string) {
+        this.string = string;
+        return this;
+      }
+
+      public StringBox build() {
+        return new StringBox(string);
+      }
+    }
+
+    private final String string;
+
+    public StringBox(String string) {
+      this.string = string;
+    }
+
+    public String getString() {
+      return string;
+    }
+
+    public static Builder builder() {
+      return new Builder();
+    }
+  }
+
+  static class Unused {}
+}
diff --git a/src/test/java/com/android/tools/r8/utils/codeinspector/MethodSubject.java b/src/test/java/com/android/tools/r8/utils/codeinspector/MethodSubject.java
index 1e21552..98bb8d0 100644
--- a/src/test/java/com/android/tools/r8/utils/codeinspector/MethodSubject.java
+++ b/src/test/java/com/android/tools/r8/utils/codeinspector/MethodSubject.java
@@ -5,8 +5,10 @@
 package com.android.tools.r8.utils.codeinspector;
 
 import com.android.tools.r8.graph.DexEncodedMethod;
+import com.google.common.collect.Streams;
 import java.util.Iterator;
 import java.util.function.Predicate;
+import java.util.stream.Stream;
 
 public abstract class MethodSubject extends MemberSubject {
 
@@ -40,4 +42,8 @@
   public abstract LineNumberTable getLineNumberTable();
 
   public abstract boolean hasLocalVariableTable();
+
+  public Stream<InstructionSubject> streamInstructions() {
+    return Streams.stream(iterateInstructions());
+  }
 }
diff --git a/tools/archive_logs.py b/tools/archive_logs.py
new file mode 100755
index 0000000..bdae32e
--- /dev/null
+++ b/tools/archive_logs.py
@@ -0,0 +1,11 @@
+#!/usr/bin/env python
+# 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.
+
+# Script for achiving gradle test logs.
+
+import utils
+
+if __name__ == '__main__':
+  utils.archive_failures()
diff --git a/tools/dex2oat.py b/tools/dex2oat.py
index eab424f..1e2cffd 100755
--- a/tools/dex2oat.py
+++ b/tools/dex2oat.py
@@ -16,8 +16,7 @@
   'default',
   '7.0.0',
   '6.0.1',
-  # TODO(b/79191363): Build a boot image for 5.1.1 dex2oat.
-  # '5.1.1',
+  '5.1.1',
 ]
 
 DIRS = {
@@ -34,6 +33,13 @@
   '5.1.1': 'mako',
 }
 
+ARCHS = {
+  'default': 'arm64',
+  '7.0.0': 'arm64',
+  '6.0.1': 'arm64',
+  '5.1.1': 'arm',
+}
+
 def ParseOptions():
   parser = optparse.OptionParser()
   parser.add_option('--version',
@@ -74,15 +80,15 @@
       oatfile = os.path.join(temp, "out.oat")
     base = os.path.join(LINUX_DIR, DIRS[version])
     product = PRODUCTS[version]
+    arch = ARCHS[version]
     cmd = [
       os.path.join(base, 'bin', 'dex2oat'),
-      '--android-root=' + os.path.join(base, 'product', product),
+      '--android-root=' + os.path.join(base, 'product', product, 'system'),
       '--runtime-arg',
       '-Xnorelocate',
-      '--boot-image=' + os.path.join(base, 'product', product, 'system', 'framework', 'boot.art'),
       '--dex-file=' + dexfile,
       '--oat-file=' + oatfile,
-      '--instruction-set=arm64',
+      '--instruction-set=' + arch,
     ]
     env = {"LD_LIBRARY_PATH": os.path.join(base, 'lib')}
     utils.PrintCmd(cmd)
diff --git a/tools/linux/README.art-versions b/tools/linux/README.art-versions
index 1512a64..095872b 100644
--- a/tools/linux/README.art-versions
+++ b/tools/linux/README.art-versions
@@ -42,6 +42,29 @@
   <continue with repo sync as above>
 
 
+art-9.0.0 (Android P)
+---------------------
+Build from branch android-9.0.0_r18.
+
+export BRANCH=android-9.0.0_r18
+mkdir ${BRANCH}
+cd ${BRANCH}
+repo init -u https://android.googlesource.com/platform/manifest -b ${BRANCH}
+repo sync -cq -j24
+source build/envsetup.sh
+lunch aosp_marlin-userdebug
+m -j24
+m -j24 build-art
+m -j24 test-art-host
+
+Collected into tools/linux/art-9.0.0.
+
+  cd <r8 checkout>
+  scripts/update-host-art.sh \
+    --android-checkout /usr/local/ssd/android/${BRANCH} \
+    --art-dir art-9.0.0 \
+    --android-product marlin
+
 art-8.1.0 (Android O MR1)
 -------------------------
 Build from branch android-8.1.0_r51.
@@ -59,6 +82,7 @@
 
 Collected into tools/linux/art-8.1.0.
 
+  cd <r8 checkout>
   scripts/update-host-art.sh \
     --android-checkout /usr/local/ssd/android/${BRANCH} \
     --art-dir art-8.1.0 \
diff --git a/tools/linux/art-5.1.1.tar.gz.sha1 b/tools/linux/art-5.1.1.tar.gz.sha1
index 2b6f07a..d7f86b0 100644
--- a/tools/linux/art-5.1.1.tar.gz.sha1
+++ b/tools/linux/art-5.1.1.tar.gz.sha1
@@ -1 +1 @@
-737072daed9a7cd4ef046b7ea8a60aa7b1b6c65d
\ No newline at end of file
+7c1b10e333a5a028db7f74a989d9edfe168900bf
\ No newline at end of file
diff --git a/tools/linux/art-9.0.0.tar.gz.sha1 b/tools/linux/art-9.0.0.tar.gz.sha1
new file mode 100644
index 0000000..788e039
--- /dev/null
+++ b/tools/linux/art-9.0.0.tar.gz.sha1
@@ -0,0 +1 @@
+bfd3d6f4c7d7245d93eecdcc386b41299266e2d1
\ No newline at end of file
diff --git a/tools/run-jdwp-tests.py b/tools/run-jdwp-tests.py
index db69197..2ef479d 100755
--- a/tools/run-jdwp-tests.py
+++ b/tools/run-jdwp-tests.py
@@ -15,6 +15,7 @@
 
 VERSIONS = [
   'default',
+  '9.0.0',
   '8.1.0',
   '7.0.0',
   '6.0.1',
@@ -101,6 +102,8 @@
     flags.extend(['-Ximage:%s' % IMAGE])
     if version != '5.1.1':
       flags.extend(['-Xcompiler-option', '--debuggable'])
+  if version == '9.0.0':
+    flags.extend(['-XjdwpProvider:internal'])
   return flags
 
 def get_debuggee_flags(version):
diff --git a/tools/test.py b/tools/test.py
index 31b2134..e4433b3 100755
--- a/tools/test.py
+++ b/tools/test.py
@@ -13,13 +13,17 @@
 import subprocess
 import sys
 import utils
-import uuid
 import notify
-import upload_to_x20
 
-
-ALL_ART_VMS = ["default", "8.1.0", "7.0.0", "6.0.1", "5.1.1", "4.4.4", "4.0.4"]
-BUCKET = 'r8-test-results'
+ALL_ART_VMS = [
+    "default",
+    "9.0.0",
+    "8.1.0",
+    "7.0.0",
+    "6.0.1",
+    "5.1.1",
+    "4.4.4",
+    "4.0.4"]
 
 def ParseOptions():
   result = optparse.OptionParser()
@@ -89,15 +93,6 @@
 
   return result.parse_args()
 
-def archive_failures():
-  upload_dir = os.path.join(utils.REPO_ROOT, 'build', 'reports', 'tests')
-  u_dir = uuid.uuid4()
-  destination = 'gs://%s/%s' % (BUCKET, u_dir)
-  utils.upload_dir_to_cloud_storage(upload_dir, destination, is_html=True)
-  url = 'http://storage.googleapis.com/%s/%s/test/index.html' % (BUCKET, u_dir)
-  print 'Test results available at: %s' % url
-  print '@@@STEP_LINK@Test failures@%s@@@' % url
-
 def Main():
   (options, args) = ParseOptions()
   if 'BUILDBOT_BUILDERNAME' in os.environ:
@@ -193,7 +188,7 @@
 
     if return_code != 0:
       if options.archive_failures and os.name != 'nt':
-        archive_failures()
+        utils.archive_failures()
       return return_code
 
   return 0
diff --git a/tools/utils.py b/tools/utils.py
index d28643d..282ddfa 100644
--- a/tools/utils.py
+++ b/tools/utils.py
@@ -12,6 +12,7 @@
 import sys
 import tarfile
 import tempfile
+import uuid
 
 ANDROID_JAR = 'third_party/android_jar/lib-v{api}/android.jar'
 TOOLS_DIR = os.path.abspath(os.path.normpath(os.path.join(__file__, '..')))
@@ -44,6 +45,8 @@
 RT_JAR = os.path.join(REPO_ROOT, 'third_party/openjdk/openjdk-rt-1.8/rt.jar')
 R8LIB_KEEP_RULES = os.path.join(REPO_ROOT, 'src/main/keep.txt')
 
+TEST_RESULT_BUCKET = 'r8-test-results'
+
 def PrintCmd(s):
   if type(s) is list:
     s = ' '.join(s)
@@ -180,6 +183,15 @@
  def __exit__(self, *_):
    shutil.rmtree(self._temp_dir, ignore_errors=True)
 
+def archive_failures():
+  upload_dir = os.path.join(REPO_ROOT, 'build', 'reports', 'tests')
+  u_dir = uuid.uuid4()
+  destination = 'gs://%s/%s' % (TEST_RESULT_BUCKET, u_dir)
+  upload_dir_to_cloud_storage(upload_dir, destination, is_html=True)
+  url = 'http://storage.googleapis.com/%s/%s/test/index.html' % (TEST_RESULT_BUCKET, u_dir)
+  print 'Test results available at: %s' % url
+  print '@@@STEP_LINK@Test failures@%s@@@' % url
+
 class ChangedWorkingDirectory(object):
  def __init__(self, working_directory):
    self._working_directory = working_directory