Merge "Support for keepattributes LineNumberTable and LocalVariableTable."
diff --git a/src/main/java/com/android/tools/r8/ExtractMarker.java b/src/main/java/com/android/tools/r8/ExtractMarker.java
index 6fd04b6..fd85c25 100644
--- a/src/main/java/com/android/tools/r8/ExtractMarker.java
+++ b/src/main/java/com/android/tools/r8/ExtractMarker.java
@@ -26,6 +26,7 @@
 import java.util.Collection;
 import java.util.concurrent.ExecutionException;
 
+@Keep
 public class ExtractMarker {
   public static class VdexOrigin extends Origin {
 
diff --git a/src/main/java/com/android/tools/r8/GenerateMainDexList.java b/src/main/java/com/android/tools/r8/GenerateMainDexList.java
index 43989ff..d28e045 100644
--- a/src/main/java/com/android/tools/r8/GenerateMainDexList.java
+++ b/src/main/java/com/android/tools/r8/GenerateMainDexList.java
@@ -5,6 +5,7 @@
 
 import com.android.tools.r8.dex.ApplicationReader;
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
+import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexApplication;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.GraphLense;
@@ -28,6 +29,7 @@
 import java.util.concurrent.ExecutorService;
 import java.util.stream.Collectors;
 
+@Keep
 public class GenerateMainDexList {
   private final Timing timing = new Timing("maindex");
   private final InternalOptions options;
@@ -41,10 +43,11 @@
     try {
       DexApplication application =
           new ApplicationReader(app, options, timing).read(executor).toDirect();
-      AppInfoWithSubtyping appInfo = new AppInfoWithSubtyping(application);
+      AppView<? extends AppInfoWithSubtyping> appView =
+          new AppView<>(new AppInfoWithSubtyping(application), GraphLense.getIdentityLense());
       RootSet mainDexRootSet =
-          new RootSetBuilder(appInfo, application, options.mainDexKeepRules, options).run(executor);
-      Enqueuer enqueuer = new Enqueuer(appInfo, GraphLense.getIdentityLense(), options, true);
+          new RootSetBuilder(appView, application, options.mainDexKeepRules, options).run(executor);
+      Enqueuer enqueuer = new Enqueuer(appView, options, true);
       AppInfoWithLiveness mainDexAppInfo = enqueuer.traceMainDex(mainDexRootSet, executor, timing);
       // LiveTypes is the result.
       Set<DexType> mainDexClasses =
diff --git a/src/main/java/com/android/tools/r8/PrintSeeds.java b/src/main/java/com/android/tools/r8/PrintSeeds.java
index 78cb75a..4c52b53 100644
--- a/src/main/java/com/android/tools/r8/PrintSeeds.java
+++ b/src/main/java/com/android/tools/r8/PrintSeeds.java
@@ -5,9 +5,11 @@
 
 import com.android.tools.r8.dex.ApplicationReader;
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
+import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexApplication;
 import com.android.tools.r8.graph.GraphLense;
 import com.android.tools.r8.shaking.Enqueuer;
+import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
 import com.android.tools.r8.shaking.RootSetBuilder;
 import com.android.tools.r8.shaking.RootSetBuilder.RootSet;
 import com.android.tools.r8.utils.ExceptionUtils;
@@ -76,21 +78,21 @@
   private static void run(
       R8Command command, Set<String> descriptors, InternalOptions options, ExecutorService executor)
       throws IOException {
+    assert !options.forceProguardCompatibility;
     Timing timing = new Timing("PrintSeeds");
     try {
       DexApplication application =
           new ApplicationReader(command.getInputApp(), options, timing).read(executor).toDirect();
-      AppInfoWithSubtyping appInfo = new AppInfoWithSubtyping(application);
+      AppView<? extends AppInfoWithSubtyping> appView =
+          new AppView<>(new AppInfoWithSubtyping(application), GraphLense.getIdentityLense());
       RootSet rootSet =
           new RootSetBuilder(
-                  appInfo, application, options.proguardConfiguration.getRules(), options)
+                  appView, application, options.proguardConfiguration.getRules(), options)
               .run(executor);
-      Enqueuer enqueuer = new Enqueuer(appInfo, GraphLense.getIdentityLense(), options, false);
-      appInfo = enqueuer.traceApplication(rootSet, executor, timing);
+      Enqueuer enqueuer = new Enqueuer(appView, options);
+      AppInfoWithLiveness appInfo = enqueuer.traceApplication(rootSet, executor, timing);
       RootSetBuilder.writeSeeds(
-          appInfo.withLiveness(),
-          System.out,
-          type -> descriptors.contains(type.toDescriptorString()));
+          appInfo, System.out, type -> descriptors.contains(type.toDescriptorString()));
     } catch (ExecutionException e) {
       throw R8.unwrapExecutionException(e);
     }
diff --git a/src/main/java/com/android/tools/r8/R8.java b/src/main/java/com/android/tools/r8/R8.java
index 8be6306..ec863ee 100644
--- a/src/main/java/com/android/tools/r8/R8.java
+++ b/src/main/java/com/android/tools/r8/R8.java
@@ -275,24 +275,15 @@
         // kotlin metadata annotation is removed.
         computeKotlinInfoForProgramClasses(application, appView.appInfo());
 
-        final ProguardConfiguration.Builder compatibility =
+        ProguardConfiguration.Builder compatibility =
             ProguardConfiguration.builder(application.dexItemFactory, options.reporter);
 
         rootSet =
             new RootSetBuilder(
-                    appView.appInfo(),
-                    application,
-                    options.proguardConfiguration.getRules(),
-                    options)
+                    appView, application, options.proguardConfiguration.getRules(), options)
                 .run(executorService);
 
-        Enqueuer enqueuer =
-            new Enqueuer(
-                appView.appInfo(),
-                appView.graphLense(),
-                options,
-                options.forceProguardCompatibility,
-                compatibility);
+        Enqueuer enqueuer = new Enqueuer(appView, options, compatibility);
         appView.setAppInfo(enqueuer.traceApplication(rootSet, executorService, timing));
         if (options.proguardConfiguration.isPrintSeeds()) {
           ByteArrayOutputStream bytes = new ByteArrayOutputStream();
@@ -416,10 +407,10 @@
 
       if (!options.mainDexKeepRules.isEmpty()) {
         appView.setAppInfo(new AppInfoWithSubtyping(application));
-        Enqueuer enqueuer = new Enqueuer(appView.appInfo(), appView.graphLense(), options, true);
+        Enqueuer enqueuer = new Enqueuer(appView, options, true);
         // Lets find classes which may have code executed before secondary dex files installation.
         RootSet mainDexRootSet =
-            new RootSetBuilder(appView.appInfo(), application, options.mainDexKeepRules, options)
+            new RootSetBuilder(appView, application, options.mainDexKeepRules, options)
                 .run(executorService);
         AppInfoWithLiveness mainDexAppInfo =
             enqueuer.traceMainDex(mainDexRootSet, executorService, timing);
@@ -448,12 +439,7 @@
       if (options.enableTreeShaking || options.enableMinification) {
         timing.begin("Post optimization code stripping");
         try {
-          Enqueuer enqueuer =
-              new Enqueuer(
-                  appView.appInfo(),
-                  appView.graphLense(),
-                  options,
-                  options.forceProguardCompatibility);
+          Enqueuer enqueuer = new Enqueuer(appView, options);
           appView.setAppInfo(enqueuer.traceApplication(rootSet, executorService, timing));
 
           AppView<AppInfoWithLiveness> appViewWithLiveness = appView.withLiveness();
diff --git a/src/main/java/com/android/tools/r8/Version.java b/src/main/java/com/android/tools/r8/Version.java
index 0d4e79d..3dbaa56 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.0-dev";
+  public static final String LABEL = "1.4.2-dev";
 
   private Version() {
   }
diff --git a/src/main/java/com/android/tools/r8/cf/FixedLocalValue.java b/src/main/java/com/android/tools/r8/cf/FixedLocalValue.java
index b9be068..d703c88 100644
--- a/src/main/java/com/android/tools/r8/cf/FixedLocalValue.java
+++ b/src/main/java/com/android/tools/r8/cf/FixedLocalValue.java
@@ -18,7 +18,7 @@
   private final Phi phi;
 
   public FixedLocalValue(Phi phi) {
-    super(phi.getNumber(), phi.outType(), phi.getLocalInfo());
+    super(phi.getNumber(), phi.getTypeLattice(), phi.getLocalInfo());
     this.phi = phi;
   }
 
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 08af875..d640a30 100644
--- a/src/main/java/com/android/tools/r8/cf/TypeVerificationHelper.java
+++ b/src/main/java/com/android/tools/r8/cf/TypeVerificationHelper.java
@@ -68,7 +68,7 @@
   }
 
   private TypeLatticeElement getLatticeElement(DexType type) {
-    return TypeLatticeElement.fromDexType(appInfo, type, true);
+    return TypeLatticeElement.fromDexType(type, appInfo, true);
   }
 
   public Map<Value, DexType> computeVerificationTypes() {
diff --git a/src/main/java/com/android/tools/r8/cf/code/CfConstNumber.java b/src/main/java/com/android/tools/r8/cf/code/CfConstNumber.java
index c24490c..2ea0593 100644
--- a/src/main/java/com/android/tools/r8/cf/code/CfConstNumber.java
+++ b/src/main/java/com/android/tools/r8/cf/code/CfConstNumber.java
@@ -124,6 +124,6 @@
 
   @Override
   public void buildIR(IRBuilder builder, CfState state, CfSourceCode code) {
-    builder.addConst(type, state.push(type).register, value);
+    builder.addConst(type.toTypeLattice(), state.push(type).register, value);
   }
 }
diff --git a/src/main/java/com/android/tools/r8/code/CheckCast.java b/src/main/java/com/android/tools/r8/code/CheckCast.java
index 9416a7b..57151fa 100644
--- a/src/main/java/com/android/tools/r8/code/CheckCast.java
+++ b/src/main/java/com/android/tools/r8/code/CheckCast.java
@@ -38,6 +38,11 @@
   }
 
   @Override
+  public boolean isCheckCast() {
+    return true;
+  }
+
+  @Override
   public void registerUse(UseRegistry registry) {
     registry.registerCheckCast(getType());
   }
diff --git a/src/main/java/com/android/tools/r8/code/Const.java b/src/main/java/com/android/tools/r8/code/Const.java
index 1d8313d..48c1aa9 100644
--- a/src/main/java/com/android/tools/r8/code/Const.java
+++ b/src/main/java/com/android/tools/r8/code/Const.java
@@ -3,8 +3,8 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.code;
 
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.SingleConstant;
-import com.android.tools.r8.ir.code.ValueType;
 import com.android.tools.r8.ir.conversion.IRBuilder;
 import com.android.tools.r8.naming.ClassNameMapper;
 import com.android.tools.r8.utils.StringUtils;
@@ -58,7 +58,8 @@
   @Override
   public void buildIR(IRBuilder builder) {
     int value = decodedValue();
-    ValueType type = value == 0 ? ValueType.INT_OR_FLOAT_OR_NULL : ValueType.INT_OR_FLOAT;
-    builder.addConst(type, AA, value);
+    TypeLatticeElement typeLattice =
+        value == 0 ? TypeLatticeElement.BOTTOM : TypeLatticeElement.SINGLE;
+    builder.addConst(typeLattice, AA, value);
   }
 }
diff --git a/src/main/java/com/android/tools/r8/code/Const16.java b/src/main/java/com/android/tools/r8/code/Const16.java
index 24dae68..c4d46e2 100644
--- a/src/main/java/com/android/tools/r8/code/Const16.java
+++ b/src/main/java/com/android/tools/r8/code/Const16.java
@@ -3,8 +3,8 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.code;
 
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.SingleConstant;
-import com.android.tools.r8.ir.code.ValueType;
 import com.android.tools.r8.ir.conversion.IRBuilder;
 import com.android.tools.r8.naming.ClassNameMapper;
 import com.android.tools.r8.utils.StringUtils;
@@ -52,7 +52,8 @@
   @Override
   public void buildIR(IRBuilder builder) {
     int value = decodedValue();
-    ValueType type = value == 0 ? ValueType.INT_OR_FLOAT_OR_NULL : ValueType.INT_OR_FLOAT;
-    builder.addConst(type, AA, value);
+    TypeLatticeElement typeLattice =
+        value == 0 ? TypeLatticeElement.BOTTOM : TypeLatticeElement.SINGLE;
+    builder.addConst(typeLattice, AA, value);
   }
 }
diff --git a/src/main/java/com/android/tools/r8/code/Const4.java b/src/main/java/com/android/tools/r8/code/Const4.java
index 497a9ed..edfcb28 100644
--- a/src/main/java/com/android/tools/r8/code/Const4.java
+++ b/src/main/java/com/android/tools/r8/code/Const4.java
@@ -3,8 +3,8 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.code;
 
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.SingleConstant;
-import com.android.tools.r8.ir.code.ValueType;
 import com.android.tools.r8.ir.conversion.IRBuilder;
 import com.android.tools.r8.naming.ClassNameMapper;
 import com.android.tools.r8.utils.StringUtils;
@@ -58,7 +58,8 @@
   @Override
   public void buildIR(IRBuilder builder) {
     int value = decodedValue();
-    ValueType type = value == 0 ? ValueType.INT_OR_FLOAT_OR_NULL : ValueType.INT_OR_FLOAT;
-    builder.addConst(type, A, value);
+    TypeLatticeElement typeLattice =
+        value == 0 ? TypeLatticeElement.BOTTOM : TypeLatticeElement.SINGLE;
+    builder.addConst(typeLattice, A, value);
   }
 }
diff --git a/src/main/java/com/android/tools/r8/code/ConstHigh16.java b/src/main/java/com/android/tools/r8/code/ConstHigh16.java
index ecaf61f..70e31c8 100644
--- a/src/main/java/com/android/tools/r8/code/ConstHigh16.java
+++ b/src/main/java/com/android/tools/r8/code/ConstHigh16.java
@@ -3,8 +3,8 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.code;
 
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.SingleConstant;
-import com.android.tools.r8.ir.code.ValueType;
 import com.android.tools.r8.ir.conversion.IRBuilder;
 import com.android.tools.r8.naming.ClassNameMapper;
 import com.android.tools.r8.utils.StringUtils;
@@ -58,7 +58,8 @@
   @Override
   public void buildIR(IRBuilder builder) {
     int value = decodedValue();
-    ValueType type = value == 0 ? ValueType.INT_OR_FLOAT_OR_NULL : ValueType.INT_OR_FLOAT;
-    builder.addConst(type, AA, value);
+    TypeLatticeElement typeLattice =
+        value == 0 ? TypeLatticeElement.BOTTOM : TypeLatticeElement.SINGLE;
+    builder.addConst(typeLattice, AA, value);
   }
 }
diff --git a/src/main/java/com/android/tools/r8/code/ConstString.java b/src/main/java/com/android/tools/r8/code/ConstString.java
index d165de5..ed7847a 100644
--- a/src/main/java/com/android/tools/r8/code/ConstString.java
+++ b/src/main/java/com/android/tools/r8/code/ConstString.java
@@ -45,6 +45,11 @@
   }
 
   @Override
+  public boolean isConstString() {
+    return true;
+  }
+
+  @Override
   public String toString(ClassNameMapper naming) {
     return formatString("v" + AA + ", \"" + BBBB.toString() + "\"");
   }
diff --git a/src/main/java/com/android/tools/r8/code/ConstWide.java b/src/main/java/com/android/tools/r8/code/ConstWide.java
index 509b00b..1820172 100644
--- a/src/main/java/com/android/tools/r8/code/ConstWide.java
+++ b/src/main/java/com/android/tools/r8/code/ConstWide.java
@@ -3,7 +3,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.code;
 
-import com.android.tools.r8.ir.code.ValueType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.WideConstant;
 import com.android.tools.r8.ir.conversion.IRBuilder;
 import com.android.tools.r8.naming.ClassNameMapper;
@@ -57,6 +57,6 @@
 
   @Override
   public void buildIR(IRBuilder builder) {
-    builder.addConst(ValueType.LONG_OR_DOUBLE, AA, decodedValue());
+    builder.addConst(TypeLatticeElement.WIDE, AA, decodedValue());
   }
 }
diff --git a/src/main/java/com/android/tools/r8/code/ConstWide16.java b/src/main/java/com/android/tools/r8/code/ConstWide16.java
index 4b74eb4..ad7e84f 100644
--- a/src/main/java/com/android/tools/r8/code/ConstWide16.java
+++ b/src/main/java/com/android/tools/r8/code/ConstWide16.java
@@ -3,7 +3,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.code;
 
-import com.android.tools.r8.ir.code.ValueType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.WideConstant;
 import com.android.tools.r8.ir.conversion.IRBuilder;
 import com.android.tools.r8.naming.ClassNameMapper;
@@ -57,6 +57,6 @@
 
   @Override
   public void buildIR(IRBuilder builder) {
-    builder.addConst(ValueType.LONG_OR_DOUBLE, AA, decodedValue());
+    builder.addConst(TypeLatticeElement.WIDE, AA, decodedValue());
   }
 }
diff --git a/src/main/java/com/android/tools/r8/code/ConstWide32.java b/src/main/java/com/android/tools/r8/code/ConstWide32.java
index f09fd14..0b75213 100644
--- a/src/main/java/com/android/tools/r8/code/ConstWide32.java
+++ b/src/main/java/com/android/tools/r8/code/ConstWide32.java
@@ -3,7 +3,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.code;
 
-import com.android.tools.r8.ir.code.ValueType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.WideConstant;
 import com.android.tools.r8.ir.conversion.IRBuilder;
 import com.android.tools.r8.naming.ClassNameMapper;
@@ -57,6 +57,6 @@
 
   @Override
   public void buildIR(IRBuilder builder) {
-    builder.addConst(ValueType.LONG_OR_DOUBLE, AA, decodedValue());
+    builder.addConst(TypeLatticeElement.WIDE, AA, decodedValue());
   }
 }
diff --git a/src/main/java/com/android/tools/r8/code/ConstWideHigh16.java b/src/main/java/com/android/tools/r8/code/ConstWideHigh16.java
index 762e2ee..e139b35 100644
--- a/src/main/java/com/android/tools/r8/code/ConstWideHigh16.java
+++ b/src/main/java/com/android/tools/r8/code/ConstWideHigh16.java
@@ -3,7 +3,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.code;
 
-import com.android.tools.r8.ir.code.ValueType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.WideConstant;
 import com.android.tools.r8.ir.conversion.IRBuilder;
 import com.android.tools.r8.naming.ClassNameMapper;
@@ -57,6 +57,6 @@
 
   @Override
   public void buildIR(IRBuilder builder) {
-    builder.addConst(ValueType.LONG_OR_DOUBLE, AA, decodedValue());
+    builder.addConst(TypeLatticeElement.WIDE, AA, decodedValue());
   }
 }
diff --git a/src/main/java/com/android/tools/r8/code/Instruction.java b/src/main/java/com/android/tools/r8/code/Instruction.java
index c8b5154..fbb93ca 100644
--- a/src/main/java/com/android/tools/r8/code/Instruction.java
+++ b/src/main/java/com/android/tools/r8/code/Instruction.java
@@ -122,6 +122,14 @@
     this.offset = offset;
   }
 
+  public boolean isCheckCast() {
+    return false;
+  }
+
+  public boolean isConstString() {
+    return false;
+  }
+
   public boolean isSimpleNop() {
     return !isPayload() && this instanceof Nop;
   }
diff --git a/src/main/java/com/android/tools/r8/code/MoveType.java b/src/main/java/com/android/tools/r8/code/MoveType.java
index a9ff6e0..ac0af87 100644
--- a/src/main/java/com/android/tools/r8/code/MoveType.java
+++ b/src/main/java/com/android/tools/r8/code/MoveType.java
@@ -4,6 +4,7 @@
 package com.android.tools.r8.code;
 
 import com.android.tools.r8.errors.Unreachable;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.ValueType;
 
 public enum  MoveType {
@@ -29,14 +30,14 @@
     }
   }
 
-  public ValueType toValueType() {
+  public TypeLatticeElement toTypeLattice() {
     switch (this) {
       case SINGLE:
-        return ValueType.INT_OR_FLOAT;
+        return TypeLatticeElement.SINGLE;
       case WIDE:
-        return ValueType.LONG_OR_DOUBLE;
+        return TypeLatticeElement.WIDE;
       case OBJECT:
-        return ValueType.OBJECT;
+        return TypeLatticeElement.REFERENCE;
       default:
         throw new Unreachable("Unexpected move type: " + this);
     }
diff --git a/src/main/java/com/android/tools/r8/dexfilemerger/DexFileMerger.java b/src/main/java/com/android/tools/r8/dexfilemerger/DexFileMerger.java
index b5db1ae..7cbf816 100644
--- a/src/main/java/com/android/tools/r8/dexfilemerger/DexFileMerger.java
+++ b/src/main/java/com/android/tools/r8/dexfilemerger/DexFileMerger.java
@@ -73,6 +73,22 @@
       }
       throw new AssertionError("Unknown: " + this);
     }
+
+    public static MultidexStrategy parse(String value) {
+      switch (value) {
+        case "off":
+          return OFF;
+        case "given_shard":
+          return GIVEN_SHARD;
+        case "minimal":
+          return MINIMAL;
+        case "best_effort":
+          return BEST_EFFORT;
+        default:
+          throw new RuntimeException(
+              "Multidex argument must be either 'off', 'given_shard', 'minimal' or 'best_effort'.");
+      }
+    }
   }
 
   private static class Options {
@@ -129,7 +145,7 @@
       }
       string = OptionsParsing.tryParseSingle(context, "--multidex", null);
       if (string != null) {
-        options.multidexMode = MultidexStrategy.valueOf(string.toUpperCase());
+        options.multidexMode = MultidexStrategy.parse(string);
         continue;
       }
       string = OptionsParsing.tryParseSingle(context, "--main-dex-list", null);
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 3d83104..f2cc53f 100644
--- a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
+++ b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
@@ -301,10 +301,21 @@
   }
 
   public IRCode buildInliningIRForTesting(
-      InternalOptions options, ValueNumberGenerator valueNumberGenerator) {
+      InternalOptions options, ValueNumberGenerator valueNumberGenerator, AppInfo appInfo) {
     checkIfObsolete();
     return buildInliningIR(
-        null, GraphLense.getIdentityLense(), options, valueNumberGenerator, null, Origin.unknown());
+        appInfo,
+        GraphLense.getIdentityLense(),
+        options,
+        valueNumberGenerator,
+        null,
+        Origin.unknown());
+  }
+
+  public IRCode buildInliningIRForTesting(
+      InternalOptions options, ValueNumberGenerator valueNumberGenerator) {
+    checkIfObsolete();
+    return buildInliningIRForTesting(options, valueNumberGenerator, null);
   }
 
   public IRCode buildInliningIR(
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 b02222f..7254577 100644
--- a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
+++ b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
@@ -70,12 +70,14 @@
   public static final DexType nullValueType = new DexType(new DexString("NULL"));
 
   public static final DexString unknownTypeName = new DexString("UNKNOWN");
+  public static final DexType unknownType = new DexType(unknownTypeName);
 
   private static final IdentityHashMap<DexItem, DexItem> internalSentinels =
       new IdentityHashMap<>(
           ImmutableMap.of(
               catchAllType, catchAllType,
               nullValueType, nullValueType,
+              unknownType, unknownType,
               unknownTypeName, unknownTypeName));
 
   public DexItemFactory() {
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 c8f2b8c..6b368b3 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
@@ -31,7 +31,7 @@
   }
 
   @Override
-  TypeLatticeElement asNullable() {
+  public TypeLatticeElement asNullable() {
     return isNullable() ? this : new ArrayTypeLatticeElement(type, true);
   }
 
@@ -52,7 +52,7 @@
 
   @Override
   public TypeLatticeElement arrayGet(AppInfo appInfo) {
-    return fromDexType(appInfo, getArrayElementType(appInfo.dexItemFactory), true);
+    return fromDexType(getArrayElementType(appInfo.dexItemFactory), appInfo, true);
   }
 
   @Override
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 81b4488..dba0a2a 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
@@ -14,11 +14,11 @@
   }
 
   @Override
-  TypeLatticeElement asNullable() {
+  public TypeLatticeElement asNullable() {
     return this;
   }
 
-  public static BottomTypeLatticeElement getInstance() {
+  static BottomTypeLatticeElement getInstance() {
     return 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 3efc915..de75d5f 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
@@ -3,7 +3,6 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.analysis.type;
 
-import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.graph.DexType;
 import java.util.Set;
 
@@ -28,7 +27,7 @@
   }
 
   @Override
-  TypeLatticeElement asNullable() {
+  public TypeLatticeElement asNullable() {
     return isNullable() ? this : new ClassTypeLatticeElement(type, true, interfaces);
   }
 
@@ -47,9 +46,4 @@
     return this;
   }
 
-  @Override
-  public TypeLatticeElement arrayGet(AppInfo appInfo) {
-    return objectType(appInfo, true);
-  }
-
 }
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/DoubleTypeLatticeElement.java b/src/main/java/com/android/tools/r8/ir/analysis/type/DoubleTypeLatticeElement.java
index a5f0b18..7273f19 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/type/DoubleTypeLatticeElement.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/DoubleTypeLatticeElement.java
@@ -6,7 +6,7 @@
 public class DoubleTypeLatticeElement extends WideTypeLatticeElement {
   private static final DoubleTypeLatticeElement INSTANCE = new DoubleTypeLatticeElement();
 
-  public static DoubleTypeLatticeElement getInstance() {
+  static DoubleTypeLatticeElement getInstance() {
     return INSTANCE;
   }
 
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/FloatTypeLatticeElement.java b/src/main/java/com/android/tools/r8/ir/analysis/type/FloatTypeLatticeElement.java
index d0e5f48..511d6b9 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/type/FloatTypeLatticeElement.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/FloatTypeLatticeElement.java
@@ -6,7 +6,7 @@
 public class FloatTypeLatticeElement extends SingleTypeLatticeElement {
   private static final FloatTypeLatticeElement INSTANCE = new FloatTypeLatticeElement();
 
-  public static FloatTypeLatticeElement getInstance() {
+  static FloatTypeLatticeElement getInstance() {
     return INSTANCE;
   }
 
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/IntTypeLatticeElement.java b/src/main/java/com/android/tools/r8/ir/analysis/type/IntTypeLatticeElement.java
index 8b71446..02594a4 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/type/IntTypeLatticeElement.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/IntTypeLatticeElement.java
@@ -6,7 +6,7 @@
 public class IntTypeLatticeElement extends SingleTypeLatticeElement {
   private static final IntTypeLatticeElement INSTANCE = new IntTypeLatticeElement();
 
-  public static IntTypeLatticeElement getInstance() {
+  static IntTypeLatticeElement getInstance() {
     return INSTANCE;
   }
 
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/LongTypeLatticeElement.java b/src/main/java/com/android/tools/r8/ir/analysis/type/LongTypeLatticeElement.java
index 92b3e3d..e60eaa1 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/type/LongTypeLatticeElement.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/LongTypeLatticeElement.java
@@ -6,7 +6,7 @@
 public class LongTypeLatticeElement extends WideTypeLatticeElement {
   private static final LongTypeLatticeElement INSTANCE = new LongTypeLatticeElement();
 
-  public static LongTypeLatticeElement getInstance() {
+  static LongTypeLatticeElement getInstance() {
     return INSTANCE;
   }
 
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/NullLatticeElement.java b/src/main/java/com/android/tools/r8/ir/analysis/type/NullLatticeElement.java
new file mode 100644
index 0000000..caad0a2
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/NullLatticeElement.java
@@ -0,0 +1,65 @@
+// 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;
+
+/**
+ * Encodes the following lattice.
+ *
+ * <pre>
+ *          MAYBE NULL
+ *          /        \
+ *   DEFINITELY     DEFINITELY
+ *      NULL         NOT NULL
+ *          \        /
+ *            BOTTOM
+ * </pre>
+ */
+public class NullLatticeElement {
+
+  private static final NullLatticeElement BOTTOM = new NullLatticeElement();
+  private static final NullLatticeElement DEFINITELY_NULL = new NullLatticeElement();
+  private static final NullLatticeElement DEFINITELY_NOT_NULL = new NullLatticeElement();
+  private static final NullLatticeElement MAYBE_NULL = new NullLatticeElement();
+
+  private NullLatticeElement() {}
+
+  public boolean isDefinitelyNull() {
+    return this == DEFINITELY_NULL;
+  }
+
+  public boolean isDefinitelyNotNull() {
+    return this == DEFINITELY_NOT_NULL;
+  }
+
+  public NullLatticeElement leastUpperBound(NullLatticeElement other) {
+    if (this == BOTTOM) {
+      return other;
+    }
+    if (this == other || other == BOTTOM) {
+      return this;
+    }
+    return MAYBE_NULL;
+  }
+
+  public boolean lessThanOrEqual(NullLatticeElement other) {
+    return leastUpperBound(other) == other;
+  }
+
+  static NullLatticeElement bottom() {
+    return BOTTOM;
+  }
+
+  static NullLatticeElement definitelyNull() {
+    return DEFINITELY_NULL;
+  }
+
+  static NullLatticeElement definitelyNotNull() {
+    return DEFINITELY_NOT_NULL;
+  }
+
+  static NullLatticeElement maybeNull() {
+    return MAYBE_NULL;
+  }
+}
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 2eb732d..53c67e4 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
@@ -18,8 +18,8 @@
   }
 
   @Override
-  TypeLatticeElement asNullable() {
-    return TopTypeLatticeElement.getInstance();
+  public TypeLatticeElement asNullable() {
+    return TypeLatticeElement.TOP;
   }
 
   @Override
@@ -44,13 +44,13 @@
       case 'S':
       case 'C':
       case 'I':
-        return IntTypeLatticeElement.getInstance();
+        return TypeLatticeElement.INT;
       case 'F':
-        return FloatTypeLatticeElement.getInstance();
+        return TypeLatticeElement.FLOAT;
       case 'J':
-        return LongTypeLatticeElement.getInstance();
+        return TypeLatticeElement.LONG;
       case 'D':
-        return DoubleTypeLatticeElement.getInstance();
+        return TypeLatticeElement.DOUBLE;
       case 'V':
         throw new InternalCompilerError("No value type for void type.");
       default:
@@ -64,13 +64,13 @@
       case CHAR:
       case SHORT:
       case INT:
-        return IntTypeLatticeElement.getInstance();
+        return TypeLatticeElement.INT;
       case FLOAT:
-        return FloatTypeLatticeElement.getInstance();
+        return TypeLatticeElement.FLOAT;
       case LONG:
-        return LongTypeLatticeElement.getInstance();
+        return TypeLatticeElement.LONG;
       case DOUBLE:
-        return DoubleTypeLatticeElement.getInstance();
+        return TypeLatticeElement.DOUBLE;
       default:
         throw new Unreachable("Invalid numeric type '" + numericType + "'");
     }
@@ -83,21 +83,21 @@
     }
     if (t1.isSingle()) {
       if (t2.isSingle()) {
-        return SingleTypeLatticeElement.getInstance();
+        return TypeLatticeElement.SINGLE;
       }
       assert t2.isWide();
-      return TopTypeLatticeElement.getInstance();
+      return TypeLatticeElement.TOP;
     }
     assert t1.isWide();
     if (t2.isWide()) {
-      return WideTypeLatticeElement.getInstance();
+      return TypeLatticeElement.WIDE;
     }
     assert t2.isSingle();
-    return TopTypeLatticeElement.getInstance();
+    return TypeLatticeElement.TOP;
   }
 
   public static TypeLatticeElement meet(TypeLatticeElement t1, TypeLatticeElement t2) {
-    // TODO(b/72693244): !t1.isReference() && !t2.isReference();
+    assert !t1.isReference() && !t2.isReference();
     // TODO(b/72693244): propagate constraints backward, e.g.,
     //   vz <- add vx(1, INT) vy(0, INT_OR_FLOAT_OR_NULL)
     if (t1 == t2) {
@@ -125,7 +125,7 @@
         return t2;
       }
     }
-    return BottomTypeLatticeElement.getInstance();
+    return TypeLatticeElement.BOTTOM;
   }
 
 }
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 f700b15..ef36c4e 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
@@ -12,8 +12,10 @@
 import java.util.stream.Collectors;
 
 public class ReferenceTypeLatticeElement extends TypeLatticeElement {
-  private static final ReferenceTypeLatticeElement NULL =
+  private static final ReferenceTypeLatticeElement NULL_INSTANCE =
       new ReferenceTypeLatticeElement(DexItemFactory.nullValueType, true);
+  private static final ReferenceTypeLatticeElement REFERENCE_INSTANCE =
+      new ReferenceTypeLatticeElement(DexItemFactory.unknownType, true);
 
   final DexType type;
   final Set<DexType> interfaces;
@@ -28,8 +30,12 @@
     this.interfaces = Collections.unmodifiableSet(interfaces);
   }
 
-  public static ReferenceTypeLatticeElement getNullTypeLatticeElement() {
-    return NULL;
+  static ReferenceTypeLatticeElement getNullTypeLatticeElement() {
+    return NULL_INSTANCE;
+  }
+
+  static ReferenceTypeLatticeElement getReferenceTypeLatticeElement() {
+    return REFERENCE_INSTANCE;
   }
 
   @Override
@@ -38,8 +44,13 @@
   }
 
   @Override
-  TypeLatticeElement asNullable() {
-    assert isNull();
+  public boolean isReferenceInstance() {
+    return type == DexItemFactory.unknownType;
+  }
+
+  @Override
+  public TypeLatticeElement asNullable() {
+    assert isNull() || isReferenceInstance();
     return this;
   }
 
@@ -50,8 +61,7 @@
 
   @Override
   public TypeLatticeElement arrayGet(AppInfo appInfo) {
-    assert isNull();
-    return this;
+    return isNull() ? this : BOTTOM;
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/SingleTypeLatticeElement.java b/src/main/java/com/android/tools/r8/ir/analysis/type/SingleTypeLatticeElement.java
index 0128b5e..2f719df 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/type/SingleTypeLatticeElement.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/SingleTypeLatticeElement.java
@@ -13,7 +13,7 @@
     super();
   }
 
-  public static SingleTypeLatticeElement getInstance() {
+  static SingleTypeLatticeElement getInstance() {
     return SINGLE_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 eeb22d3..7aba6dc 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
@@ -14,11 +14,11 @@
   }
 
   @Override
-  TypeLatticeElement asNullable() {
+  public TypeLatticeElement asNullable() {
     return this;
   }
 
-  public static TopTypeLatticeElement getInstance() {
+  static TopTypeLatticeElement getInstance() {
     return INSTANCE;
   }
 
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/TypeAnalysis.java b/src/main/java/com/android/tools/r8/ir/analysis/type/TypeAnalysis.java
index ffbd3fd..b8988c1 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/type/TypeAnalysis.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/TypeAnalysis.java
@@ -84,12 +84,12 @@
         TypeLatticeElement derived;
         if (argumentsSeen < 0) {
           // Receiver
-          derived = fromDexType(appInfo, encodedMethod.method.holder,
+          derived = fromDexType(encodedMethod.method.holder, appInfo,
               // Now we try inlining even when the receiver could be null.
               encodedMethod != context);
         } else {
           DexType argType = encodedMethod.method.proto.parameters.values[argumentsSeen];
-          derived = fromDexType(appInfo, argType, true);
+          derived = fromDexType(argType, appInfo, true);
         }
         argumentsSeen++;
         updateTypeOfValue(outValue, derived);
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 f0ae028..a09039c 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
@@ -8,6 +8,7 @@
 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.MemberType;
 import com.android.tools.r8.ir.code.Value;
 import com.google.common.collect.ImmutableSet;
 import java.util.ArrayDeque;
@@ -22,7 +23,21 @@
 /**
  * The base abstraction of lattice elements for local type analysis.
  */
-abstract public class TypeLatticeElement {
+public abstract class TypeLatticeElement {
+  public static final BottomTypeLatticeElement BOTTOM = BottomTypeLatticeElement.getInstance();
+  public static final TopTypeLatticeElement TOP = TopTypeLatticeElement.getInstance();
+  public static final IntTypeLatticeElement INT = IntTypeLatticeElement.getInstance();
+  public static final FloatTypeLatticeElement FLOAT = FloatTypeLatticeElement.getInstance();
+  public static final SingleTypeLatticeElement SINGLE = SingleTypeLatticeElement.getInstance();
+  public static final LongTypeLatticeElement LONG = LongTypeLatticeElement.getInstance();
+  public static final DoubleTypeLatticeElement DOUBLE = DoubleTypeLatticeElement.getInstance();
+  public static final WideTypeLatticeElement WIDE = WideTypeLatticeElement.getInstance();
+  public static final ReferenceTypeLatticeElement NULL =
+      ReferenceTypeLatticeElement.getNullTypeLatticeElement();
+  public static final ReferenceTypeLatticeElement REFERENCE =
+      ReferenceTypeLatticeElement.getReferenceTypeLatticeElement();
+
+  // TODO(b/72693244): Switch to NullLatticeElement.
   private final boolean isNullable;
 
   TypeLatticeElement(boolean isNullable) {
@@ -33,8 +48,14 @@
     return isNullable;
   }
 
-  public boolean isNull() {
-    return false;
+  public NullLatticeElement nullElement() {
+    if (isNull()) {
+      return NullLatticeElement.definitelyNull();
+    }
+    if (!isNullable()) {
+      return NullLatticeElement.definitelyNotNull();
+    }
+    return NullLatticeElement.maybeNull();
   }
 
   /**
@@ -42,7 +63,7 @@
    *
    * @return {@link TypeLatticeElement} a result of joining with null.
    */
-  abstract TypeLatticeElement asNullable();
+  public abstract TypeLatticeElement asNullable();
 
   /**
    * Defines how to switch to non-nullable lattice element.
@@ -50,7 +71,7 @@
    * @return {@link TypeLatticeElement} a similar lattice element with nullable flag flipped.
    */
   public TypeLatticeElement asNonNullable() {
-    return BottomTypeLatticeElement.getInstance();
+    return BOTTOM;
   }
 
   String isNullableString() {
@@ -74,7 +95,7 @@
       return l1;
     }
     if (l1.isTop() || l2.isTop()) {
-      return TopTypeLatticeElement.getInstance();
+      return TOP;
     }
     if (l1.isNull()) {
       return l2.asNullable();
@@ -86,16 +107,25 @@
       return l2.isPrimitive()
           ? PrimitiveTypeLatticeElement.join(
               l1.asPrimitiveTypeLatticeElement(), l2.asPrimitiveTypeLatticeElement())
-          : TopTypeLatticeElement.getInstance();
+          : TOP;
     }
     if (l2.isPrimitive()) {
       // By the above case, !(l1.isPrimitive())
-      return TopTypeLatticeElement.getInstance();
+      return TOP;
     }
-    // From now on, l1 and l2 are reference types, i.e., either ArrayType or ClassType.
+    // From now on, l1 and l2 are reference types, but might be imprecise yet.
+    assert l1.isReference() && l2.isReference();
+    if (!l1.isPreciseType() || !l2.isPreciseType()) {
+      if (l1.isReferenceInstance()) {
+        return l1;
+      }
+      assert l2.isReferenceInstance();
+      return l2;
+    }
+    // From now on, l1 and l2 are precise reference types, i.e., either ArrayType or ClassType.
     boolean isNullable = l1.isNullable() || l2.isNullable();
     if (l1.getClass() != l2.getClass()) {
-      return objectType(appInfo, isNullable);
+      return objectClassType(appInfo, isNullable);
     }
     // From now on, l1.getClass() == l2.getClass()
     if (l1.isArrayType()) {
@@ -122,7 +152,7 @@
       assert a1BaseReferenceType.isClassType() && a2BaseReferenceType.isClassType();
       // If any nestings hit zero object is the join.
       if (a1Nesting == 0 || a2Nesting == 0) {
-        return objectType(appInfo, isNullable);
+        return objectClassType(appInfo, isNullable);
       }
       // If the nestings differ the join is the smallest nesting level.
       if (a1Nesting != a2Nesting) {
@@ -238,7 +268,7 @@
 
   public static TypeLatticeElement join(
       AppInfo appInfo, Stream<DexType> types, boolean isNullable) {
-    return join(appInfo, types.map(t -> fromDexType(appInfo, t, isNullable)));
+    return join(appInfo, types.map(t -> fromDexType(t, appInfo, isNullable)));
   }
 
   /**
@@ -350,7 +380,20 @@
         || isDouble();
   }
 
-  static ClassTypeLatticeElement objectType(AppInfo appInfo, boolean isNullable) {
+  public boolean isNull() {
+    return false;
+  }
+
+  public boolean isReferenceInstance() {
+    return false;
+  }
+
+  public int requiredRegisters() {
+    assert !isBottom() && !isTop();
+    return isWide() ? 2 : 1;
+  }
+
+  public static ClassTypeLatticeElement objectClassType(AppInfo appInfo, boolean isNullable) {
     return new ClassTypeLatticeElement(appInfo.dexItemFactory.objectType, isNullable);
   }
 
@@ -360,9 +403,17 @@
         isNullable);
   }
 
-  public static TypeLatticeElement fromDexType(AppInfo appInfo, DexType type, boolean isNullable) {
+  public static TypeLatticeElement classClassType(AppInfo appInfo) {
+    return fromDexType(appInfo.dexItemFactory.classType, appInfo, false);
+  }
+
+  public static TypeLatticeElement stringClassType(AppInfo appInfo) {
+    return fromDexType(appInfo.dexItemFactory.stringType, appInfo, false);
+  }
+
+  public static TypeLatticeElement fromDexType(DexType type, AppInfo appInfo, boolean isNullable) {
     if (type == DexItemFactory.nullValueType) {
-      return ReferenceTypeLatticeElement.getNullTypeLatticeElement();
+      return NULL;
     }
     if (type.isPrimitiveType()) {
       return PrimitiveTypeLatticeElement.fromDexType(type);
@@ -379,16 +430,60 @@
     return new ArrayTypeLatticeElement(type, isNullable);
   }
 
+  public static TypeLatticeElement fromDexType(DexType type) {
+    if (type == DexItemFactory.nullValueType) {
+      return NULL;
+    }
+    return fromTypeDescriptorChar((char) type.descriptor.content[0]);
+  }
+
+  public static TypeLatticeElement fromTypeDescriptorChar(char descriptor) {
+    switch (descriptor) {
+      case 'L':
+        // TODO(jsjeon): class type with Object?
+      case '[':
+        // TODO(jsjeon): array type with Object?
+        return REFERENCE;
+      default:
+        return PrimitiveTypeLatticeElement.fromTypeDescriptorChar(descriptor);
+    }
+  }
+
+  public static TypeLatticeElement fromMemberType(MemberType type) {
+    switch (type) {
+      case BOOLEAN:
+      case BYTE:
+      case CHAR:
+      case SHORT:
+      case INT:
+        return INT;
+      case FLOAT:
+        return FLOAT;
+      case INT_OR_FLOAT:
+        return SINGLE;
+      case LONG:
+        return LONG;
+      case DOUBLE:
+        return DOUBLE;
+      case LONG_OR_DOUBLE:
+        return WIDE;
+      case OBJECT:
+        return REFERENCE;
+      default:
+        throw new Unreachable("Unexpected member type: " + type);
+    }
+  }
+
   public static TypeLatticeElement newArray(DexType arrayType, boolean isNullable) {
     return new ArrayTypeLatticeElement(arrayType, isNullable);
   }
 
   public TypeLatticeElement arrayGet(AppInfo appInfo) {
-    return BottomTypeLatticeElement.getInstance();
+    return BOTTOM;
   }
 
   public TypeLatticeElement checkCast(AppInfo appInfo, DexType castType) {
-    TypeLatticeElement castTypeLattice = fromDexType(appInfo, castType, isNullable());
+    TypeLatticeElement castTypeLattice = fromDexType(castType, appInfo, isNullable());
     if (lessThanOrEqual(appInfo, this, castTypeLattice)) {
       return this;
     }
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/WideTypeLatticeElement.java b/src/main/java/com/android/tools/r8/ir/analysis/type/WideTypeLatticeElement.java
index ec0b846..53c0da1 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/type/WideTypeLatticeElement.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/WideTypeLatticeElement.java
@@ -13,7 +13,7 @@
     super();
   }
 
-  public static WideTypeLatticeElement getInstance() {
+  static WideTypeLatticeElement getInstance() {
     return WIDE_INSTANCE;
   }
 
diff --git a/src/main/java/com/android/tools/r8/ir/code/ArithmeticBinop.java b/src/main/java/com/android/tools/r8/ir/code/ArithmeticBinop.java
index 296fba5..cc154e9 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ArithmeticBinop.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ArithmeticBinop.java
@@ -9,6 +9,7 @@
 import com.android.tools.r8.ir.analysis.constant.Bottom;
 import com.android.tools.r8.ir.analysis.constant.ConstLatticeElement;
 import com.android.tools.r8.ir.analysis.constant.LatticeElement;
+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 java.util.function.Function;
@@ -139,20 +140,20 @@
       ConstNumber newConst;
       if (type == NumericType.INT) {
         int result = foldIntegers(leftConst.getIntValue(), rightConst.getIntValue());
-        Value value = code.createValue(ValueType.INT, getLocalInfo());
+        Value value = code.createValue(TypeLatticeElement.INT, getLocalInfo());
         newConst = new ConstNumber(value, result);
       } else if (type == NumericType.LONG) {
         long result = foldLongs(leftConst.getLongValue(), rightConst.getLongValue());
-        Value value = code.createValue(ValueType.LONG, getLocalInfo());
+        Value value = code.createValue(TypeLatticeElement.LONG, getLocalInfo());
         newConst = new ConstNumber(value, result);
       } else if (type == NumericType.FLOAT) {
         float result = foldFloat(leftConst.getFloatValue(), rightConst.getFloatValue());
-        Value value = code.createValue(ValueType.FLOAT, getLocalInfo());
+        Value value = code.createValue(TypeLatticeElement.FLOAT, getLocalInfo());
         newConst = new ConstNumber(value, Float.floatToIntBits(result));
       } else {
         assert type == NumericType.DOUBLE;
         double result = foldDouble(leftConst.getDoubleValue(), rightConst.getDoubleValue());
-        Value value = code.createValue(ValueType.DOUBLE, getLocalInfo());
+        Value value = code.createValue(TypeLatticeElement.DOUBLE, getLocalInfo());
         newConst = new ConstNumber(value, Double.doubleToLongBits(result));
       }
       return new ConstLatticeElement(newConst);
diff --git a/src/main/java/com/android/tools/r8/ir/code/ArrayLength.java b/src/main/java/com/android/tools/r8/ir/code/ArrayLength.java
index 0c8f214..e222eaa 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ArrayLength.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ArrayLength.java
@@ -9,7 +9,6 @@
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.graph.DexType;
-import com.android.tools.r8.ir.analysis.type.IntTypeLatticeElement;
 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;
@@ -107,7 +106,7 @@
 
   @Override
   public TypeLatticeElement evaluate(AppInfo appInfo) {
-    return IntTypeLatticeElement.getInstance();
+    return TypeLatticeElement.INT;
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java b/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
index 8a2c169..a8c9b2f 100644
--- a/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
+++ b/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
@@ -6,11 +6,13 @@
 import static com.android.tools.r8.ir.code.IRCode.INSTRUCTION_NUMBER_DELTA;
 
 import com.android.tools.r8.errors.CompilationError;
+import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.graph.DebugLocalInfo;
 import com.android.tools.r8.graph.DebugLocalInfo.PrintLevel;
 import com.android.tools.r8.graph.DexItemFactory;
 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.Phi.RegisterReadType;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.conversion.IRBuilder;
@@ -68,6 +70,11 @@
     return true;
   }
 
+  public boolean verifyTypes(AppInfo appInfo) {
+    assert instructions.stream().allMatch(instruction -> instruction.verifyTypes(appInfo));
+    return true;
+  }
+
   public void setLocalsAtEntry(Int2ReferenceMap<DebugLocalInfo> localsAtEntry) {
     this.localsAtEntry = localsAtEntry;
   }
@@ -1174,10 +1181,11 @@
     return block;
   }
 
-  public static BasicBlock createRethrowBlock(IRCode code, Position position) {
+  public static BasicBlock createRethrowBlock(
+      IRCode code, Position position, TypeLatticeElement guardTypeLattice) {
     BasicBlock block = new BasicBlock();
-    MoveException moveException =
-        new MoveException(new Value(code.valueNumberGenerator.next(), ValueType.OBJECT, null));
+    MoveException moveException = new MoveException(
+        new Value(code.valueNumberGenerator.next(), guardTypeLattice, null));
     moveException.setPosition(position);
     Throw throwInstruction = new Throw(moveException.outValue);
     throwInstruction.setPosition(position);
@@ -1438,11 +1446,13 @@
       Consumer<BasicBlock> onNewBlock) {
     List<BasicBlock> predecessors = this.getPredecessors();
     boolean hasMoveException = entry().isMoveException();
+    TypeLatticeElement exceptionTypeLattice = null;
     MoveException move = null;
     Position position = entry().getPosition();
     if (hasMoveException) {
       // Remove the move-exception instruction.
       move = entry().asMoveException();
+      exceptionTypeLattice = move.outValue().getTypeLattice();
       assert move.getDebugValues().isEmpty();
       getInstructions().remove(0);
     }
@@ -1458,7 +1468,10 @@
       newBlock.setNumber(nextBlockNumber++);
       newPredecessors.add(newBlock);
       if (hasMoveException) {
-        Value value = new Value(valueNumberGenerator.next(), ValueType.OBJECT, move.getLocalInfo());
+        Value value = new Value(
+            valueNumberGenerator.next(),
+            exceptionTypeLattice,
+            move.getLocalInfo());
         values.add(value);
         MoveException newMove = new MoveException(value);
         newBlock.add(newMove);
@@ -1483,7 +1496,7 @@
           new Phi(
               valueNumberGenerator.next(),
               this,
-              ValueType.OBJECT,
+              exceptionTypeLattice,
               move.getLocalInfo(),
               RegisterReadType.NORMAL);
       phi.addOperands(values);
diff --git a/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionIterator.java b/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionIterator.java
index fbbe2fd..7caaff9 100644
--- a/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionIterator.java
+++ b/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionIterator.java
@@ -7,6 +7,7 @@
 import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.ir.analysis.type.TypeAnalysis;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.Phi.RegisterReadType;
 import com.android.tools.r8.utils.IteratorUtils;
 import com.google.common.collect.ImmutableList;
@@ -363,8 +364,11 @@
 
     int i = 0;
     if (downcast != null) {
+      Value receiver = invoke.inValues().get(0);
+      TypeLatticeElement castTypeLattice = TypeLatticeElement.fromDexType(
+          downcast, appInfo, receiver.getTypeLattice().isNullable());
       CheckCast castInstruction =
-          new CheckCast(code.createValue(ValueType.OBJECT), invoke.inValues().get(0), downcast);
+          new CheckCast(code.createValue(castTypeLattice), receiver, downcast);
       castInstruction.setPosition(invoke.getPosition());
 
       // Splice in the check cast operation.
@@ -544,7 +548,7 @@
             new Phi(
                 code.valueNumberGenerator.next(),
                 newExitBlock,
-                returnType,
+                returnType.toTypeLattice(),
                 null,
                 RegisterReadType.NORMAL);
         phi.addOperands(operands);
diff --git a/src/main/java/com/android/tools/r8/ir/code/CheckCast.java b/src/main/java/com/android/tools/r8/ir/code/CheckCast.java
index 4c1824b..8d461bd 100644
--- a/src/main/java/com/android/tools/r8/ir/code/CheckCast.java
+++ b/src/main/java/com/android/tools/r8/ir/code/CheckCast.java
@@ -123,6 +123,47 @@
   }
 
   @Override
+  public boolean verifyTypes(AppInfo appInfo) {
+    TypeLatticeElement inType = object().getTypeLattice();
+
+    // TODO(b/72693244): There should never be a value with imprecise type lattice.
+    if (!inType.isPreciseType()) {
+      return true;
+    }
+
+    TypeLatticeElement outType = outValue().getTypeLattice();
+    TypeLatticeElement castType =
+        TypeLatticeElement.fromDexType(getType(), appInfo, inType.isNullable());
+
+    if (TypeLatticeElement.lessThanOrEqual(appInfo, inType, castType)) {
+      // Cast can be removed. Check that it is sound to replace all users of the out-value by the
+      // in-value.
+      assert TypeLatticeElement.lessThanOrEqual(appInfo, inType, outType);
+
+      // TODO(b/72693244): Consider checking equivalence. This requires that the types are always
+      // as precise as possible, though, meaning that almost all changes to the IR must be followed
+      // by a fix-point analysis.
+      // assert outType.equals(inType);
+    } else {
+      // We don't have enough information to remove the cast. Check that the out-value does not
+      // have a more precise type than the cast-type.
+      assert castType.asNullable().equals(outType.asNullable());
+
+      // Check soundness of null information.
+      assert inType.nullElement().lessThanOrEqual(outType.nullElement());
+
+      // Since we cannot remove the cast the in-value must be different from null.
+      assert !inType.isNull();
+
+      // TODO(b/72693244): Consider checking equivalence. This requires that the types are always
+      // as precise as possible, though, meaning that almost all changes to the IR must be followed
+      // by a fix-point analysis.
+      // assert outType.equals(castType);
+    }
+    return true;
+  }
+
+  @Override
   public void insertLoadAndStores(InstructionListIterator it, LoadStoreHelper helper) {
     helper.loadInValues(this, it);
     helper.storeOutValue(this, it);
diff --git a/src/main/java/com/android/tools/r8/ir/code/Cmp.java b/src/main/java/com/android/tools/r8/ir/code/Cmp.java
index 239e404..4c2529d 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Cmp.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Cmp.java
@@ -11,9 +11,11 @@
 import com.android.tools.r8.code.CmplFloat;
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.errors.Unreachable;
+import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.ir.analysis.constant.Bottom;
 import com.android.tools.r8.ir.analysis.constant.ConstLatticeElement;
 import com.android.tools.r8.ir.analysis.constant.LatticeElement;
+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.utils.LongInterval;
@@ -179,7 +181,7 @@
           result = (int) Math.signum(left - right);
         }
       }
-      Value value = code.createValue(ValueType.INT, getLocalInfo());
+      Value value = code.createValue(TypeLatticeElement.INT, getLocalInfo());
       ConstNumber newConst = new ConstNumber(value, result);
       return new ConstLatticeElement(newConst);
     } else if (leftLattice.isValueRange() && rightLattice.isConst()) {
@@ -207,7 +209,7 @@
       return Bottom.getInstance();
     }
     int result = Integer.signum(Long.compare(leftRange.getMin(), rightRange.getMin()));
-    Value value = code.createValue(ValueType.INT, getLocalInfo());
+    Value value = code.createValue(TypeLatticeElement.INT, getLocalInfo());
     ConstNumber newConst = new ConstNumber(value, result);
     return new ConstLatticeElement(newConst);
   }
@@ -226,4 +228,10 @@
   public void buildCf(CfBuilder builder) {
     builder.add(new CfCmp(bias, type));
   }
+
+  @Override
+  public TypeLatticeElement evaluate(AppInfo appInfo) {
+    return TypeLatticeElement.INT;
+  }
+
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/ConstClass.java b/src/main/java/com/android/tools/r8/ir/code/ConstClass.java
index 2da242e..401656c 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ConstClass.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ConstClass.java
@@ -105,7 +105,7 @@
 
   @Override
   public TypeLatticeElement evaluate(AppInfo appInfo) {
-    return TypeLatticeElement.fromDexType(appInfo, appInfo.dexItemFactory.classType, false);
+    return TypeLatticeElement.fromDexType(appInfo.dexItemFactory.classType, appInfo, false);
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/ir/code/ConstMethodHandle.java b/src/main/java/com/android/tools/r8/ir/code/ConstMethodHandle.java
index b319dbb..ffc4359 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ConstMethodHandle.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ConstMethodHandle.java
@@ -91,7 +91,7 @@
 
   @Override
   public TypeLatticeElement evaluate(AppInfo appInfo) {
-    return TypeLatticeElement.fromDexType(appInfo, appInfo.dexItemFactory.methodHandleType, false);
+    return TypeLatticeElement.fromDexType(appInfo.dexItemFactory.methodHandleType, appInfo, false);
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/ir/code/ConstMethodType.java b/src/main/java/com/android/tools/r8/ir/code/ConstMethodType.java
index 4159c31..81d7b28 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ConstMethodType.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ConstMethodType.java
@@ -91,7 +91,7 @@
 
   @Override
   public TypeLatticeElement evaluate(AppInfo appInfo) {
-    return TypeLatticeElement.fromDexType(appInfo, appInfo.dexItemFactory.methodTypeType, false);
+    return TypeLatticeElement.fromDexType(appInfo.dexItemFactory.methodTypeType, appInfo, false);
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/ir/code/ConstNumber.java b/src/main/java/com/android/tools/r8/ir/code/ConstNumber.java
index 73cf1c2..fa15046 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ConstNumber.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ConstNumber.java
@@ -21,15 +21,7 @@
 import com.android.tools.r8.ir.analysis.constant.Bottom;
 import com.android.tools.r8.ir.analysis.constant.ConstLatticeElement;
 import com.android.tools.r8.ir.analysis.constant.LatticeElement;
-import com.android.tools.r8.ir.analysis.type.BottomTypeLatticeElement;
-import com.android.tools.r8.ir.analysis.type.DoubleTypeLatticeElement;
-import com.android.tools.r8.ir.analysis.type.FloatTypeLatticeElement;
-import com.android.tools.r8.ir.analysis.type.IntTypeLatticeElement;
-import com.android.tools.r8.ir.analysis.type.LongTypeLatticeElement;
-import com.android.tools.r8.ir.analysis.type.ReferenceTypeLatticeElement;
-import com.android.tools.r8.ir.analysis.type.SingleTypeLatticeElement;
 import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
-import com.android.tools.r8.ir.analysis.type.WideTypeLatticeElement;
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.utils.NumberUtils;
@@ -49,8 +41,10 @@
   }
 
   public static ConstNumber copyOf(IRCode code, ConstNumber original) {
-    Value newValue =
-        new Value(code.valueNumberGenerator.next(), original.outType(), original.getLocalInfo());
+    Value newValue = new Value(
+        code.valueNumberGenerator.next(),
+        original.outValue().getTypeLattice(),
+        original.getLocalInfo());
     return new ConstNumber(newValue, original.getRawValue());
   }
 
@@ -278,22 +272,23 @@
     // TODO(b/72693244): IR builder should know the type and assign a proper type lattice.
     switch (outType()) {
       case OBJECT:
-        return ReferenceTypeLatticeElement.getNullTypeLatticeElement();
+        assert isZero();
+        return TypeLatticeElement.NULL;
       case INT:
-        return IntTypeLatticeElement.getInstance();
+        return TypeLatticeElement.INT;
       case FLOAT:
-        return FloatTypeLatticeElement.getInstance();
+        return TypeLatticeElement.FLOAT;
       case LONG:
-        return LongTypeLatticeElement.getInstance();
+        return TypeLatticeElement.LONG;
       case DOUBLE:
-        return DoubleTypeLatticeElement.getInstance();
+        return TypeLatticeElement.DOUBLE;
       case INT_OR_FLOAT:
-        return SingleTypeLatticeElement.getInstance();
+        return TypeLatticeElement.SINGLE;
       case LONG_OR_DOUBLE:
-        return WideTypeLatticeElement.getInstance();
+        return TypeLatticeElement.DOUBLE;
       case INT_OR_FLOAT_OR_NULL:
       default:
-        return BottomTypeLatticeElement.getInstance();
+        return TypeLatticeElement.BOTTOM;
     }
   }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/ConstString.java b/src/main/java/com/android/tools/r8/ir/code/ConstString.java
index b5a3b90..85fd784 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ConstString.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ConstString.java
@@ -28,7 +28,9 @@
 
   public static ConstString copyOf(IRCode code, ConstString original) {
     Value newValue =
-        new Value(code.valueNumberGenerator.next(), original.outType(), original.getLocalInfo());
+        new Value(code.valueNumberGenerator.next(),
+            original.outValue().getTypeLattice(),
+            original.getLocalInfo());
     return new ConstString(newValue, original.getValue());
   }
 
@@ -131,6 +133,6 @@
 
   @Override
   public TypeLatticeElement evaluate(AppInfo appInfo) {
-    return TypeLatticeElement.fromDexType(appInfo, appInfo.dexItemFactory.stringType, false);
+    return TypeLatticeElement.fromDexType(appInfo.dexItemFactory.stringType, appInfo, false);
   }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/FixedRegisterValue.java b/src/main/java/com/android/tools/r8/ir/code/FixedRegisterValue.java
index 1427e12..0578506 100644
--- a/src/main/java/com/android/tools/r8/ir/code/FixedRegisterValue.java
+++ b/src/main/java/com/android/tools/r8/ir/code/FixedRegisterValue.java
@@ -3,14 +3,16 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.code;
 
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
+
 // Value that has a fixed register allocated. These are used for inserting spill, restore, and phi
 // moves in the spilling register allocator.
 public class FixedRegisterValue extends Value {
   private final int register;
 
-  public FixedRegisterValue(ValueType type, int register) {
+  public FixedRegisterValue(TypeLatticeElement typeLattice, int register) {
     // Set local info to null since these values are never representatives of live-ranges.
-    super(-1, type, null);
+    super(-1, typeLattice, null);
     setNeedsRegister(true);
     this.register = register;
   }
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 1cafe2a..92e2ddb 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
@@ -4,8 +4,10 @@
 package com.android.tools.r8.ir.code;
 
 import com.android.tools.r8.errors.Unreachable;
+import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.graph.DebugLocalInfo;
 import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.utils.CfgPrinter;
 import com.android.tools.r8.utils.InternalOptions;
 import com.google.common.collect.ImmutableList;
@@ -22,6 +24,7 @@
 import java.util.Map;
 import java.util.Queue;
 import java.util.Set;
+import java.util.function.Predicate;
 import java.util.stream.Collectors;
 
 public class IRCode {
@@ -407,6 +410,7 @@
     assert consistentDefUseChains();
     assert validThrowingInstructions();
     assert noCriticalEdges();
+    assert noBottomTypeLatticeLeft();
     return true;
   }
 
@@ -420,6 +424,11 @@
     return true;
   }
 
+  public boolean verifyTypes(AppInfo appInfo) {
+    assert blocks.stream().allMatch(block -> block.verifyTypes(appInfo));
+    return true;
+  }
+
   private boolean noCriticalEdges() {
     for (BasicBlock block : blocks) {
       List<BasicBlock> predecessors = block.getPredecessors();
@@ -605,6 +614,29 @@
     return true;
   }
 
+  private boolean noBottomTypeLatticeLeft() {
+    return verifySSATypeLattice(lattice -> !lattice.isBottom());
+  }
+
+  private boolean noImpreciseTypeLatticeLeft() {
+    return verifySSATypeLattice(TypeLatticeElement::isPreciseType);
+  }
+
+  private boolean verifySSATypeLattice(Predicate<TypeLatticeElement> tester) {
+    for (BasicBlock block : blocks) {
+      for (Instruction instruction : block.getInstructions()) {
+        Value outValue = instruction.outValue();
+        if (outValue != null) {
+          assert tester.test(outValue.getTypeLattice());
+        }
+      }
+      for (Phi phi : block.getPhis()) {
+        assert tester.test(phi.getTypeLattice());
+      }
+    }
+    return true;
+  }
+
   public InstructionIterator instructionIterator() {
     return new IRCodeInstructionsIterator(this);
   }
@@ -683,16 +715,20 @@
     return thisValue;
   }
 
-  public Value createValue(ValueType valueType, DebugLocalInfo local) {
-    return new Value(valueNumberGenerator.next(), valueType, local);
+  public Value createValue(TypeLatticeElement typeLattice, DebugLocalInfo local) {
+    return new Value(valueNumberGenerator.next(), typeLattice, local);
   }
 
-  public Value createValue(ValueType valueType) {
-    return createValue(valueType, null);
+  public Value createValue(TypeLatticeElement typeLattice) {
+    return createValue(typeLattice, null);
+  }
+
+  public Value createValue(DebugLocalInfo local) {
+    return createValue(TypeLatticeElement.BOTTOM, local);
   }
 
   public ConstNumber createIntConstant(int value) {
-    Value out = createValue(ValueType.INT);
+    Value out = createValue(TypeLatticeElement.INT);
     return new ConstNumber(out, value);
   }
 
@@ -701,7 +737,7 @@
   }
 
   public ConstNumber createConstNull() {
-    Value out = createValue(ValueType.OBJECT);
+    Value out = createValue(TypeLatticeElement.NULL);
     return new ConstNumber(out, 0);
   }
 
diff --git a/src/main/java/com/android/tools/r8/ir/code/If.java b/src/main/java/com/android/tools/r8/ir/code/If.java
index 266069b..4fdb047 100644
--- a/src/main/java/com/android/tools/r8/ir/code/If.java
+++ b/src/main/java/com/android/tools/r8/ir/code/If.java
@@ -228,12 +228,13 @@
 
   @Override
   public void buildCf(CfBuilder builder) {
+    ValueType ifType = inValues.get(0).type;
     if (inValues.size() == 1) {
-      builder.add(new CfIf(type, inValues.get(0).type, builder.getLabel(getTrueTarget())));
+      builder.add(new CfIf(type, ifType, builder.getLabel(getTrueTarget())));
       return;
     }
     assert inValues.size() == 2;
     assert inValues.get(0).type == inValues.get(1).type;
-    builder.add(new CfIfCmp(type, inValues.get(0).type, builder.getLabel(getTrueTarget())));
+    builder.add(new CfIfCmp(type, ifType, builder.getLabel(getTrueTarget())));
   }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/InstanceGet.java b/src/main/java/com/android/tools/r8/ir/code/InstanceGet.java
index 0a919bb..0c8c372 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InstanceGet.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InstanceGet.java
@@ -135,7 +135,7 @@
 
   @Override
   public TypeLatticeElement evaluate(AppInfo appInfo) {
-    return TypeLatticeElement.fromDexType(appInfo, field.type, true);
+    return TypeLatticeElement.fromDexType(field.type, appInfo, true);
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/ir/code/InstanceOf.java b/src/main/java/com/android/tools/r8/ir/code/InstanceOf.java
index c5dc5e4..8e2446b 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InstanceOf.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InstanceOf.java
@@ -9,7 +9,6 @@
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.graph.DexType;
-import com.android.tools.r8.ir.analysis.type.IntTypeLatticeElement;
 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;
@@ -87,7 +86,7 @@
 
   @Override
   public TypeLatticeElement evaluate(AppInfo appInfo) {
-    return IntTypeLatticeElement.getInstance();
+    return TypeLatticeElement.INT;
   }
 
   @Override
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 8f1a004..d3355b4 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
@@ -1089,6 +1089,11 @@
         "Implement type lattice evaluation for: " + getInstructionName());
   }
 
+  public boolean verifyTypes(AppInfo appInfo) {
+    // TODO(b/72693244): for instructions with invariant out type, we can verify type directly here.
+    return true;
+  }
+
   /**
    * Indicates whether the instruction throws a NullPointerException if the object denoted by the
    * given value is null at runtime execution.
diff --git a/src/main/java/com/android/tools/r8/ir/code/Invoke.java b/src/main/java/com/android/tools/r8/ir/code/Invoke.java
index 6e7c207..b755336 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Invoke.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Invoke.java
@@ -280,6 +280,6 @@
     if (returnType.isVoidType()) {
       throw new Unreachable("void methods have no type.");
     }
-    return TypeLatticeElement.fromDexType(appInfo, returnType, true);
+    return TypeLatticeElement.fromDexType(returnType, appInfo, true);
   }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/LogicalBinop.java b/src/main/java/com/android/tools/r8/ir/code/LogicalBinop.java
index 4b34ca1..ad3d344 100644
--- a/src/main/java/com/android/tools/r8/ir/code/LogicalBinop.java
+++ b/src/main/java/com/android/tools/r8/ir/code/LogicalBinop.java
@@ -9,6 +9,7 @@
 import com.android.tools.r8.ir.analysis.constant.Bottom;
 import com.android.tools.r8.ir.analysis.constant.ConstLatticeElement;
 import com.android.tools.r8.ir.analysis.constant.LatticeElement;
+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 java.util.function.Function;
@@ -116,7 +117,7 @@
       ConstNumber newConst;
       if (type == NumericType.INT) {
         int result = foldIntegers(leftConst.getIntValue(), rightConst.getIntValue());
-        Value value = code.createValue(ValueType.INT, getLocalInfo());
+        Value value = code.createValue(TypeLatticeElement.INT, getLocalInfo());
         newConst = new ConstNumber(value, result);
       } else {
         assert type == NumericType.LONG;
@@ -128,7 +129,7 @@
           right = rightConst.getLongValue();
         }
         long result = foldLongs(leftConst.getLongValue(), right);
-        Value value = code.createValue(ValueType.LONG, getLocalInfo());
+        Value value = code.createValue(TypeLatticeElement.LONG, getLocalInfo());
         newConst = new ConstNumber(value, result);
       }
       return new ConstLatticeElement(newConst);
diff --git a/src/main/java/com/android/tools/r8/ir/code/MoveException.java b/src/main/java/com/android/tools/r8/ir/code/MoveException.java
index c92ac50..562b33d 100644
--- a/src/main/java/com/android/tools/r8/ir/code/MoveException.java
+++ b/src/main/java/com/android/tools/r8/ir/code/MoveException.java
@@ -94,14 +94,15 @@
     return true;
   }
 
-  private Set<DexType> collectExceptionTypes(DexItemFactory dexItemFactory) {
-    Set<DexType> exceptionTypes = new HashSet<>(getBlock().getPredecessors().size());
-    for (BasicBlock block : getBlock().getPredecessors()) {
+  public static Set<DexType> collectExceptionTypes(
+      BasicBlock currentBlock, DexItemFactory dexItemFactory) {
+    Set<DexType> exceptionTypes = new HashSet<>(currentBlock.getPredecessors().size());
+    for (BasicBlock block : currentBlock.getPredecessors()) {
       int size = block.getCatchHandlers().size();
       List<BasicBlock> targets = block.getCatchHandlers().getAllTargets();
       List<DexType> guards = block.getCatchHandlers().getGuards();
       for (int i = 0; i < size; i++) {
-        if (targets.get(i) == getBlock()) {
+        if (targets.get(i) == currentBlock) {
           DexType guard = guards.get(i);
           exceptionTypes.add(
               guard == dexItemFactory.catchAllType
@@ -115,14 +116,14 @@
 
   @Override
   public DexType computeVerificationType(TypeVerificationHelper helper) {
-    return helper.join(collectExceptionTypes(helper.getFactory()));
+    return helper.join(collectExceptionTypes(getBlock(), helper.getFactory()));
   }
 
   @Override
   public TypeLatticeElement evaluate(AppInfo appInfo) {
-    Set<DexType> exceptionTypes = collectExceptionTypes(appInfo.dexItemFactory);
+    Set<DexType> exceptionTypes = collectExceptionTypes(getBlock(), appInfo.dexItemFactory);
     return TypeLatticeElement.join(
         appInfo,
-        exceptionTypes.stream().map(t -> TypeLatticeElement.fromDexType(appInfo, t, false)));
+        exceptionTypes.stream().map(t -> TypeLatticeElement.fromDexType(t, appInfo, false)));
   }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Neg.java b/src/main/java/com/android/tools/r8/ir/code/Neg.java
index 16b2922..86e7440 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Neg.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Neg.java
@@ -12,6 +12,8 @@
 import com.android.tools.r8.ir.analysis.constant.Bottom;
 import com.android.tools.r8.ir.analysis.constant.ConstLatticeElement;
 import com.android.tools.r8.ir.analysis.constant.LatticeElement;
+import com.android.tools.r8.ir.analysis.type.PrimitiveTypeLatticeElement;
+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 java.util.function.Function;
@@ -81,8 +83,8 @@
     LatticeElement sourceLattice = getLatticeElement.apply(source());
     if (sourceLattice.isConst()) {
       ConstNumber sourceConst = sourceLattice.asConst().getConstNumber();
-      ValueType valueType = ValueType.fromNumericType(type);
-      Value value = code.createValue(valueType, getLocalInfo());
+      TypeLatticeElement typeLattice = PrimitiveTypeLatticeElement.fromNumericType(type);
+      Value value = code.createValue(typeLattice, getLocalInfo());
       ConstNumber newConst;
       if (type == NumericType.INT) {
         newConst = new ConstNumber(value, -sourceConst.getIntValue());
diff --git a/src/main/java/com/android/tools/r8/ir/code/NewInstance.java b/src/main/java/com/android/tools/r8/ir/code/NewInstance.java
index 8dbc38b..29b263f 100644
--- a/src/main/java/com/android/tools/r8/ir/code/NewInstance.java
+++ b/src/main/java/com/android/tools/r8/ir/code/NewInstance.java
@@ -107,7 +107,7 @@
 
   @Override
   public TypeLatticeElement evaluate(AppInfo appInfo) {
-    return TypeLatticeElement.fromDexType(appInfo, clazz, false);
+    return TypeLatticeElement.fromDexType(clazz, appInfo, false);
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/ir/code/Not.java b/src/main/java/com/android/tools/r8/ir/code/Not.java
index 1037c34..55918cc 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Not.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Not.java
@@ -12,6 +12,8 @@
 import com.android.tools.r8.ir.analysis.constant.Bottom;
 import com.android.tools.r8.ir.analysis.constant.ConstLatticeElement;
 import com.android.tools.r8.ir.analysis.constant.LatticeElement;
+import com.android.tools.r8.ir.analysis.type.PrimitiveTypeLatticeElement;
+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 java.util.function.Function;
@@ -35,8 +37,8 @@
     LatticeElement sourceLattice = getLatticeElement.apply(source());
     if (sourceLattice.isConst()) {
       ConstNumber sourceConst = sourceLattice.asConst().getConstNumber();
-      ValueType valueType = ValueType.fromNumericType(type);
-      Value value = code.createValue(valueType, getLocalInfo());
+      TypeLatticeElement typeLattice  = PrimitiveTypeLatticeElement.fromNumericType(type);
+      Value value = code.createValue(typeLattice, getLocalInfo());
       ConstNumber newConst;
       if (type == NumericType.INT) {
         newConst = new ConstNumber(value, ~sourceConst.getIntValue());
diff --git a/src/main/java/com/android/tools/r8/ir/code/Phi.java b/src/main/java/com/android/tools/r8/ir/code/Phi.java
index f3301e7..c688e6d 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Phi.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Phi.java
@@ -8,6 +8,7 @@
 import com.android.tools.r8.errors.InvalidDebugInfoException;
 import com.android.tools.r8.graph.DebugLocalInfo;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.BasicBlock.EdgeType;
 import com.android.tools.r8.ir.conversion.IRBuilder;
 import com.android.tools.r8.utils.CfgPrinter;
@@ -41,10 +42,10 @@
   public Phi(
       int number,
       BasicBlock block,
-      ValueType type,
+      TypeLatticeElement typeLattice,
       DebugLocalInfo local,
       RegisterReadType readType) {
-    super(number, type, local);
+    super(number, typeLattice, local);
     this.block = block;
     this.readType = readType;
     block.addPhi(this);
@@ -95,7 +96,7 @@
           assert readType == RegisterReadType.DEBUG;
           BasicBlock block = getBlock();
           InstructionListIterator it = block.listIterator();
-          Value value = new Value(builder.getValueNumberGenerator().next(), type, null);
+          Value value = new Value(builder.getValueNumberGenerator().next(), getTypeLattice(), null);
           Position position = block.getPosition();
           Instruction definition = new DebugLocalUninitialized(value);
           definition.setBlock(block);
diff --git a/src/main/java/com/android/tools/r8/ir/code/StackValue.java b/src/main/java/com/android/tools/r8/ir/code/StackValue.java
index 46aa5db..d9dabef 100644
--- a/src/main/java/com/android/tools/r8/ir/code/StackValue.java
+++ b/src/main/java/com/android/tools/r8/ir/code/StackValue.java
@@ -5,14 +5,15 @@
 
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 
 public class StackValue extends Value {
 
   private final int height;
   private final DexType objectType;
 
-  private StackValue(DexType objectType, ValueType valueType, int height) {
-    super(Value.UNDEFINED_NUMBER, valueType, null);
+  private StackValue(DexType objectType, TypeLatticeElement typeLattice, int height) {
+    super(Value.UNDEFINED_NUMBER, typeLattice, null);
     this.height = height;
     this.objectType = objectType;
     assert height >= 0;
@@ -20,12 +21,12 @@
 
   public static StackValue forObjectType(DexType type, int height) {
     assert DexItemFactory.nullValueType == type || type.isClassType() || type.isArrayType();
-    return new StackValue(type, ValueType.OBJECT, height);
+    return new StackValue(type, TypeLatticeElement.fromDexType(type), height);
   }
 
   public static StackValue forNonObjectType(ValueType valueType, int height) {
     assert valueType.isPreciseType() && !valueType.isObject();
-    return new StackValue(null, valueType, height);
+    return new StackValue(null, valueType.toTypeLattice(), height);
   }
 
   public int getHeight() {
diff --git a/src/main/java/com/android/tools/r8/ir/code/StaticGet.java b/src/main/java/com/android/tools/r8/ir/code/StaticGet.java
index 50591b0..9ef7ed4 100644
--- a/src/main/java/com/android/tools/r8/ir/code/StaticGet.java
+++ b/src/main/java/com/android/tools/r8/ir/code/StaticGet.java
@@ -145,7 +145,7 @@
 
   @Override
   public TypeLatticeElement evaluate(AppInfo appInfo) {
-    return TypeLatticeElement.fromDexType(appInfo, field.type, true);
+    return TypeLatticeElement.fromDexType(field.type, appInfo, true);
   }
 
   @Override
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 48b8f5b..26c2e60 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
@@ -8,7 +8,6 @@
 import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.graph.DebugLocalInfo;
 import com.android.tools.r8.graph.DexMethod;
-import com.android.tools.r8.ir.analysis.type.BottomTypeLatticeElement;
 import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.regalloc.LiveIntervals;
 import com.android.tools.r8.origin.Origin;
@@ -43,6 +42,7 @@
               new MethodPosition(method)));
     }
     type = meet;
+    typeLattice = meet.toTypeLattice();
   }
 
   public void markNonDebugLocalRead() {
@@ -113,7 +113,8 @@
 
   public static final int UNDEFINED_NUMBER = -1;
 
-  public static final Value UNDEFINED = new Value(UNDEFINED_NUMBER, ValueType.OBJECT, null);
+  public static final Value UNDEFINED =
+      new Value(UNDEFINED_NUMBER, TypeLatticeElement.BOTTOM, null);
 
   protected final int number;
   // TODO(b/72693244): deprecate once typeLattice is landed.
@@ -134,12 +135,13 @@
   private boolean knownToBeBoolean = false;
   private LongInterval valueRange;
   private DebugData debugData;
-  private TypeLatticeElement typeLattice = BottomTypeLatticeElement.getInstance();
+  private TypeLatticeElement typeLattice;
 
-  public Value(int number, ValueType type, DebugLocalInfo local) {
+  public Value(int number, TypeLatticeElement typeLattice, DebugLocalInfo local) {
     this.number = number;
-    this.type = type;
+    this.type = ValueType.fromTypeLattice(typeLattice);
     this.debugData = local == null ? null : new DebugData(local);
+    this.typeLattice = typeLattice;
   }
 
   public boolean isFixedRegisterValue() {
diff --git a/src/main/java/com/android/tools/r8/ir/code/ValueType.java b/src/main/java/com/android/tools/r8/ir/code/ValueType.java
index 99f949d..2d53749 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ValueType.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ValueType.java
@@ -7,6 +7,7 @@
 import com.android.tools.r8.errors.InternalCompilerError;
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 
 public enum ValueType {
   OBJECT,
@@ -181,4 +182,54 @@
         throw new Unreachable("Invalid numeric type '" + type + "'");
     }
   }
+
+  public static ValueType fromTypeLattice(TypeLatticeElement typeLatticeElement) {
+    if (typeLatticeElement.isBottom()) {
+      return INT_OR_FLOAT_OR_NULL;
+    }
+    if (typeLatticeElement.isReference()) {
+      return OBJECT;
+    }
+    if (typeLatticeElement.isInt()) {
+      return INT;
+    }
+    if (typeLatticeElement.isFloat()) {
+      return FLOAT;
+    }
+    if (typeLatticeElement.isLong()) {
+      return LONG;
+    }
+    if (typeLatticeElement.isDouble()) {
+      return DOUBLE;
+    }
+    if (typeLatticeElement.isSingle()) {
+      return INT_OR_FLOAT;
+    }
+    if (typeLatticeElement.isWide()) {
+      return LONG_OR_DOUBLE;
+    }
+    throw new Unreachable("Invalid type lattice '" + typeLatticeElement + "'");
+  }
+
+  public TypeLatticeElement toTypeLattice() {
+    switch (this) {
+      case OBJECT:
+        return TypeLatticeElement.REFERENCE;
+      case INT:
+        return TypeLatticeElement.INT;
+      case FLOAT:
+        return TypeLatticeElement.FLOAT;
+      case INT_OR_FLOAT:
+        return TypeLatticeElement.SINGLE;
+      case LONG:
+        return TypeLatticeElement.LONG;
+      case DOUBLE:
+        return TypeLatticeElement.DOUBLE;
+      case LONG_OR_DOUBLE:
+        return TypeLatticeElement.WIDE;
+      case INT_OR_FLOAT_OR_NULL:
+      default:
+        return TypeLatticeElement.BOTTOM;
+    }
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/CfSourceCode.java b/src/main/java/com/android/tools/r8/ir/conversion/CfSourceCode.java
index 6fbafcb..9e14033 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/CfSourceCode.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/CfSourceCode.java
@@ -22,10 +22,10 @@
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.CanonicalPositions;
 import com.android.tools.r8.ir.code.CatchHandlers;
 import com.android.tools.r8.ir.code.Position;
-import com.android.tools.r8.ir.code.ValueType;
 import com.android.tools.r8.ir.conversion.CfState.Snapshot;
 import com.android.tools.r8.ir.conversion.IRBuilder.BlockInfo;
 import com.android.tools.r8.origin.Origin;
@@ -347,9 +347,9 @@
       if (type.isBooleanType()) {
         builder.addBooleanNonThisArgument(argumentRegister++);
       } else {
-        ValueType valueType = ValueType.fromDexType(type);
-        builder.addNonThisArgument(argumentRegister, valueType);
-        argumentRegister += valueType.requiredRegisters();
+        TypeLatticeElement typeLattice = TypeLatticeElement.fromDexType(type);
+        builder.addNonThisArgument(argumentRegister, typeLattice);
+        argumentRegister += typeLattice.requiredRegisters();
       }
     }
   }
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/DexSourceCode.java b/src/main/java/com/android/tools/r8/ir/conversion/DexSourceCode.java
index b588408..b7c99b1 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/DexSourceCode.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/DexSourceCode.java
@@ -40,10 +40,10 @@
 import com.android.tools.r8.graph.DexProto;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.MethodAccessFlags;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.CanonicalPositions;
 import com.android.tools.r8.ir.code.CatchHandlers;
 import com.android.tools.r8.ir.code.Position;
-import com.android.tools.r8.ir.code.ValueType;
 import java.util.ArrayList;
 import java.util.HashMap;
 import java.util.HashSet;
@@ -71,7 +71,7 @@
   private Position currentPosition = null;
   private final CanonicalPositions canonicalPositions;
 
-  private final List<ValueType> argumentTypes;
+  private final List<TypeLatticeElement> argumentTypes;
 
   private List<DexDebugEntry> debugEntries = null;
   // In case of inlining the position of the invoke in the caller.
@@ -150,9 +150,9 @@
       builder.addThisArgument(register);
       ++register;
     }
-    for (ValueType type : argumentTypes) {
-      builder.addNonThisArgument(register, type);
-      register += type.requiredRegisters();
+    for (TypeLatticeElement typeLattice : argumentTypes) {
+      builder.addNonThisArgument(register, typeLattice);
+      register += typeLattice.requiredRegisters();
     }
   }
 
@@ -303,12 +303,12 @@
         arrayFilledDataPayloadResolver.getData(payloadOffset));
   }
 
-  private List<ValueType> computeArgumentTypes() {
-    List<ValueType> types = new ArrayList<>(proto.parameters.size());
+  private List<TypeLatticeElement> computeArgumentTypes() {
+    List<TypeLatticeElement> types = new ArrayList<>(proto.parameters.size());
     String shorty = proto.shorty.toString();
     for (int i = 1; i < proto.shorty.size; i++) {
-      ValueType valueType = ValueType.fromTypeDescriptorChar(shorty.charAt(i));
-      types.add(valueType);
+      TypeLatticeElement typeLattice = TypeLatticeElement.fromTypeDescriptorChar(shorty.charAt(i));
+      types.add(typeLattice);
     }
     return types;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java b/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java
index deac5eb..b471e12 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java
@@ -20,6 +20,8 @@
 import com.android.tools.r8.graph.DexProto;
 import com.android.tools.r8.graph.DexString;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.PrimitiveTypeLatticeElement;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.Add;
 import com.android.tools.r8.ir.code.And;
 import com.android.tools.r8.ir.code.Argument;
@@ -118,6 +120,11 @@
  * http://compilers.cs.uni-saarland.de/papers/bbhlmz13cc.pdf
  */
 public class IRBuilder {
+  private static final TypeLatticeElement INT = TypeLatticeElement.INT;
+  private static final TypeLatticeElement FLOAT = TypeLatticeElement.FLOAT;
+  private static final TypeLatticeElement LONG = TypeLatticeElement.LONG;
+  private static final TypeLatticeElement DOUBLE = TypeLatticeElement.DOUBLE;
+  private static final TypeLatticeElement NULL = TypeLatticeElement.NULL;
 
   public static final int INITIAL_BLOCK_OFFSET = -1;
 
@@ -672,7 +679,10 @@
     int moveExceptionDest = source.getMoveExceptionRegister(targetIndex);
     Position position = source.getCanonicalDebugPositionAtOffset(moveExceptionItem.targetOffset);
     if (moveExceptionDest >= 0) {
-      Value out = writeRegister(moveExceptionDest, ValueType.OBJECT, ThrowingInfo.NO_THROW, null);
+      Set<DexType> exceptionTypes = MoveException.collectExceptionTypes(currentBlock, getFactory());
+      TypeLatticeElement typeLattice = TypeLatticeElement.join(appInfo,
+          exceptionTypes.stream().map(t -> TypeLatticeElement.fromDexType(t, appInfo, false)));
+      Value out = writeRegister(moveExceptionDest, typeLattice, ThrowingInfo.NO_THROW, null);
       MoveException moveException = new MoveException(out);
       moveException.setPosition(position);
       currentBlock.add(moveException);
@@ -719,20 +729,23 @@
 
   public void addThisArgument(int register) {
     DebugLocalInfo local = getOutgoingLocal(register);
-    Value value = writeRegister(register, ValueType.OBJECT, ThrowingInfo.NO_THROW, local);
+    // TODO(b/72693244): Update nullability if this is for building inlinee's IR.
+    TypeLatticeElement receiver =
+        TypeLatticeElement.fromDexType(method.method.getHolder(), appInfo, false);
+    Value value = writeRegister(register, receiver, ThrowingInfo.NO_THROW, local);
     addInstruction(new Argument(value));
     value.markAsThis();
   }
 
-  public void addNonThisArgument(int register, ValueType valueType) {
+  public void addNonThisArgument(int register, TypeLatticeElement typeLattice) {
     DebugLocalInfo local = getOutgoingLocal(register);
-    Value value = writeRegister(register, valueType, ThrowingInfo.NO_THROW, local);
+    Value value = writeRegister(register, typeLattice, ThrowingInfo.NO_THROW, local);
     addInstruction(new Argument(value));
   }
 
   public void addBooleanNonThisArgument(int register) {
     DebugLocalInfo local = getOutgoingLocal(register);
-    Value value = writeRegister(register, ValueType.INT, ThrowingInfo.NO_THROW, local);
+    Value value = writeRegister(register, INT, ThrowingInfo.NO_THROW, local);
     value.setKnownToBeBoolean(true);
     addInstruction(new Argument(value));
   }
@@ -756,7 +769,8 @@
       // Note that the write register must not lookup outgoing local information and the local is
       // never considered clobbered by a start (if the in value has local info it must have been
       // marked ended elsewhere).
-      Value out = writeRegister(register, incomingValue.outType(), ThrowingInfo.NO_THROW, local);
+      Value out = writeRegister(
+          register, incomingValue.getTypeLattice(), ThrowingInfo.NO_THROW, local);
       DebugLocalWrite write = new DebugLocalWrite(out, incomingValue);
       addInstruction(write);
     }
@@ -831,7 +845,8 @@
   public void addArrayGet(MemberType type, int dest, int array, int index) {
     Value in1 = readRegister(array, ValueType.OBJECT);
     Value in2 = readRegister(index, ValueType.INT);
-    Value out = writeRegister(dest, ValueType.fromMemberType(type), ThrowingInfo.CAN_THROW);
+    Value out = writeRegister(
+        dest, TypeLatticeElement.fromMemberType(type), ThrowingInfo.CAN_THROW);
     out.setKnownToBeBoolean(type == MemberType.BOOLEAN);
     ArrayGet instruction = new ArrayGet(type, out, in1, in2);
     assert instruction.instructionTypeCanThrow();
@@ -840,7 +855,7 @@
 
   public void addArrayLength(int dest, int array) {
     Value in = readRegister(array, ValueType.OBJECT);
-    Value out = writeRegister(dest, ValueType.INT, ThrowingInfo.CAN_THROW);
+    Value out = writeRegister(dest, INT, ThrowingInfo.CAN_THROW);
     ArrayLength instruction = new ArrayLength(out, in);
     assert instruction.instructionTypeCanThrow();
     add(instruction);
@@ -856,7 +871,9 @@
 
   public void addCheckCast(int value, DexType type) {
     Value in = readRegister(value, ValueType.OBJECT);
-    Value out = writeRegister(value, ValueType.OBJECT, ThrowingInfo.CAN_THROW);
+    TypeLatticeElement castTypeLattice =
+        TypeLatticeElement.fromDexType(type, appInfo, in.getTypeLattice().isNullable());
+    Value out = writeRegister(value, castTypeLattice, ThrowingInfo.CAN_THROW);
     CheckCast instruction = new CheckCast(out, in, type);
     assert instruction.instructionTypeCanThrow();
     add(instruction);
@@ -865,41 +882,42 @@
   public void addCmp(NumericType type, Bias bias, int dest, int left, int right) {
     Value in1 = readNumericRegister(left, type);
     Value in2 = readNumericRegister(right, type);
-    Value out = writeRegister(dest, ValueType.INT, ThrowingInfo.NO_THROW);
+    Value out = writeRegister(dest, INT, ThrowingInfo.NO_THROW);
     Cmp instruction = new Cmp(type, bias, out, in1, in2);
     assert !instruction.instructionTypeCanThrow();
     add(instruction);
   }
 
-  public void addConst(ValueType type, int dest, long value) {
-    Value out = writeRegister(dest, type, ThrowingInfo.NO_THROW);
+  public void addConst(TypeLatticeElement typeLattice, int dest, long value) {
+    Value out = writeRegister(dest, typeLattice, ThrowingInfo.NO_THROW);
     ConstNumber instruction = new ConstNumber(out, value);
     assert !instruction.instructionTypeCanThrow();
     add(instruction);
   }
 
   public void addLongConst(int dest, long value) {
-    add(new ConstNumber(writeRegister(dest, ValueType.LONG, ThrowingInfo.NO_THROW), value));
+    add(new ConstNumber(writeRegister(dest, LONG, ThrowingInfo.NO_THROW), value));
   }
 
   public void addDoubleConst(int dest, long value) {
-    add(new ConstNumber(writeRegister(dest, ValueType.DOUBLE, ThrowingInfo.NO_THROW), value));
+    add(new ConstNumber(writeRegister(dest, DOUBLE, ThrowingInfo.NO_THROW), value));
   }
 
   public void addIntConst(int dest, long value) {
-    add(new ConstNumber(writeRegister(dest, ValueType.INT, ThrowingInfo.NO_THROW), value));
+    add(new ConstNumber(writeRegister(dest, INT, ThrowingInfo.NO_THROW), value));
   }
 
   public void addFloatConst(int dest, long value) {
-    add(new ConstNumber(writeRegister(dest, ValueType.FLOAT, ThrowingInfo.NO_THROW), value));
+    add(new ConstNumber(writeRegister(dest, FLOAT, ThrowingInfo.NO_THROW), value));
   }
 
   public void addNullConst(int dest) {
-    add(new ConstNumber(writeRegister(dest, ValueType.OBJECT, ThrowingInfo.NO_THROW), 0L));
+    add(new ConstNumber(writeRegister(dest, NULL, ThrowingInfo.NO_THROW), 0L));
   }
 
   public void addConstClass(int dest, DexType type) {
-    Value out = writeRegister(dest, ValueType.OBJECT, ThrowingInfo.CAN_THROW);
+    TypeLatticeElement typeLattice = TypeLatticeElement.classClassType(appInfo);
+    Value out = writeRegister(dest, typeLattice, ThrowingInfo.CAN_THROW);
     ConstClass instruction = new ConstClass(out, type);
     assert instruction.instructionTypeCanThrow();
     add(instruction);
@@ -912,7 +930,9 @@
           "Const-method-handle",
           null /* sourceString */);
     }
-    Value out = writeRegister(dest, ValueType.OBJECT, ThrowingInfo.CAN_THROW);
+    TypeLatticeElement typeLattice =
+        TypeLatticeElement.fromDexType(appInfo.dexItemFactory.methodHandleType, appInfo, false);
+    Value out = writeRegister(dest, typeLattice, ThrowingInfo.CAN_THROW);
     ConstMethodHandle instruction = new ConstMethodHandle(out, methodHandle);
     add(instruction);
   }
@@ -924,13 +944,16 @@
           "Const-method-type",
           null /* sourceString */);
     }
-    Value out = writeRegister(dest, ValueType.OBJECT, ThrowingInfo.CAN_THROW);
+    TypeLatticeElement typeLattice =
+        TypeLatticeElement.fromDexType(appInfo.dexItemFactory.methodTypeType, appInfo, false);
+    Value out = writeRegister(dest, typeLattice, ThrowingInfo.CAN_THROW);
     ConstMethodType instruction = new ConstMethodType(out, methodType);
     add(instruction);
   }
 
   public void addConstString(int dest, DexString string) {
-    Value out = writeRegister(dest, ValueType.OBJECT, ThrowingInfo.CAN_THROW);
+    TypeLatticeElement typeLattice = TypeLatticeElement.stringClassType(appInfo);
+    Value out = writeRegister(dest, typeLattice, ThrowingInfo.CAN_THROW);
     ConstString instruction = new ConstString(out, string);
     add(instruction);
   }
@@ -971,7 +994,7 @@
       // If the move is writing to a different local we must construct a new value.
       DebugLocalInfo destLocal = getOutgoingLocal(dest);
       if (destLocal != null && destLocal != in.getLocalInfo()) {
-        Value out = writeRegister(dest, type, ThrowingInfo.NO_THROW);
+        Value out = writeRegister(dest, in.getTypeLattice(), ThrowingInfo.NO_THROW);
         addInstruction(new DebugLocalWrite(out, in));
         return;
       }
@@ -1067,7 +1090,8 @@
     }
   }
 
-  public void addIfZero(If.Type type, ValueType operandType, int value, int trueTargetOffset, int falseTargetOffset) {
+  public void addIfZero(
+      If.Type type, ValueType operandType, int value, int trueTargetOffset, int falseTargetOffset) {
     if (trueTargetOffset == falseTargetOffset) {
       addTrivialIf(trueTargetOffset, falseTargetOffset);
     } else {
@@ -1079,7 +1103,8 @@
   public void addInstanceGet(int dest, int object, DexField field) {
     MemberType type = MemberType.fromDexType(field.type);
     Value in = readRegister(object, ValueType.OBJECT);
-    Value out = writeRegister(dest, ValueType.fromMemberType(type), ThrowingInfo.CAN_THROW);
+    Value out = writeRegister(
+        dest, TypeLatticeElement.fromDexType(field.type, appInfo, true), ThrowingInfo.CAN_THROW);
     out.setKnownToBeBoolean(type == MemberType.BOOLEAN);
     InstanceGet instruction = new InstanceGet(type, out, in, field);
     assert instruction.instructionTypeCanThrow();
@@ -1088,7 +1113,7 @@
 
   public void addInstanceOf(int dest, int value, DexType type) {
     Value in = readRegister(value, ValueType.OBJECT);
-    Value out = writeRegister(dest, ValueType.INT, ThrowingInfo.CAN_THROW);
+    Value out = writeRegister(dest, INT, ThrowingInfo.CAN_THROW);
     InstanceOf instruction = new InstanceOf(out, in, type);
     assert instruction.instructionTypeCanThrow();
     addInstruction(instruction);
@@ -1359,7 +1384,8 @@
     assert invoke.outValue() == null;
     assert invoke.instructionTypeCanThrow();
     DexType outType = invoke.getReturnType();
-    Value outValue = writeRegister(dest, ValueType.fromDexType(outType), ThrowingInfo.CAN_THROW);
+    Value outValue =
+        writeRegister(dest, TypeLatticeElement.fromDexType(outType), ThrowingInfo.CAN_THROW);
     outValue.setKnownToBeBoolean(outType.isBooleanType());
     invoke.setOutValue(outValue);
   }
@@ -1389,7 +1415,8 @@
   public void addNewArrayEmpty(int dest, int size, DexType type) {
     assert type.isArrayType();
     Value in = readRegister(size, ValueType.INT);
-    Value out = writeRegister(dest, ValueType.OBJECT, ThrowingInfo.CAN_THROW);
+    TypeLatticeElement arrayTypeLattice = TypeLatticeElement.fromDexType(type, appInfo, false);
+    Value out = writeRegister(dest, arrayTypeLattice, ThrowingInfo.CAN_THROW);
     NewArrayEmpty instruction = new NewArrayEmpty(out, in, type);
     assert instruction.instructionTypeCanThrow();
     addInstruction(instruction);
@@ -1400,7 +1427,8 @@
   }
 
   public void addNewInstance(int dest, DexType type) {
-    Value out = writeRegister(dest, ValueType.OBJECT, ThrowingInfo.CAN_THROW);
+    TypeLatticeElement instanceType = TypeLatticeElement.fromDexType(type, appInfo, false);
+    Value out = writeRegister(dest, instanceType, ThrowingInfo.CAN_THROW);
     NewInstance instruction = new NewInstance(type, out);
     assert instruction.instructionTypeCanThrow();
     addInstruction(instruction);
@@ -1426,7 +1454,8 @@
 
   public void addStaticGet(int dest, DexField field) {
     MemberType type = MemberType.fromDexType(field.type);
-    Value out = writeRegister(dest, ValueType.fromMemberType(type), ThrowingInfo.CAN_THROW);
+    Value out = writeRegister(
+        dest, TypeLatticeElement.fromDexType(field.type, appInfo, true), ThrowingInfo.CAN_THROW);
     out.setKnownToBeBoolean(type == MemberType.BOOLEAN);
     StaticGet instruction = new StaticGet(type, out, field);
     assert instruction.instructionTypeCanThrow();
@@ -1683,8 +1712,8 @@
 
   public Value readRegister(int register, ValueType type) {
     DebugLocalInfo local = getIncomingLocal(register);
-    Value value =
-        readRegister(register, type, currentBlock, EdgeType.NON_EDGE, RegisterReadType.NORMAL);
+    Value value = readRegister(
+        register, type, currentBlock, EdgeType.NON_EDGE, RegisterReadType.NORMAL);
     // Check that any information about a current-local is consistent with the read.
     if (local != null && value.getLocalInfo() != local && !value.isUninitializedLocal()) {
       throw new InvalidDebugInfoException(
@@ -1759,7 +1788,9 @@
         value = getUninitializedDebugLocalValue(register, type);
       } else {
         DebugLocalInfo local = getIncomingLocalAtBlock(register, block);
-        Phi phi = new Phi(valueNumberGenerator.next(), block, type, local, readType);
+        // TODO(b/72693244): Use BOTTOM, then run type analysis at the end of IR building.
+        Phi phi = new Phi(
+            valueNumberGenerator.next(), block, type.toTypeLattice(), local, readType);
         if (!block.isSealed()) {
           block.addIncompletePhi(register, phi, readingEdge);
           value = phi;
@@ -1811,7 +1842,7 @@
     // Create a new SSA value for the uninitialized local value.
     // Note that the uninitialized local value must not itself have local information, so that it
     // does not contribute to the visible/live-range of the local variable.
-    Value value = new Value(valueNumberGenerator.next(), type, null);
+    Value value = new Value(valueNumberGenerator.next(), type.toTypeLattice(), null);
     values.add(value);
     return value;
   }
@@ -1830,14 +1861,14 @@
   }
 
   public Value readLongLiteral(long constant) {
-    Value value = new Value(valueNumberGenerator.next(), ValueType.LONG, null);
+    Value value = new Value(valueNumberGenerator.next(), LONG, null);
     ConstNumber number = new ConstNumber(value, constant);
     add(number);
     return number.outValue();
   }
 
   public Value readIntLiteral(long constant) {
-    Value value = new Value(valueNumberGenerator.next(), ValueType.INT, null);
+    Value value = new Value(valueNumberGenerator.next(), INT, null);
     ConstNumber number = new ConstNumber(value, constant);
     add(number);
     return number.outValue();
@@ -1846,14 +1877,14 @@
   // This special write register is needed when changing the scoping of a local variable.
   // See addDebugLocalStart and addDebugLocalEnd.
   private Value writeRegister(
-      int register, ValueType type, ThrowingInfo throwing, DebugLocalInfo local) {
+      int register, TypeLatticeElement typeLattice, ThrowingInfo throwing, DebugLocalInfo local) {
     checkRegister(register);
-    Value value = new Value(valueNumberGenerator.next(), type, local);
+    Value value = new Value(valueNumberGenerator.next(), typeLattice, local);
     currentBlock.writeCurrentDefinition(register, value, throwing);
     return value;
   }
 
-  public Value writeRegister(int register, ValueType type, ThrowingInfo throwing) {
+  public Value writeRegister(int register, TypeLatticeElement typeLattice, ThrowingInfo throwing) {
     DebugLocalInfo incomingLocal = getIncomingLocal(register);
     DebugLocalInfo outgoingLocal = getOutgoingLocal(register);
     // If the local info does not change at the current instruction, we need to ensure
@@ -1868,11 +1899,11 @@
         (incomingLocal == null || incomingLocal != outgoingLocal)
             ? null
             : readRegisterForDebugLocal(register, incomingLocal);
-    return writeRegister(register, type, throwing, outgoingLocal);
+    return writeRegister(register, typeLattice, throwing, outgoingLocal);
   }
 
   public Value writeNumericRegister(int register, NumericType type, ThrowingInfo throwing) {
-    return writeRegister(register, ValueType.fromNumericType(type), throwing);
+    return writeRegister(register, PrimitiveTypeLatticeElement.fromNumericType(type), throwing);
   }
 
   private DebugLocalInfo getIncomingLocal(int register) {
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 db0c983..3c657ec 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
@@ -27,6 +27,7 @@
 import com.android.tools.r8.graph.GraphLense;
 import com.android.tools.r8.ir.analysis.constant.SparseConditionalConstantPropagation;
 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.AlwaysMaterializingDefinition;
 import com.android.tools.r8.ir.code.AlwaysMaterializingUser;
 import com.android.tools.r8.ir.code.BasicBlock;
@@ -34,7 +35,6 @@
 import com.android.tools.r8.ir.code.Instruction;
 import com.android.tools.r8.ir.code.InstructionListIterator;
 import com.android.tools.r8.ir.code.Value;
-import com.android.tools.r8.ir.code.ValueType;
 import com.android.tools.r8.ir.desugar.CovariantReturnTypeAnnotationTransformer;
 import com.android.tools.r8.ir.desugar.InterfaceMethodRewriter;
 import com.android.tools.r8.ir.desugar.LambdaRewriter;
@@ -143,7 +143,7 @@
     this.options = options;
     this.printer = printer;
     this.codeRewriter = new CodeRewriter(this, libraryMethodsReturningReceiver(), options);
-    this.stringConcatRewriter = new StringConcatRewriter(options.itemFactory);
+    this.stringConcatRewriter = new StringConcatRewriter(appInfo);
     this.lambdaRewriter = options.enableDesugaring ? new LambdaRewriter(this) : null;
     this.interfaceMethodRewriter =
         (options.enableDesugaring && enableInterfaceMethodDesugaring())
@@ -151,8 +151,8 @@
     this.twrCloseResourceRewriter =
         (options.enableDesugaring && enableTwrCloseResourceDesugaring())
             ? new TwrCloseResourceRewriter(this) : null;
-    this.lambdaMerger = options.enableLambdaMerging
-        ? new LambdaMerger(appInfo.dexItemFactory, options.reporter) : null;
+    this.lambdaMerger =
+        options.enableLambdaMerging ? new LambdaMerger(appInfo, options.reporter) : null;
     this.covariantReturnTypeAnnotationTransformer =
         options.processCovariantReturnTypeAnnotations
             ? new CovariantReturnTypeAnnotationTransformer(this, appInfo.dexItemFactory)
@@ -790,6 +790,9 @@
     if (devirtualizer != null) {
       devirtualizer.devirtualizeInvokeInterface(code, method.method.getHolder());
     }
+
+    assert code.verifyTypes(appInfo);
+
     codeRewriter.removeCasts(code);
     codeRewriter.rewriteLongCompareAndRequireNonNull(code, options);
     codeRewriter.commonSubexpressionElimination(code);
@@ -834,6 +837,8 @@
       assert code.isConsistentSSA();
     }
 
+    assert code.verifyTypes(appInfo);
+
     if (classInliner != null) {
       // Class inliner should work before lambda merger, so if it inlines the
       // lambda, it does not get collected by merger.
@@ -962,7 +967,7 @@
 
   private void finalizeToDex(DexEncodedMethod method, IRCode code, OptimizationFeedback feedback) {
     // Workaround massive dex2oat memory use for self-recursive methods.
-    CodeRewriter.disableDex2OatInliningForSelfRecursiveMethods(code, options);
+    CodeRewriter.disableDex2OatInliningForSelfRecursiveMethods(code, options, appInfo);
     // Perform register allocation.
     RegisterAllocator registerAllocator = performRegisterAllocation(code, method);
     method.setCode(code, registerAllocator, options);
@@ -1075,7 +1080,7 @@
     Instruction check = it.previous();
     assert addBefore == check;
     // Forced definition of const-zero
-    Value fixitValue = code.createValue(ValueType.INT);
+    Value fixitValue = code.createValue(TypeLatticeElement.INT);
     Instruction fixitDefinition = new AlwaysMaterializingDefinition(fixitValue);
     fixitDefinition.setBlock(addBefore.getBlock());
     fixitDefinition.setPosition(addBefore.getPosition());
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/JarSourceCode.java b/src/main/java/com/android/tools/r8/ir/conversion/JarSourceCode.java
index d17233f..22a5bc2 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/JarSourceCode.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/JarSourceCode.java
@@ -15,6 +15,7 @@
 import com.android.tools.r8.graph.DexProto;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.JarApplicationReader;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.CatchHandlers;
 import com.android.tools.r8.ir.code.Cmp.Bias;
 import com.android.tools.r8.ir.code.If;
@@ -278,28 +279,29 @@
     state.beginTransactionSynthetic();
 
     // Record types for arguments.
-    Int2ReferenceMap<ValueType> argumentLocals = recordArgumentTypes();
-    Int2ReferenceMap<ValueType> initializedLocals = new Int2ReferenceOpenHashMap<>(argumentLocals);
+    Int2ReferenceMap<TypeLatticeElement> argumentLocals = recordArgumentTypes(builder);
+    Int2ReferenceMap<TypeLatticeElement> initializedLocals =
+        new Int2ReferenceOpenHashMap<>(argumentLocals);
     // Initialize all non-argument locals to ensure safe insertion of debug-local instructions.
     for (Object o : node.localVariables) {
       LocalVariableNode local = (LocalVariableNode) o;
       Type localType;
-      ValueType localValueType;
+      TypeLatticeElement localValueTypeLattice;
       switch (application.getAsmType(local.desc).getSort()) {
         case Type.OBJECT:
         case Type.ARRAY: {
           localType = JarState.NULL_TYPE;
-          localValueType = ValueType.OBJECT;
+          localValueTypeLattice = TypeLatticeElement.REFERENCE;
           break;
         }
         case Type.LONG: {
           localType = Type.LONG_TYPE;
-          localValueType = ValueType.LONG;
+          localValueTypeLattice = TypeLatticeElement.LONG;
           break;
         }
         case Type.DOUBLE: {
           localType = Type.DOUBLE_TYPE;
-          localValueType = ValueType.DOUBLE;
+          localValueTypeLattice = TypeLatticeElement.DOUBLE;
           break;
         }
         case Type.BOOLEAN:
@@ -308,12 +310,12 @@
         case Type.SHORT:
         case Type.INT: {
           localType = Type.INT_TYPE;
-          localValueType = ValueType.INT;
+          localValueTypeLattice = TypeLatticeElement.INT;
           break;
         }
         case Type.FLOAT: {
           localType = Type.FLOAT_TYPE;
-          localValueType = ValueType.FLOAT;
+          localValueTypeLattice = TypeLatticeElement.FLOAT;
           break;
         }
         case Type.VOID:
@@ -322,11 +324,11 @@
           throw new Unreachable("Invalid local variable type: " );
       }
       int localRegister = state.getLocalRegister(local.index, localType);
-      ValueType existingLocalType = initializedLocals.get(localRegister);
-      if (existingLocalType == null) {
+      TypeLatticeElement existingLocalTypeLattice = initializedLocals.get(localRegister);
+      if (existingLocalTypeLattice == null) {
         int writeRegister = state.writeLocal(local.index, localType);
         assert writeRegister == localRegister;
-        initializedLocals.put(localRegister, localValueType);
+        initializedLocals.put(localRegister, localValueTypeLattice);
       }
     }
 
@@ -375,31 +377,31 @@
       builder.addThisArgument(slot.register);
     }
     for (Type type : parameterTypes) {
-      ValueType valueType = valueType(type);
+      TypeLatticeElement typeLattice = typeLattice(type);
       Slot slot = state.readLocal(argumentRegister, type);
       if (type == Type.BOOLEAN_TYPE) {
         builder.addBooleanNonThisArgument(slot.register);
       } else {
-        builder.addNonThisArgument(slot.register, valueType);
+        builder.addNonThisArgument(slot.register, typeLattice);
       }
-      argumentRegister += valueType.requiredRegisters();
+      argumentRegister += typeLattice.requiredRegisters();
     }
   }
 
-  private Int2ReferenceMap<ValueType> recordArgumentTypes() {
-    Int2ReferenceMap<ValueType> initializedLocals =
+  private Int2ReferenceMap<TypeLatticeElement> recordArgumentTypes(IRBuilder builder) {
+    Int2ReferenceMap<TypeLatticeElement> initializedLocals =
         new Int2ReferenceOpenHashMap<>(node.localVariables.size());
     int argumentRegister = 0;
     if (!isStatic()) {
       Type thisType = application.getAsmType(clazz.descriptor.toString());
       int register = state.writeLocal(argumentRegister++, thisType);
-      initializedLocals.put(register, valueType(thisType));
+      initializedLocals.put(register, typeLattice(thisType));
     }
     for (Type type : parameterTypes) {
-      ValueType valueType = valueType(type);
+      TypeLatticeElement typeLattice = typeLattice(type);
       int register = state.writeLocal(argumentRegister, type);
-      argumentRegister += valueType.requiredRegisters();
-      initializedLocals.put(register, valueType);
+      argumentRegister += typeLattice.requiredRegisters();
+      initializedLocals.put(register, typeLattice);
     }
     return initializedLocals;
   }
@@ -937,6 +939,10 @@
     }
   }
 
+  private static TypeLatticeElement typeLattice(Type type) {
+    return valueType(type).toTypeLattice();
+  }
+
   private static MemberType memberType(Type type) {
     switch (type.getSort()) {
       case Type.ARRAY:
@@ -2691,7 +2697,10 @@
     }
   }
 
-  private static void addArgument(List<ValueType> types, List<Integer> registers, Type type,
+  private static void addArgument(
+      List<ValueType> types,
+      List<Integer> registers,
+      Type type,
       Slot slot) {
     assert slot.isCompatibleWith(type);
     types.add(valueType(type));
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/LensCodeRewriter.java b/src/main/java/com/android/tools/r8/ir/conversion/LensCodeRewriter.java
index 283c163..d3b57cd 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/LensCodeRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/LensCodeRewriter.java
@@ -46,10 +46,12 @@
 import com.android.tools.r8.ir.code.Value;
 import com.android.tools.r8.shaking.VerticalClassMerger.VerticallyMergedClasses;
 import com.android.tools.r8.utils.InternalOptions;
+import com.google.common.collect.ImmutableSet;
 import java.util.ArrayList;
 import java.util.List;
 import java.util.ListIterator;
 import java.util.Map;
+import java.util.Set;
 import java.util.concurrent.ConcurrentHashMap;
 
 public class LensCodeRewriter {
@@ -69,18 +71,24 @@
     this.options = options;
   }
 
-  private Value makeOutValue(Instruction insn, IRCode code) {
+  private Value makeOutValue(
+      Instruction insn,
+      IRCode code,
+      ImmutableSet.Builder<Value> collector) {
     if (insn.outValue() == null) {
       return null;
     } else {
-      return code.createValue(insn.outType(), insn.getLocalInfo());
+      Value newValue = code.createValue(insn.outValue().getTypeLattice(), insn.getLocalInfo());
+      collector.add(newValue);
+      return newValue;
     }
   }
 
   /**
    * Replace type appearances, invoke targets and field accesses with actual definitions.
    */
-  public void rewrite(IRCode code, DexEncodedMethod method) {
+  public Set<Value> rewrite(IRCode code, DexEncodedMethod method) {
+    ImmutableSet.Builder<Value> valueCollector = ImmutableSet.builder();
     ListIterator<BasicBlock> blocks = code.blocks.listIterator();
     while (blocks.hasNext()) {
       BasicBlock block = blocks.next();
@@ -118,9 +126,7 @@
               handle, method, NOT_ARGUMENT_TO_LAMBDA_METAFACTORY);
           if (newHandle != handle) {
             ConstMethodHandle newInstruction =
-                new ConstMethodHandle(
-                    code.createValue(current.outType(), current.getLocalInfo()),
-                    newHandle);
+                new ConstMethodHandle(makeOutValue(current, code, valueCollector), newHandle);
             iterator.replaceCurrentInstruction(newInstruction);
           }
         } else if (current.isInvokeMethod()) {
@@ -144,7 +150,7 @@
             // Fix up the return type if needed.
             if (actualTarget.proto.returnType != invokedMethod.proto.returnType
                 && newInvoke.outValue() != null) {
-              Value newValue = code.createValue(newInvoke.outType(), invoke.getLocalInfo());
+              Value newValue = makeOutValue(newInvoke, code, valueCollector);
               newInvoke.outValue().replaceUsers(newValue);
               CheckCast cast =
                   new CheckCast(
@@ -202,60 +208,66 @@
           CheckCast checkCast = current.asCheckCast();
           DexType newType = graphLense.lookupType(checkCast.getType());
           if (newType != checkCast.getType()) {
-            CheckCast newCheckCast =
-                new CheckCast(makeOutValue(checkCast, code), checkCast.object(), newType);
+            CheckCast newCheckCast = new CheckCast(
+                makeOutValue(checkCast, code, valueCollector), checkCast.object(), newType);
             iterator.replaceCurrentInstruction(newCheckCast);
           }
         } else if (current.isConstClass()) {
           ConstClass constClass = current.asConstClass();
           DexType newType = graphLense.lookupType(constClass.getValue());
           if (newType != constClass.getValue()) {
-            ConstClass newConstClass = new ConstClass(makeOutValue(constClass, code), newType);
+            ConstClass newConstClass = new ConstClass(
+                makeOutValue(constClass, code, valueCollector), newType);
             iterator.replaceCurrentInstruction(newConstClass);
           }
         } else if (current.isInstanceOf()) {
           InstanceOf instanceOf = current.asInstanceOf();
           DexType newType = graphLense.lookupType(instanceOf.type());
           if (newType != instanceOf.type()) {
-            InstanceOf newInstanceOf = new InstanceOf(makeOutValue(instanceOf, code),
-                instanceOf.value(), newType);
+            InstanceOf newInstanceOf = new InstanceOf(
+                makeOutValue(instanceOf, code, valueCollector), instanceOf.value(), newType);
             iterator.replaceCurrentInstruction(newInstanceOf);
           }
         } else if (current.isInvokeMultiNewArray()) {
           InvokeMultiNewArray multiNewArray = current.asInvokeMultiNewArray();
           DexType newType = graphLense.lookupType(multiNewArray.getArrayType());
           if (newType != multiNewArray.getArrayType()) {
-            InvokeMultiNewArray newMultiNewArray = new InvokeMultiNewArray(
-                newType, makeOutValue(multiNewArray, code), multiNewArray.inValues());
+            InvokeMultiNewArray newMultiNewArray =
+                new InvokeMultiNewArray(
+                    newType,
+                    makeOutValue(multiNewArray, code, valueCollector),
+                    multiNewArray.inValues());
             iterator.replaceCurrentInstruction(newMultiNewArray);
           }
         } else if (current.isInvokeNewArray()) {
           InvokeNewArray newArray = current.asInvokeNewArray();
           DexType newType = graphLense.lookupType(newArray.getArrayType());
           if (newType != newArray.getArrayType()) {
-            InvokeNewArray newNewArray = new InvokeNewArray(newType, makeOutValue(newArray, code),
-                newArray.inValues());
+            InvokeNewArray newNewArray = new InvokeNewArray(
+                newType, makeOutValue(newArray, code, valueCollector), newArray.inValues());
             iterator.replaceCurrentInstruction(newNewArray);
           }
         } else if (current.isNewArrayEmpty()) {
           NewArrayEmpty newArrayEmpty = current.asNewArrayEmpty();
           DexType newType = graphLense.lookupType(newArrayEmpty.type);
           if (newType != newArrayEmpty.type) {
-            NewArrayEmpty newNewArray = new NewArrayEmpty(makeOutValue(newArrayEmpty, code),
-                newArrayEmpty.size(), newType);
+            NewArrayEmpty newNewArray = new NewArrayEmpty(
+                makeOutValue(newArrayEmpty, code, valueCollector), newArrayEmpty.size(), newType);
             iterator.replaceCurrentInstruction(newNewArray);
           }
         } else if (current.isNewInstance()) {
           NewInstance newInstance= current.asNewInstance();
           DexType newClazz = graphLense.lookupType(newInstance.clazz);
           if (newClazz != newInstance.clazz) {
-            NewInstance newNewInstance = new NewInstance(newClazz, makeOutValue(newInstance, code));
+            NewInstance newNewInstance = new NewInstance(
+                newClazz, makeOutValue(newInstance, code, valueCollector));
             iterator.replaceCurrentInstruction(newNewInstance);
           }
         }
       }
     }
     assert code.isConsistentSSA();
+    return valueCollector.build();
   }
 
   // If the given invoke is on the form "invoke-direct A.<init>, v0, ..." and the definition of
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/LambdaClassConstructorSourceCode.java b/src/main/java/com/android/tools/r8/ir/desugar/LambdaClassConstructorSourceCode.java
index ccccb21..2aa4630 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/LambdaClassConstructorSourceCode.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/LambdaClassConstructorSourceCode.java
@@ -8,7 +8,7 @@
 import com.android.tools.r8.ir.code.Position;
 import com.android.tools.r8.ir.code.ValueType;
 import com.android.tools.r8.ir.conversion.IRBuilder;
-import java.util.Collections;
+import com.google.common.collect.ImmutableList;
 
 // Source code representing synthesized lambda class constructor.
 // Used for stateless lambdas to instantiate singleton instance.
@@ -25,8 +25,11 @@
     int instance = nextRegister(ValueType.OBJECT);
     add(builder -> builder.addNewInstance(instance, lambda.type));
     add(builder -> builder.addInvoke(
-        Invoke.Type.DIRECT, lambda.constructor, lambda.constructor.proto,
-        Collections.singletonList(ValueType.OBJECT), Collections.singletonList(instance)));
+        Invoke.Type.DIRECT,
+        lambda.constructor,
+        lambda.constructor.proto,
+        ImmutableList.of(ValueType.OBJECT),
+        ImmutableList.of(instance)));
 
     // Assign to a field.
     add(builder -> builder.addStaticPut(instance, lambda.instanceField));
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/LambdaMainMethodSourceCode.java b/src/main/java/com/android/tools/r8/ir/desugar/LambdaMainMethodSourceCode.java
index 9d815ce..872f7ac 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/LambdaMainMethodSourceCode.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/LambdaMainMethodSourceCode.java
@@ -16,6 +16,7 @@
 import com.android.tools.r8.ir.code.Position;
 import com.android.tools.r8.ir.code.ValueType;
 import com.android.tools.r8.ir.conversion.IRBuilder;
+import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Lists;
 import java.util.ArrayList;
 import java.util.Collections;
@@ -479,7 +480,7 @@
   private int addPrimitiveUnboxing(int register, DexType primitiveType, DexType boxType) {
     DexMethod method = getUnboxMethod(primitiveType.descriptor.content[0], boxType);
 
-    List<ValueType> argValueTypes = Collections.singletonList(ValueType.OBJECT);
+    List<ValueType> argValueTypes = ImmutableList.of(ValueType.OBJECT);
     List<Integer> argRegisters = Collections.singletonList(register);
     add(builder -> builder.addInvoke(Invoke.Type.VIRTUAL,
         method, method.proto, argValueTypes, argRegisters));
@@ -502,7 +503,7 @@
     DexMethod method = factory.createMethod(boxType, proto, factory.valueOfMethodName);
 
     ValueType valueType = ValueType.fromDexType(primitiveType);
-    List<ValueType> argValueTypes = Collections.singletonList(valueType);
+    List<ValueType> argValueTypes = ImmutableList.of(valueType);
     List<Integer> argRegisters = Collections.singletonList(register);
     add(builder -> builder.addInvoke(Invoke.Type.STATIC,
         method, method.proto, argValueTypes, argRegisters));
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/LambdaRewriter.java b/src/main/java/com/android/tools/r8/ir/desugar/LambdaRewriter.java
index 9d475c3..129ed58 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/LambdaRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/LambdaRewriter.java
@@ -15,6 +15,7 @@
 import com.android.tools.r8.graph.DexProto;
 import com.android.tools.r8.graph.DexString;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.BasicBlock;
 import com.android.tools.r8.ir.code.IRCode;
 import com.android.tools.r8.ir.code.Instruction;
@@ -25,7 +26,6 @@
 import com.android.tools.r8.ir.code.NewInstance;
 import com.android.tools.r8.ir.code.StaticGet;
 import com.android.tools.r8.ir.code.Value;
-import com.android.tools.r8.ir.code.ValueType;
 import com.android.tools.r8.ir.conversion.IRConverter;
 import com.google.common.collect.BiMap;
 import com.google.common.collect.HashBiMap;
@@ -276,7 +276,8 @@
     Value lambdaInstanceValue = invoke.outValue();
     if (lambdaInstanceValue == null) {
       // The out value might be empty in case it was optimized out.
-      lambdaInstanceValue = code.createValue(ValueType.OBJECT);
+      lambdaInstanceValue = code.createValue(
+          TypeLatticeElement.fromDexType(lambdaClass.type, appInfo, true));
     }
 
     // For stateless lambdas we replace InvokeCustom instruction with StaticGet
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/StringConcatRewriter.java b/src/main/java/com/android/tools/r8/ir/desugar/StringConcatRewriter.java
index 399ae92..c805494 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/StringConcatRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/StringConcatRewriter.java
@@ -6,12 +6,14 @@
 
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.errors.CompilationError;
+import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.graph.DexCallSite;
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexProto;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.DexValue;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.BasicBlock;
 import com.android.tools.r8.ir.code.ConstString;
 import com.android.tools.r8.ir.code.IRCode;
@@ -22,7 +24,6 @@
 import com.android.tools.r8.ir.code.InvokeVirtual;
 import com.android.tools.r8.ir.code.NewInstance;
 import com.android.tools.r8.ir.code.Value;
-import com.android.tools.r8.ir.code.ValueType;
 import com.google.common.collect.Lists;
 import java.util.ArrayList;
 import java.util.Collections;
@@ -43,6 +44,7 @@
   private static final String TO_STRING = "toString";
   private static final String APPEND = "append";
 
+  private final AppInfo appInfo;
   private final DexItemFactory factory;
 
   private final DexMethod makeConcat;
@@ -54,9 +56,10 @@
   private final Map<DexType, DexMethod> paramTypeToAppendMethod = new IdentityHashMap<>();
   private final DexMethod defaultAppendMethod;
 
-  public StringConcatRewriter(DexItemFactory factory) {
-    assert factory != null;
-    this.factory = factory;
+  public StringConcatRewriter(AppInfo appInfo) {
+    this.appInfo = appInfo;
+    assert appInfo.dexItemFactory != null;
+    this.factory = appInfo.dexItemFactory;
 
     DexType factoryType = factory.createType(CONCAT_FACTORY_TYPE_DESCR);
     DexType callSiteType = factory.createType(CALLSITE_TYPE_DESCR);
@@ -159,7 +162,7 @@
     }
 
     // Collect chunks.
-    ConcatBuilder builder = new ConcatBuilder(code, blocks, instructions);
+    ConcatBuilder builder = new ConcatBuilder(appInfo, code, blocks, instructions);
     for (int i = 0; i < paramCount; i++) {
       builder.addChunk(arguments.get(i),
           paramTypeToAppendMethod.getOrDefault(parameters[i], defaultAppendMethod));
@@ -214,7 +217,7 @@
     String recipe = ((DexValue.DexValueString) recipeValue).getValue().toString();
 
     // Collect chunks and patch the instruction.
-    ConcatBuilder builder = new ConcatBuilder(code, blocks, instructions);
+    ConcatBuilder builder = new ConcatBuilder(appInfo, code, blocks, instructions);
     StringBuilder acc = new StringBuilder();
     int argIndex = 0;
     int constArgIndex = 0;
@@ -276,6 +279,7 @@
   }
 
   private final class ConcatBuilder {
+    private final AppInfo appInfo;
     private final IRCode code;
     private final ListIterator<BasicBlock> blocks;
     private final InstructionListIterator instructions;
@@ -284,7 +288,11 @@
     private final List<Chunk> chunks = new ArrayList<>();
 
     private ConcatBuilder(
-        IRCode code, ListIterator<BasicBlock> blocks, InstructionListIterator instructions) {
+        AppInfo appInfo,
+        IRCode code,
+        ListIterator<BasicBlock> blocks,
+        InstructionListIterator instructions) {
+      this.appInfo = appInfo;
       this.code = code;
       this.blocks = blocks;
       this.instructions = instructions;
@@ -328,7 +336,9 @@
       instructions.previous();
 
       // new-instance v0, StringBuilder
-      Value sbInstance = code.createValue(ValueType.OBJECT);
+      TypeLatticeElement stringBuilderTypeLattice =
+          TypeLatticeElement.fromDexType(factory.stringBuilderType, appInfo, false);
+      Value sbInstance = code.createValue(stringBuilderTypeLattice);
       appendInstruction(new NewInstance(factory.stringBuilderType, sbInstance));
 
       // invoke-direct {v0}, void StringBuilder.<init>()
@@ -349,7 +359,7 @@
       Value concatValue = invokeCustom.outValue();
       if (concatValue == null) {
         // The out value might be empty in case it was optimized out.
-        concatValue = code.createValue(ValueType.OBJECT);
+        concatValue = code.createValue(TypeLatticeElement.stringClassType(appInfo));
       }
 
       // Replace the instruction.
@@ -427,7 +437,7 @@
 
       @Override
       Value getOrCreateValue() {
-        Value value = code.createValue(ValueType.OBJECT);
+        Value value = code.createValue(TypeLatticeElement.stringClassType(appInfo));
         appendInstruction(new ConstString(value, factory.createString(str)));
         return value;
       }
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 67b6e2d..f8b85de 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
@@ -76,7 +76,6 @@
 import com.android.tools.r8.ir.code.Switch;
 import com.android.tools.r8.ir.code.Throw;
 import com.android.tools.r8.ir.code.Value;
-import com.android.tools.r8.ir.code.ValueType;
 import com.android.tools.r8.ir.code.Xor;
 import com.android.tools.r8.ir.conversion.IRConverter;
 import com.android.tools.r8.ir.conversion.OptimizationFeedback;
@@ -270,7 +269,7 @@
   // For method with many self-recursive calls, insert a try-catch to disable inlining.
   // Marshmallow dex2oat aggressively inlines and eats up all the memory on devices.
   public static void disableDex2OatInliningForSelfRecursiveMethods(
-      IRCode code, InternalOptions options) {
+      IRCode code, InternalOptions options, AppInfo appInfo) {
     if (!options.canHaveDex2OatInliningIssue() || code.hasCatchHandlers()) {
       // Catch handlers disables inlining, so if the method already has catch handlers
       // there is nothing to do.
@@ -294,11 +293,14 @@
       splitIterator.previous();
       BasicBlock newBlock = splitIterator.split(code, 1);
       // Generate rethrow block.
-      BasicBlock rethrowBlock =
-          BasicBlock.createRethrowBlock(code, lastSelfRecursiveCall.getPosition());
+      DexType guard = options.itemFactory.throwableType;
+      BasicBlock rethrowBlock = BasicBlock.createRethrowBlock(
+          code,
+          lastSelfRecursiveCall.getPosition(),
+          TypeLatticeElement.fromDexType(guard, appInfo, true));
       code.blocks.add(rethrowBlock);
       // Add catch handler to the block containing the last recursive call.
-      newBlock.addCatchHandler(rethrowBlock, options.itemFactory.throwableType);
+      newBlock.addCatchHandler(rethrowBlock, guard);
     }
   }
 
@@ -1649,35 +1651,39 @@
           && outValue.isUsed()
           && outValue.numberOfPhiUsers() == 0
           && outValue.uniqueUsers().stream().allMatch(isCheckcastToSubtype)) {
-        removeOrReplaceByDebugLocalWrite(it, inValue, outValue);
+        removeOrReplaceByDebugLocalWrite(checkCast, it, inValue, outValue);
         continue;
       }
 
       TypeLatticeElement inTypeLattice = inValue.getTypeLattice();
-      // TODO(b/72693244): Soon, there won't be a value with Bottom at this point.
-      if (!inTypeLattice.isBottom()) {
+      // TODO(b/72693244): Soon, there won't be a value with imprecise type at this point.
+      if (inTypeLattice.isPreciseType() || inTypeLattice.isNull()) {
         TypeLatticeElement outTypeLattice = outValue.getTypeLattice();
         TypeLatticeElement castTypeLattice =
-            TypeLatticeElement.fromDexType(appInfo, castType, inTypeLattice.isNullable());
-        // 1) Trivial cast.
-        //   A a = ...
-        //   A a' = (A) a;
-        // 2) Up-cast: we already have finer type info.
-        //   A < B
-        //   A a = ...
-        //   B b = (B) a;
+            TypeLatticeElement.fromDexType(castType, appInfo, inTypeLattice.isNullable());
+
+        assert inTypeLattice.nullElement().lessThanOrEqual(outTypeLattice.nullElement());
+
         if (TypeLatticeElement.lessThanOrEqual(appInfo, inTypeLattice, castTypeLattice)) {
-          assert outTypeLattice.equals(inTypeLattice);
+          // 1) Trivial cast.
+          //   A a = ...
+          //   A a' = (A) a;
+          // 2) Up-cast: we already have finer type info.
+          //   A < B
+          //   A a = ...
+          //   B b = (B) a;
+          assert TypeLatticeElement.lessThanOrEqual(appInfo, inTypeLattice, outTypeLattice);
           needToRemoveTrivialPhis = needToRemoveTrivialPhis || outValue.numberOfPhiUsers() != 0;
-          removeOrReplaceByDebugLocalWrite(it, inValue, outValue);
-          continue;
+          removeOrReplaceByDebugLocalWrite(checkCast, it, inValue, outValue);
+        } else {
+          // Otherwise, keep the checkcast to preserve verification errors. E.g., down-cast:
+          // A < B < C
+          // c = ...        // Even though we know c is of type A,
+          // a' = (B) c;    // (this could be removed, since chained below.)
+          // a'' = (A) a';  // this should remain for runtime verification.
+          assert !inTypeLattice.isNull();
+          assert outTypeLattice.asNullable().equals(castTypeLattice.asNullable());
         }
-        // Otherwise, keep the checkcast to preserve verification errors. E.g., down-cast:
-        // A < B < C
-        // c = ...        // Even though we know c is of type A,
-        // a' = (B) c;    // (this could be removed, since chained below.)
-        // a'' = (A) a';  // this should remain for runtime verification.
-        assert outTypeLattice.equals(castTypeLattice);
       }
     }
     // ... v1
@@ -1689,16 +1695,20 @@
     if (needToRemoveTrivialPhis) {
       code.removeAllTrivialPhis();
     }
-    it = code.instructionIterator();
     assert code.isConsistentSSA();
   }
 
   private void removeOrReplaceByDebugLocalWrite(
-      InstructionIterator it, Value inValue, Value outValue) {
-    if (outValue.getLocalInfo() != inValue.getLocalInfo() && outValue.hasLocalInfo()) {
+      Instruction currentInstruction, InstructionIterator it, Value inValue, Value outValue) {
+    if (outValue.hasLocalInfo() && outValue.getLocalInfo() != inValue.getLocalInfo()) {
       DebugLocalWrite debugLocalWrite = new DebugLocalWrite(outValue, inValue);
       it.replaceCurrentInstruction(debugLocalWrite);
     } else {
+      if (outValue.hasLocalInfo()) {
+        assert outValue.getLocalInfo() == inValue.getLocalInfo();
+        // Should remove the end-marker before replacing the current instruction.
+        currentInstruction.removeDebugValue(outValue.getLocalInfo());
+      }
       outValue.replaceUsers(inValue);
       it.removeOrReplaceByDebugLocalRead();
     }
@@ -2153,7 +2163,8 @@
           for (ConstInstruction value : values) {
             stringValues.add(value.outValue());
           }
-          Value invokeValue = code.createValue(newArray.outType(), newArray.getLocalInfo());
+          Value invokeValue = code.createValue(
+              newArray.outValue().getTypeLattice(), newArray.getLocalInfo());
           InvokeNewArray invoke =
               new InvokeNewArray(dexItemFactory.stringArrayType, invokeValue, stringValues);
           for (Value value : newArray.inValues()) {
@@ -2662,7 +2673,7 @@
         InstructionListIterator throwNullInsnIterator = throwNullBlock.listIterator();
 
         // Insert 'null' constant.
-        Value nullValue = code.createValue(ValueType.OBJECT, gotoInsn.getLocalInfo());
+        Value nullValue = code.createValue(TypeLatticeElement.NULL, gotoInsn.getLocalInfo());
         ConstNumber nullConstant = new ConstNumber(nullValue, 0);
         nullConstant.setPosition(insn.getPosition());
         throwNullInsnIterator.add(nullConstant);
@@ -2744,7 +2755,7 @@
                          (theIf.getType() == Type.EQ &&
                            trueNumber.isIntegerOne() &&
                            falseNumber.isIntegerZero())) {
-                Value newOutValue = code.createValue(phi.outType(), phi.getLocalInfo());
+                Value newOutValue = code.createValue(phi.getTypeLattice(), phi.getLocalInfo());
                 ConstNumber cstToUse = trueNumber.isIntegerOne() ? trueNumber : falseNumber;
                 BasicBlock phiBlock = phi.getBlock();
                 Position phiPosition = phiBlock.getPosition();
@@ -2971,7 +2982,8 @@
   }
 
   private Value addConstString(IRCode code, InstructionListIterator iterator, String s) {
-    Value value = code.createValue(ValueType.OBJECT);
+    TypeLatticeElement typeLattice = TypeLatticeElement.stringClassType(appInfo);
+    Value value = code.createValue(typeLattice);
     iterator.add(new ConstString(value, dexItemFactory.createString(s)));
     return value;
   }
@@ -2998,9 +3010,10 @@
 
     // Now that the block is split there should not be any catch handlers in the block.
     assert !block.hasCatchHandlers();
-    Value out = code.createValue(ValueType.OBJECT);
     DexType javaLangSystemType = dexItemFactory.createType("Ljava/lang/System;");
     DexType javaIoPrintStreamType = dexItemFactory.createType("Ljava/io/PrintStream;");
+    Value out = code.createValue(
+        TypeLatticeElement.fromDexType(javaIoPrintStreamType, appInfo, false));
 
     DexProto proto = dexItemFactory.createProto(dexItemFactory.voidType, dexItemFactory.objectType);
     DexMethod print = dexItemFactory.createMethod(javaIoPrintStreamType, proto, "print");
@@ -3010,11 +3023,11 @@
         new StaticGet(MemberType.OBJECT, out,
             dexItemFactory.createField(javaLangSystemType, javaIoPrintStreamType, "out")));
 
-    Value value = code.createValue(ValueType.OBJECT);
+    Value value = code.createValue(TypeLatticeElement.stringClassType(appInfo));
     iterator.add(new ConstString(value, dexItemFactory.createString("INVOKE ")));
     iterator.add(new InvokeVirtual(print, null, ImmutableList.of(out, value)));
 
-    value = code.createValue(ValueType.OBJECT);
+    value = code.createValue(TypeLatticeElement.stringClassType(appInfo));
     iterator.add(
         new ConstString(value, dexItemFactory.createString(method.method.qualifiedName())));
     iterator.add(new InvokeVirtual(print, null, ImmutableList.of(out, value)));
@@ -3040,7 +3053,7 @@
       eol.link(successor);
 
       Value argument = arguments.get(i);
-      if (argument.outType() != ValueType.OBJECT) {
+      if (!argument.getTypeLattice().isReference()) {
         iterator.add(new InvokeVirtual(print, null, ImmutableList.of(out, primitive)));
       } else {
         // Insert "if (argument != null) ...".
@@ -3068,7 +3081,7 @@
         iterator.add(new InvokeVirtual(print, null, ImmutableList.of(out, nul)));
         iterator = isNotNullBlock.listIterator();
         iterator.setInsertionPosition(position);
-        value = code.createValue(ValueType.OBJECT);
+        value = code.createValue(TypeLatticeElement.classClassType(appInfo));
         iterator.add(new InvokeVirtual(dexItemFactory.objectMethods.getClass, value,
             ImmutableList.of(arguments.get(i))));
         iterator.add(new InvokeVirtual(print, null, ImmutableList.of(out, value)));
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/Devirtualizer.java b/src/main/java/com/android/tools/r8/ir/optimize/Devirtualizer.java
index 9f57e52..37cfb44 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/Devirtualizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/Devirtualizer.java
@@ -110,12 +110,12 @@
           Value receiver = invoke.getReceiver();
           TypeLatticeElement receiverTypeLattice = receiver.getTypeLattice();
           TypeLatticeElement castTypeLattice =
-              TypeLatticeElement.fromDexType(appInfo, holderType, receiverTypeLattice.isNullable());
+              TypeLatticeElement.fromDexType(holderType, appInfo, receiverTypeLattice.isNullable());
           // Avoid adding trivial cast and up-cast.
           // We should not use strictlyLessThan(castType, receiverType), which detects downcast,
           // due to side-casts, e.g., A (unused) < I, B < I, and cast from A to B.
-          // TODO(b/72693244): Soon, there won't be a value with Bottom at this point.
-          if (receiverTypeLattice.isBottom()
+          // TODO(b/72693244): Soon, there won't be a value with imprecise type at this point.
+          if (!receiverTypeLattice.isPreciseType()
               || !TypeLatticeElement.lessThanOrEqual(
                   appInfo, receiverTypeLattice, castTypeLattice)) {
             Value newReceiver = null;
@@ -140,8 +140,8 @@
             if (newReceiver == null) {
               newReceiver =
                   receiver.definition != null
-                      ? code.createValue(receiver.outType(), receiver.definition.getLocalInfo())
-                      : code.createValue(receiver.outType());
+                      ? code.createValue(receiverTypeLattice, receiver.definition.getLocalInfo())
+                      : code.createValue(receiverTypeLattice);
               // Cache the new receiver with a narrower type to avoid redundant checkcast.
               castedReceiverCache.putIfAbsent(receiver, new IdentityHashMap<>());
               castedReceiverCache.get(receiver).put(holderType, newReceiver);
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 1a23da1..98de5be 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
@@ -13,6 +13,7 @@
 import com.android.tools.r8.graph.DexItem;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.ConstNumber;
 import com.android.tools.r8.ir.code.IRCode;
 import com.android.tools.r8.ir.code.InstancePut;
@@ -22,7 +23,6 @@
 import com.android.tools.r8.ir.code.StaticGet;
 import com.android.tools.r8.ir.code.StaticPut;
 import com.android.tools.r8.ir.code.Value;
-import com.android.tools.r8.ir.code.ValueType;
 import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
 import com.android.tools.r8.shaking.ProguardMemberRule;
 import java.util.function.Predicate;
@@ -68,19 +68,19 @@
       ProguardMemberRule rule, IRCode code, Instruction instruction) {
     // Check if this value can be assumed constant.
     Instruction replacement = null;
-    ValueType valueType = instruction.outValue().outType();
+    TypeLatticeElement typeLattice = instruction.outValue().getTypeLattice();
     if (rule != null && rule.hasReturnValue() && rule.getReturnValue().isSingleValue()) {
-      Value value = code.createValue(valueType, instruction.getLocalInfo());
-      assert valueType != ValueType.OBJECT || rule.getReturnValue().isNull();
+      Value value = code.createValue(typeLattice, instruction.getLocalInfo());
+      assert !typeLattice.isReference() || rule.getReturnValue().isNull();
       replacement = new ConstNumber(value, rule.getReturnValue().getSingleValue());
     }
     if (replacement == null &&
         rule != null && rule.hasReturnValue() && rule.getReturnValue().isField()) {
       DexField field = rule.getReturnValue().getField();
-      assert ValueType.fromDexType(field.type) == valueType;
+      assert TypeLatticeElement.fromDexType(field.type) == typeLattice;
       DexEncodedField staticField = appInfo.lookupStaticTarget(field.clazz, field);
       if (staticField != null) {
-        Value value = code.createValue(valueType, instruction.getLocalInfo());
+        Value value = code.createValue(typeLattice, instruction.getLocalInfo());
         replacement = staticField.getStaticValue().asConstInstruction(false, value);
       } else {
         throw new CompilationError(field.clazz.toSourceString() + "." + field.name.toString() +
@@ -164,8 +164,8 @@
             }
             if (target.getOptimizationInfo().returnsConstant()) {
               long constant = target.getOptimizationInfo().getReturnedConstant();
-              ValueType valueType = invoke.outType();
-              Value value = code.createValue(valueType, invoke.getLocalInfo());
+              Value value = code.createValue(
+                  invoke.outValue().getTypeLattice(), invoke.getLocalInfo());
               Instruction knownConstReturn = new ConstNumber(value, constant);
               invoke.outValue().replaceUsers(value);
               invoke.setOutValue(null);
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 536eac8..eed1c47 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
@@ -16,7 +16,6 @@
 import com.android.tools.r8.ir.code.NonNull;
 import com.android.tools.r8.ir.code.Phi;
 import com.android.tools.r8.ir.code.Value;
-import com.android.tools.r8.ir.code.ValueType;
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Sets;
@@ -119,9 +118,9 @@
         // ...
         // A: non_null_rcv <- non-null(rcv)
         // ...y
-        // TODO(b/72693244): Attach lattice when Value is created.
-        Value nonNullValue =
-            code.createValue(ValueType.OBJECT, knownToBeNonNullValue.getLocalInfo());
+        Value nonNullValue = code.createValue(
+            knownToBeNonNullValue.getTypeLattice(),
+            knownToBeNonNullValue.getLocalInfo());
         nonNullValueCollector.add(nonNullValue);
         NonNull nonNull = new NonNull(nonNullValue, knownToBeNonNullValue, current);
         nonNull.setPosition(current.getPosition());
@@ -219,9 +218,9 @@
               }
               // Avoid adding a non-null for the value without meaningful users.
               if (!dominatedUsers.isEmpty() || !dominatedPhiUsersWithPositions.isEmpty()) {
-                // TODO(b/72693244): Attach lattice when Value is created.
                 Value nonNullValue = code.createValue(
-                    knownToBeNonNullValue.outType(), knownToBeNonNullValue.getLocalInfo());
+                    knownToBeNonNullValue.getTypeLattice(),
+                    knownToBeNonNullValue.getLocalInfo());
                 nonNullValueCollector.add(nonNullValue);
                 NonNull nonNull = new NonNull(nonNullValue, knownToBeNonNullValue, theIf);
                 InstructionListIterator targetIterator = target.listIterator();
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/Outliner.java b/src/main/java/com/android/tools/r8/ir/optimize/Outliner.java
index e02222f..708dc12 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/Outliner.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/Outliner.java
@@ -24,6 +24,7 @@
 import com.android.tools.r8.graph.MethodAccessFlags;
 import com.android.tools.r8.graph.ParameterAnnotationsList;
 import com.android.tools.r8.graph.UseRegistry;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.Add;
 import com.android.tools.r8.ir.code.BasicBlock;
 import com.android.tools.r8.ir.code.BasicBlock.ThrowingInfo;
@@ -1031,8 +1032,8 @@
     public void buildPrelude(IRBuilder builder) {
       // Fill in the Argument instructions in the argument block.
       for (int i = 0; i < outline.arguments.size(); i++) {
-        ValueType valueType = outline.arguments.get(i).outType();
-        builder.addNonThisArgument(i, valueType);
+        TypeLatticeElement typeLattice = outline.arguments.get(i).getTypeLattice();
+        builder.addNonThisArgument(i, typeLattice);
       }
     }
 
@@ -1076,8 +1077,8 @@
       Value outValue = null;
       if (template.outValue() != null) {
         Value value = template.outValue();
-        outValue = builder
-            .writeRegister(outline.argumentCount(), value.outType(), ThrowingInfo.CAN_THROW);
+        outValue = builder.writeRegister(
+            outline.argumentCount(), value.getTypeLattice(), ThrowingInfo.CAN_THROW);
       }
 
       Instruction newInstruction = null;
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/classinliner/ClassInliner.java b/src/main/java/com/android/tools/r8/ir/optimize/classinliner/ClassInliner.java
index 0ef4597..6999f9a 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/classinliner/ClassInliner.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/classinliner/ClassInliner.java
@@ -137,6 +137,7 @@
     // of roots to avoid infinite inlining. Looping makes possible for some roots to
     // become eligible after other roots are inlined.
 
+    boolean anyInlinedMethods = false;
     boolean repeat;
     do {
       repeat = false;
@@ -169,18 +170,24 @@
         }
 
         // Inline the class instance.
-        boolean anyInlinedMethods = processor.processInlining(code, inliner);
+        anyInlinedMethods |= processor.processInlining(code, inliner);
 
         // Restore normality.
         code.removeAllTrivialPhis();
         assert code.isConsistentSSA();
-        if (anyInlinedMethods) {
-          codeRewriter.simplifyIf(code);
-        }
         rootsIterator.remove();
         repeat = true;
       }
     } while (repeat);
+
+    if (anyInlinedMethods) {
+      // If a method was inlined we may be able to remove check-cast instructions because we may
+      // have more information about the types of the arguments at the call site. This is
+      // particularly important for bridge methods.
+      codeRewriter.removeCasts(code);
+      // If a method was inlined we may be able to prune additional branches.
+      codeRewriter.simplifyIf(code);
+    }
   }
 
   private boolean isClassEligible(AppInfo appInfo, DexClass clazz) {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/classinliner/FieldValueHelper.java b/src/main/java/com/android/tools/r8/ir/optimize/classinliner/FieldValueHelper.java
index 714c28b..8ed50ce 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/classinliner/FieldValueHelper.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/classinliner/FieldValueHelper.java
@@ -5,6 +5,7 @@
 package com.android.tools.r8.ir.optimize.classinliner;
 
 import com.android.tools.r8.graph.DexField;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.BasicBlock;
 import com.android.tools.r8.ir.code.ConstNumber;
 import com.android.tools.r8.ir.code.IRCode;
@@ -13,7 +14,6 @@
 import com.android.tools.r8.ir.code.Phi;
 import com.android.tools.r8.ir.code.Phi.RegisterReadType;
 import com.android.tools.r8.ir.code.Value;
-import com.android.tools.r8.ir.code.ValueType;
 import java.util.ArrayList;
 import java.util.IdentityHashMap;
 import java.util.LinkedList;
@@ -89,7 +89,7 @@
           new Phi(
               code.valueNumberGenerator.next(),
               block,
-              ValueType.fromDexType(field.type),
+              TypeLatticeElement.fromDexType(field.type),
               null,
               RegisterReadType.NORMAL);
       ins.put(block, phi);
@@ -137,7 +137,7 @@
     assert root == valueProducingInsn;
     if (defaultValue == null) {
       // If we met newInstance it means that default value is supposed to be used.
-      defaultValue = code.createValue(ValueType.fromDexType(field.type));
+      defaultValue = code.createValue(TypeLatticeElement.fromDexType(field.type));
       ConstNumber defaultValueInsn = new ConstNumber(defaultValue, 0);
       defaultValueInsn.setPosition(root.getPosition());
       LinkedList<Instruction> instructions = block.getInstructions();
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/lambda/CodeProcessor.java b/src/main/java/com/android/tools/r8/ir/optimize/lambda/CodeProcessor.java
index eb7826e..030cd4f 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/lambda/CodeProcessor.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/lambda/CodeProcessor.java
@@ -5,6 +5,7 @@
 package com.android.tools.r8.ir.optimize.lambda;
 
 import com.android.tools.r8.errors.Unreachable;
+import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexField;
 import com.android.tools.r8.graph.DexItemFactory;
@@ -139,6 +140,7 @@
     }
   };
 
+  public final AppInfo appInfo;
   public final DexItemFactory factory;
   public final Kotlin kotlin;
 
@@ -156,13 +158,15 @@
   public final ListIterator<BasicBlock> blocks;
   private InstructionListIterator instructions;
 
-  CodeProcessor(DexItemFactory factory,
+  CodeProcessor(
+      AppInfo appInfo,
       Function<DexType, Strategy> strategyProvider,
       LambdaTypeVisitor lambdaChecker,
       DexEncodedMethod method, IRCode code) {
 
+    this.appInfo = appInfo;
     this.strategyProvider = strategyProvider;
-    this.factory = factory;
+    this.factory = appInfo.dexItemFactory;
     this.kotlin = factory.kotlin;
     this.lambdaChecker = lambdaChecker;
     this.method = method;
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 d1b56f2..270f8ba 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
@@ -6,6 +6,7 @@
 
 import com.android.tools.r8.DiagnosticsHandler;
 import com.android.tools.r8.errors.Unreachable;
+import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.DexApplication;
 import com.android.tools.r8.graph.DexApplication.Builder;
@@ -98,6 +99,7 @@
   // should not be happening very frequently and we ignore possible overhead.
   private final Set<DexEncodedMethod> methodsToReprocess = Sets.newIdentityHashSet();
 
+  private final AppInfo appInfo;
   private final DexItemFactory factory;
   private final Kotlin kotlin;
   private final DiagnosticsHandler reporter;
@@ -109,8 +111,9 @@
   // Lambda visitor throwing Unreachable on each lambdas it sees.
   private final LambdaTypeVisitor lambdaChecker;
 
-  public LambdaMerger(DexItemFactory factory, DiagnosticsHandler reporter) {
-    this.factory = factory;
+  public LambdaMerger(AppInfo appInfo, DiagnosticsHandler reporter) {
+    this.appInfo = appInfo;
+    this.factory = appInfo.dexItemFactory;
     this.kotlin = factory.kotlin;
     this.reporter = reporter;
 
@@ -346,7 +349,7 @@
 
   private final class AnalysisStrategy extends CodeProcessor {
     private AnalysisStrategy(DexEncodedMethod method, IRCode code) {
-      super(LambdaMerger.this.factory,
+      super(LambdaMerger.this.appInfo,
           LambdaMerger.this::strategyProvider, lambdaInvalidator, method, code);
     }
 
@@ -383,7 +386,7 @@
 
   private final class ApplyStrategy extends CodeProcessor {
     private ApplyStrategy(DexEncodedMethod method, IRCode code) {
-      super(LambdaMerger.this.factory,
+      super(LambdaMerger.this.appInfo,
           LambdaMerger.this::strategyProvider, lambdaChecker, method, code);
     }
 
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/ClassInitializerSourceCode.java b/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/ClassInitializerSourceCode.java
index 19d6bda..5177e4a 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/ClassInitializerSourceCode.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/ClassInitializerSourceCode.java
@@ -8,6 +8,7 @@
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.DexTypeList;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.Invoke.Type;
 import com.android.tools.r8.ir.code.Position;
 import com.android.tools.r8.ir.code.ValueType;
@@ -45,7 +46,7 @@
       if (group.isSingletonLambda(lambda)) {
         int id = group.lambdaId(lambda);
         add(builder -> builder.addNewInstance(instance, groupClassType));
-        add(builder -> builder.addConst(ValueType.INT, lambdaId, id));
+        add(builder -> builder.addConst(TypeLatticeElement.INT, lambdaId, id));
         add(builder -> builder.addInvoke(Type.DIRECT,
             lambdaConstructorMethod, lambdaConstructorMethod.proto, argTypes, argRegisters));
         add(builder -> builder.addStaticPut(
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/KStyleLambdaGroup.java b/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/KStyleLambdaGroup.java
index 76bf797..f677b46 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/KStyleLambdaGroup.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/KStyleLambdaGroup.java
@@ -17,6 +17,7 @@
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.EnclosingMethodAttribute;
 import com.android.tools.r8.graph.InnerClassAttribute;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.Invoke.Type;
 import com.android.tools.r8.ir.code.Position;
 import com.android.tools.r8.ir.code.ValueType;
@@ -231,7 +232,7 @@
     @Override
     void prepareSuperConstructorCall(int receiverRegister) {
       int arityRegister = nextRegister(ValueType.INT);
-      add(builder -> builder.addConst(ValueType.INT, arityRegister, arity));
+      add(builder -> builder.addConst(TypeLatticeElement.INT, arityRegister, arity));
       add(builder -> builder.addInvoke(Type.DIRECT, lambdaInitializer, lambdaInitializer.proto,
           Lists.newArrayList(ValueType.OBJECT, ValueType.INT),
           Lists.newArrayList(receiverRegister, arityRegister)));
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/KotlinLambdaGroupCodeStrategy.java b/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/KotlinLambdaGroupCodeStrategy.java
index e265756..538d7be 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/KotlinLambdaGroupCodeStrategy.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/KotlinLambdaGroupCodeStrategy.java
@@ -10,6 +10,7 @@
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexProto;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.CheckCast;
 import com.android.tools.r8.ir.code.ConstNumber;
 import com.android.tools.r8.ir.code.InstanceGet;
@@ -22,7 +23,6 @@
 import com.android.tools.r8.ir.code.StaticGet;
 import com.android.tools.r8.ir.code.StaticPut;
 import com.android.tools.r8.ir.code.Value;
-import com.android.tools.r8.ir.code.ValueType;
 import com.android.tools.r8.ir.optimize.lambda.CaptureSignature;
 import com.android.tools.r8.ir.optimize.lambda.CodeProcessor;
 import com.android.tools.r8.ir.optimize.lambda.CodeProcessor.Strategy;
@@ -113,7 +113,9 @@
   @Override
   public void patch(CodeProcessor context, NewInstance newInstance) {
     NewInstance patchedNewInstance = new NewInstance(
-        group.getGroupClassType(), context.code.createValue(ValueType.OBJECT));
+        group.getGroupClassType(),
+        context.code.createValue(
+            TypeLatticeElement.fromDexType(newInstance.clazz, context.appInfo, false)));
     context.instructions().replaceCurrentInstruction(patchedNewInstance);
   }
 
@@ -157,7 +159,9 @@
 
     // Since all captured values of non-primitive types are stored in fields of type
     // java.lang.Object, we need to cast them to appropriate type to satisfy the verifier.
-    Value newValue = context.code.createValue(ValueType.OBJECT, newInstanceGet.getLocalInfo());
+    TypeLatticeElement castTypeLattice =
+        TypeLatticeElement.fromDexType(fieldType, context.appInfo, false);
+    Value newValue = context.code.createValue(castTypeLattice, newInstanceGet.getLocalInfo());
     newInstanceGet.outValue().replaceUsers(newValue);
     CheckCast cast = new CheckCast(newValue, newInstanceGet.outValue(), fieldType);
     cast.setPosition(newInstanceGet.getPosition());
@@ -180,7 +184,10 @@
   @Override
   public void patch(CodeProcessor context, StaticGet staticGet) {
     context.instructions().replaceCurrentInstruction(
-        new StaticGet(staticGet.getType(), context.code.createValue(ValueType.OBJECT),
+        new StaticGet(
+            staticGet.getType(),
+            context.code.createValue(
+                TypeLatticeElement.fromDexType(staticGet.getField().type, context.appInfo, true)),
             mapSingletonInstanceField(context.factory, staticGet.getField())));
   }
 
@@ -195,7 +202,7 @@
     DexType lambda = method.holder;
 
     // Create constant with lambda id.
-    Value lambdaIdValue = context.code.createValue(ValueType.INT);
+    Value lambdaIdValue = context.code.createValue(TypeLatticeElement.INT);
     ConstNumber lambdaId = new ConstNumber(lambdaIdValue, group.lambdaId(lambda));
     lambdaId.setPosition(invoke.getPosition());
     context.instructions().previous();
@@ -214,7 +221,8 @@
 
   private Value createValueForType(CodeProcessor context, DexType returnType) {
     return returnType == context.factory.voidType ? null :
-        context.code.createValue(ValueType.fromDexType(returnType));
+        context.code.createValue(
+            TypeLatticeElement.fromDexType(returnType, context.appInfo, true));
   }
 
   private List<Value> mapInitializerArgs(
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 916679d..669baf9 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
@@ -14,6 +14,7 @@
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexProgramClass;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.IRCode;
 import com.android.tools.r8.ir.code.Instruction;
 import com.android.tools.r8.ir.code.InstructionIterator;
@@ -23,7 +24,6 @@
 import com.android.tools.r8.ir.code.StaticGet;
 import com.android.tools.r8.ir.code.StaticPut;
 import com.android.tools.r8.ir.code.Value;
-import com.android.tools.r8.ir.code.ValueType;
 import com.android.tools.r8.ir.conversion.CallSiteInformation;
 import com.android.tools.r8.ir.conversion.OptimizationFeedback;
 import com.android.tools.r8.ir.optimize.Outliner;
@@ -244,7 +244,7 @@
       Value newValue = null;
       Value outValue = invoke.outValue();
       if (outValue != null) {
-        newValue = code.createValue(outValue.outType());
+        newValue = code.createValue(outValue.getTypeLattice());
         DebugLocalInfo localInfo = outValue.getLocalInfo();
         if (localInfo != null) {
           newValue.setLocalInfo(localInfo);
@@ -272,7 +272,9 @@
           it.replaceCurrentInstruction(
               new StaticGet(
                   MemberType.fromDexType(field.type),
-                  code.createValue(ValueType.fromDexType(field.type), outValue.getLocalInfo()),
+                  code.createValue(
+                      TypeLatticeElement.fromDexType(field.type, classStaticizer.appInfo, true),
+                      outValue.getLocalInfo()),
                   field
               )
           );
@@ -300,7 +302,8 @@
           Value outValue = invoke.outValue();
           Value newOutValue = method.proto.returnType.isVoidType() ? null
               : code.createValue(
-                  ValueType.fromDexType(method.proto.returnType),
+                  TypeLatticeElement.fromDexType(
+                      method.proto.returnType, classStaticizer.appInfo, true),
                   outValue == null ? null : outValue.getLocalInfo());
           it.replaceCurrentInstruction(
               new InvokeStatic(newMethod, newOutValue, invoke.inValues()));
diff --git a/src/main/java/com/android/tools/r8/ir/regalloc/LinearScanRegisterAllocator.java b/src/main/java/com/android/tools/r8/ir/regalloc/LinearScanRegisterAllocator.java
index b4995c9..9345bb9 100644
--- a/src/main/java/com/android/tools/r8/ir/regalloc/LinearScanRegisterAllocator.java
+++ b/src/main/java/com/android/tools/r8/ir/regalloc/LinearScanRegisterAllocator.java
@@ -10,6 +10,7 @@
 import com.android.tools.r8.cf.FixedLocalValue;
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.graph.DebugLocalInfo;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.Add;
 import com.android.tools.r8.ir.code.And;
 import com.android.tools.r8.ir.code.ArithmeticBinop;
@@ -27,7 +28,6 @@
 import com.android.tools.r8.ir.code.Phi;
 import com.android.tools.r8.ir.code.Sub;
 import com.android.tools.r8.ir.code.Value;
-import com.android.tools.r8.ir.code.ValueType;
 import com.android.tools.r8.ir.code.Xor;
 import com.android.tools.r8.ir.regalloc.RegisterPositions.Type;
 import com.android.tools.r8.logging.Log;
@@ -2673,8 +2673,8 @@
     return true;
   }
 
-  private Value createValue(ValueType type) {
-    Value value = code.createValue(type, null);
+  private Value createValue(TypeLatticeElement typeLattice) {
+    Value value = code.createValue(typeLattice, null);
     value.setNeedsRegister(true);
     return value;
   }
@@ -2726,7 +2726,7 @@
             argument.isLinked() ||
             argument == previous ||
             argument.hasRegisterConstraint()) {
-          newArgument = createValue(argument.outType());
+          newArgument = createValue(argument.getTypeLattice());
           Move move = new Move(newArgument, argument);
           move.setBlock(invoke.getBlock());
           replaceArgument(invoke, i, newArgument);
diff --git a/src/main/java/com/android/tools/r8/ir/regalloc/RegisterMoveScheduler.java b/src/main/java/com/android/tools/r8/ir/regalloc/RegisterMoveScheduler.java
index 031d161..daa1e30 100644
--- a/src/main/java/com/android/tools/r8/ir/regalloc/RegisterMoveScheduler.java
+++ b/src/main/java/com/android/tools/r8/ir/regalloc/RegisterMoveScheduler.java
@@ -139,22 +139,25 @@
       if (move.definition.isArgument()) {
         Argument argument = move.definition.asArgument();
         int argumentRegister = argument.outValue().getLiveIntervals().getRegister();
-        Value to = new FixedRegisterValue(argument.outType(), move.dst);
-        Value from = new FixedRegisterValue(argument.outType(), argumentRegister);
+        Value to =
+            new FixedRegisterValue(argument.outValue().getTypeLattice(), move.dst);
+        Value from =
+            new FixedRegisterValue(argument.outValue().getTypeLattice(), argumentRegister);
         instruction = new Move(to, from);
       } else {
         assert move.definition.isOutConstant();
         ConstInstruction definition = move.definition.getOutConstantConstInstruction();
         if (definition.isConstNumber()) {
-          Value to = new FixedRegisterValue(move.definition.outType(), move.dst);
+          Value to =
+              new FixedRegisterValue(move.definition.outValue().getTypeLattice(), move.dst);
           instruction = new ConstNumber(to, definition.asConstNumber().getRawValue());
         } else {
           throw new Unreachable("Unexpected definition");
         }
       }
     } else {
-      Value to = new FixedRegisterValue(move.type.toValueType(), move.dst);
-      Value from = new FixedRegisterValue(move.type.toValueType(), valueMap.get(move.src));
+      Value to = new FixedRegisterValue(move.type.toTypeLattice(), move.dst);
+      Value from = new FixedRegisterValue(move.type.toTypeLattice(), valueMap.get(move.src));
       instruction = new Move(to, from);
     }
     instruction.setPosition(position);
@@ -176,9 +179,9 @@
       // (taking the value map into account). If not, we can reuse the temp register instead
       // of generating a new one.
       Value to = new FixedRegisterValue(
-          moveWithSrc.type.toValueType(), tempRegister + usedTempRegisters);
+          moveWithSrc.type.toTypeLattice(), tempRegister + usedTempRegisters);
       Value from = new FixedRegisterValue(
-          moveWithSrc.type.toValueType(), valueMap.get(moveWithSrc.src));
+          moveWithSrc.type.toTypeLattice(), valueMap.get(moveWithSrc.src));
       Move instruction = new Move(to, from);
       instruction.setPosition(position);
       insertAt.add(instruction);
diff --git a/src/main/java/com/android/tools/r8/ir/synthetic/SyntheticSourceCode.java b/src/main/java/com/android/tools/r8/ir/synthetic/SyntheticSourceCode.java
index cd9824f..164e083 100644
--- a/src/main/java/com/android/tools/r8/ir/synthetic/SyntheticSourceCode.java
+++ b/src/main/java/com/android/tools/r8/ir/synthetic/SyntheticSourceCode.java
@@ -11,6 +11,7 @@
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexProto;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.Argument;
 import com.android.tools.r8.ir.code.CatchHandlers;
 import com.android.tools.r8.ir.code.Position;
@@ -177,7 +178,8 @@
   @Override
   public final void buildPrelude(IRBuilder builder) {
     if (receiver != null) {
-      receiverValue = builder.writeRegister(receiverRegister, ValueType.OBJECT, NO_THROW);
+      receiverValue = builder.writeRegister(
+          receiverRegister, TypeLatticeElement.fromDexType(receiver), NO_THROW);
       builder.add(new Argument(receiverValue));
       receiverValue.markAsThis();
     }
@@ -185,8 +187,8 @@
     // Fill in the Argument instructions in the argument block.
     DexType[] parameters = proto.parameters.values;
     for (int i = 0; i < parameters.length; i++) {
-      ValueType valueType = ValueType.fromDexType(parameters[i]);
-      Value paramValue = builder.writeRegister(paramRegisters[i], valueType, NO_THROW);
+      TypeLatticeElement typeLattice = TypeLatticeElement.fromDexType(parameters[i]);
+      Value paramValue = builder.writeRegister(paramRegisters[i], typeLattice, NO_THROW);
       paramValues[i] = paramValue;
       builder.add(new Argument(paramValue));
     }
diff --git a/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java b/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java
index 37e6de9..051b81f 100644
--- a/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java
@@ -42,6 +42,7 @@
 import java.util.Map;
 import java.util.Map.Entry;
 import java.util.Set;
+import java.util.function.BiConsumer;
 import java.util.function.Consumer;
 import java.util.stream.Collectors;
 
@@ -188,8 +189,11 @@
     }
   }
 
-  private void parseError(DexDefinition item, Origin origin, GenericSignatureFormatError e) {
-    StringBuilder message = new StringBuilder("Invalid signature for ");
+  private void parseError(
+      DexDefinition item, Origin origin, String signature, GenericSignatureFormatError e) {
+    StringBuilder message = new StringBuilder("Invalid signature '");
+    message.append(signature);
+    message.append("' for ");
     if (item.isDexClass()) {
       message.append("class ");
       message.append((item.asDexClass()).getType().toSourceString());
@@ -202,43 +206,54 @@
       message.append(item.toSourceString());
     }
     message.append(".\n");
+    message.append("Signature is ignored and will not be present in the output.\n");
+    message.append("Parser error: ");
     message.append(e.getMessage());
     reporter.warning(new StringDiagnostic(message.toString(), origin));
   }
 
   private void renameTypesInGenericSignatures() {
     for (DexClass clazz : appInfo.classes()) {
-      clazz.annotations = rewriteGenericSignatures(clazz.annotations,
-          genericSignatureParser::parseClassSignature,
-          e -> parseError(clazz, clazz.getOrigin(), e));
-      clazz.forEachField(field ->
-          field.annotations = rewriteGenericSignatures(
-              field.annotations, genericSignatureParser::parseFieldSignature,
-              e -> parseError(field, clazz.getOrigin(), e)));
-      clazz.forEachMethod(method ->
-        method.annotations = rewriteGenericSignatures(
-            method.annotations, genericSignatureParser::parseMethodSignature,
-            e -> parseError(method, clazz.getOrigin(), e)));
+      clazz.annotations =
+          rewriteGenericSignatures(
+              clazz.annotations,
+              genericSignatureParser::parseClassSignature,
+              (signature, e) -> parseError(clazz, clazz.getOrigin(), signature, e));
+      clazz.forEachField(
+          field ->
+              field.annotations =
+                  rewriteGenericSignatures(
+                      field.annotations,
+                      genericSignatureParser::parseFieldSignature,
+                      (signature, e) -> parseError(field, clazz.getOrigin(), signature, e)));
+      clazz.forEachMethod(
+          method ->
+              method.annotations =
+                  rewriteGenericSignatures(
+                      method.annotations,
+                      genericSignatureParser::parseMethodSignature,
+                      (signature, e) -> parseError(method, clazz.getOrigin(), signature, e)));
     }
   }
 
   private DexAnnotationSet rewriteGenericSignatures(
       DexAnnotationSet annotations,
       Consumer<String> parser,
-      Consumer<GenericSignatureFormatError> parseError) {
+      BiConsumer<String, GenericSignatureFormatError> parseError) {
     // There can be no more than one signature annotation in an annotation set.
     final int VALID = -1;
     int invalid = VALID;
     for (int i = 0; i < annotations.annotations.length && invalid == VALID; i++) {
       DexAnnotation annotation = annotations.annotations[i];
       if (DexAnnotation.isSignatureAnnotation(annotation, appInfo.dexItemFactory)) {
+        String signature = DexAnnotation.getSignature(annotation);
         try {
-          parser.accept(DexAnnotation.getSignature(annotation));
+          parser.accept(signature);
           annotations.annotations[i] = DexAnnotation.createSignatureAnnotation(
               genericSignatureRewriter.getRenamedSignature(),
               appInfo.dexItemFactory);
         } catch (GenericSignatureFormatError e) {
-          parseError.accept(e);
+          parseError.accept(signature, e);
           invalid = i;
         }
       }
diff --git a/src/main/java/com/android/tools/r8/naming/IdentifierNameStringMarker.java b/src/main/java/com/android/tools/r8/naming/IdentifierNameStringMarker.java
index 8f9e2f5..59e0782 100644
--- a/src/main/java/com/android/tools/r8/naming/IdentifierNameStringMarker.java
+++ b/src/main/java/com/android/tools/r8/naming/IdentifierNameStringMarker.java
@@ -130,7 +130,7 @@
           assert iterator.peekPrevious() == fieldPut;
           iterator.previous();
           // Prepare $decoupled just before $fieldPut
-          Value newIn = code.createValue(in.outType(), in.getLocalInfo());
+          Value newIn = code.createValue(in.getTypeLattice(), in.getLocalInfo());
           ConstString decoupled = new ConstString(newIn, itemBasedString);
           decoupled.setPosition(fieldPut.getPosition());
           // If the current block has catch handler, split into two blocks.
@@ -192,7 +192,7 @@
             assert iterator.peekPrevious() == invoke;
             iterator.previous();
             // Prepare $decoupled just before $invoke
-            Value newIn = code.createValue(in.outType(), in.getLocalInfo());
+            Value newIn = code.createValue(in.getTypeLattice(), in.getLocalInfo());
             ConstString decoupled = new ConstString(newIn, itemBasedString);
             decoupled.setPosition(invoke.getPosition());
             changes[positionOfIdentifier] = newIn;
@@ -239,7 +239,7 @@
               assert iterator.peekPrevious() == invoke;
               iterator.previous();
               // Prepare $decoupled just before $invoke
-              Value newIn = code.createValue(in.outType(), in.getLocalInfo());
+              Value newIn = code.createValue(in.getTypeLattice(), in.getLocalInfo());
               ConstString decoupled = new ConstString(newIn, itemBasedString);
               decoupled.setPosition(invoke.getPosition());
               changes[i] = newIn;
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 9145de1..bfb2b95 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -11,6 +11,7 @@
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.AppInfo.ResolutionResult;
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
+import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.Descriptor;
 import com.android.tools.r8.graph.DexAnnotation;
 import com.android.tools.r8.graph.DexApplication;
@@ -95,7 +96,7 @@
   private boolean tracingMainDex = false;
 
   private final AppInfoWithSubtyping appInfo;
-  private final GraphLense graphLense;
+  private final AppView<? extends AppInfoWithSubtyping> appView;
   private final InternalOptions options;
   private RootSet rootSet;
 
@@ -220,25 +221,34 @@
    */
   private final ProguardConfiguration.Builder compatibility;
 
-  public Enqueuer(
-      AppInfoWithSubtyping appInfo,
-      GraphLense graphLense,
-      InternalOptions options,
-      boolean forceProguardCompatibility) {
-    this(appInfo, graphLense, options, forceProguardCompatibility, null);
+  public Enqueuer(AppView<? extends AppInfoWithSubtyping> appView, InternalOptions options) {
+    this(appView, options, options.forceProguardCompatibility, null);
   }
 
   public Enqueuer(
-      AppInfoWithSubtyping appInfo,
-      GraphLense graphLense,
+      AppView<? extends AppInfoWithSubtyping> appView,
+      InternalOptions options,
+      ProguardConfiguration.Builder compatibility) {
+    this(appView, options, options.forceProguardCompatibility, compatibility);
+  }
+
+  public Enqueuer(
+      AppView<? extends AppInfoWithSubtyping> appView,
+      InternalOptions options,
+      boolean forceProguardCompatibility) {
+    this(appView, options, forceProguardCompatibility, null);
+  }
+
+  public Enqueuer(
+      AppView<? extends AppInfoWithSubtyping> appView,
       InternalOptions options,
       boolean forceProguardCompatibility,
       ProguardConfiguration.Builder compatibility) {
-    this.appInfo = appInfo;
-    this.graphLense = graphLense;
+    this.appInfo = appView.appInfo();
+    this.appView = appView;
     this.compatibility = compatibility;
-    this.options = options;
     this.forceProguardCompatibility = forceProguardCompatibility;
+    this.options = options;
   }
 
   private void enqueueRootItems(Map<DexDefinition, ProguardKeepRule> items) {
@@ -1272,7 +1282,7 @@
         numOfLiveItemsAfterProcessing += (long) liveFields.items.size();
         if (numOfLiveItemsAfterProcessing > numOfLiveItems) {
           RootSetBuilder consequentSetBuilder =
-              new RootSetBuilder(appInfo, rootSet.ifRules, options);
+              new RootSetBuilder(appView, rootSet.ifRules, options);
           ConsequentRootSet consequentRootSet = consequentSetBuilder.runForIfRules(
               executorService, liveTypes, liveMethods.getItems(), liveFields.getItems());
           enqueueRootItems(consequentRootSet.noShrinking);
@@ -1518,7 +1528,7 @@
   private void handleReflectiveBehavior(DexEncodedMethod method) {
     DexType originHolder = method.method.holder;
     Origin origin = appInfo.originFor(originHolder);
-    IRCode code = method.buildIR(appInfo, graphLense, options, origin);
+    IRCode code = method.buildIR(appInfo, appView.graphLense(), options, origin);
     code.instructionIterator().forEachRemaining(this::handleReflectiveBehavior);
   }
 
diff --git a/src/main/java/com/android/tools/r8/shaking/ProguardClassSpecification.java b/src/main/java/com/android/tools/r8/shaking/ProguardClassSpecification.java
index 5d610a8..2aff5df 100644
--- a/src/main/java/com/android/tools/r8/shaking/ProguardClassSpecification.java
+++ b/src/main/java/com/android/tools/r8/shaking/ProguardClassSpecification.java
@@ -320,11 +320,12 @@
   }
 
   protected StringBuilder append(StringBuilder builder, boolean includeMemberRules) {
-    StringUtils.appendNonEmpty(builder, "@", classAnnotation, null);
-    StringUtils.appendNonEmpty(builder, "", classAccessFlags, null);
-    StringUtils.appendNonEmpty(builder, "!", negatedClassAccessFlags.toString().replace(" ", " !"),
-        null);
-    if (builder.length() > 0) {
+    boolean needsSpaceBeforeClassType =
+        StringUtils.appendNonEmpty(builder, "@", classAnnotation, null)
+            | StringUtils.appendNonEmpty(builder, "", classAccessFlags, null)
+            | StringUtils.appendNonEmpty(
+                builder, "!", negatedClassAccessFlags.toString().replace(" ", " !"), null);
+    if (needsSpaceBeforeClassType) {
       builder.append(' ');
     }
     if (classTypeNegated) {
@@ -339,12 +340,12 @@
       builder.append(' ');
       builder.append(inheritanceClassName);
     }
-    if (includeMemberRules) {
-      builder.append(" {\n");
+    if (includeMemberRules && !memberRules.isEmpty()) {
+      builder.append(" {").append(System.lineSeparator());
       memberRules.forEach(memberRule -> {
         builder.append("  ");
         builder.append(memberRule);
-        builder.append(";\n");
+        builder.append(";").append(System.lineSeparator());
       });
       builder.append("}");
     }
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 30def9e..e6f6a17 100644
--- a/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java
+++ b/src/main/java/com/android/tools/r8/shaking/RootSetBuilder.java
@@ -6,6 +6,7 @@
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.AppInfo;
+import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexAnnotation;
 import com.android.tools.r8.graph.DexAnnotationSet;
 import com.android.tools.r8.graph.DexApplication;
@@ -51,7 +52,7 @@
 
 public class RootSetBuilder {
 
-  private final AppInfo appInfo;
+  private final AppView<? extends AppInfo> appView;
   private final DirectMappedDexApplication application;
   private final Collection<ProguardConfigurationRule> rules;
   private final Map<DexDefinition, ProguardKeepRule> noShrinking = new IdentityHashMap<>();
@@ -76,22 +77,20 @@
   private final Set<ProguardIfRule> ifRules = Sets.newIdentityHashSet();
 
   public RootSetBuilder(
-      AppInfo appInfo,
+      AppView<? extends AppInfo> appView,
       DexApplication application,
       List<ProguardConfigurationRule> rules,
       InternalOptions options) {
-    this.appInfo = appInfo;
+    this.appView = appView;
     this.application = application.asDirect();
     this.rules = rules == null ? null : Collections.unmodifiableCollection(rules);
     this.options = options;
   }
 
   RootSetBuilder(
-      AppInfo appInfo,
-      Set<ProguardIfRule> ifRules,
-      InternalOptions options) {
-    this.appInfo = appInfo;
-    this.application = appInfo.app.asDirect();
+      AppView<? extends AppInfo> appView, Set<ProguardIfRule> ifRules, InternalOptions options) {
+    this.appView = appView;
+    this.application = appView.appInfo().app.asDirect();
     this.rules = Collections.unmodifiableCollection(ifRules);
     this.options = options;
   }
@@ -341,13 +340,14 @@
       Set<DexEncodedMethod> liveMethods,
       Set<DexEncodedField> liveFields) throws ExecutionException {
     application.timing.begin("Find consequent items for -if rules...");
-    Function<DexType, DexClass> definitionForWithLiveTypes = type -> {
-      DexClass clazz = appInfo.definitionFor(type);
-      if (clazz != null && liveTypes.contains(clazz.type)) {
-        return clazz;
-      }
-      return null;
-    };
+    Function<DexType, DexClass> definitionForWithLiveTypes =
+        type -> {
+          DexClass clazz = appView.appInfo().definitionFor(type);
+          if (clazz != null && liveTypes.contains(clazz.type)) {
+            return clazz;
+          }
+          return null;
+        };
     try {
       List<Future<?>> futures = new ArrayList<>();
       if (rules != null) {
@@ -358,7 +358,7 @@
           // -keep rule may vary (due to back references). So, we need to try all pairs of -if rule
           // and live types.
           for (DexType currentLiveType : liveTypes) {
-            DexClass currentLiveClass = appInfo.definitionFor(currentLiveType);
+            DexClass currentLiveClass = appView.appInfo().definitionFor(currentLiveType);
             if (currentLiveClass == null) {
               continue;
             }
@@ -550,7 +550,7 @@
     out.close();
   }
 
-  private static boolean satisfyClassType(ProguardConfigurationRule rule, DexClass clazz) {
+  private boolean satisfyClassType(ProguardConfigurationRule rule, DexClass clazz) {
     return rule.getClassType().matches(clazz) != rule.getClassTypeNegated();
   }
 
@@ -723,7 +723,7 @@
     if (type.isPrimitiveType()) {
       return;
     }
-    DexClass definition = appInfo.definitionFor(type);
+    DexClass definition = appView.appInfo().definitionFor(type);
     if (definition == null || definition.isLibraryClass()) {
       return;
     }
diff --git a/src/main/java/com/android/tools/r8/utils/StringUtils.java b/src/main/java/com/android/tools/r8/utils/StringUtils.java
index 4f0aa2c..244639e 100644
--- a/src/main/java/com/android/tools/r8/utils/StringUtils.java
+++ b/src/main/java/com/android/tools/r8/utils/StringUtils.java
@@ -59,9 +59,10 @@
     return builder.toString();
   }
 
-  public static void appendNonEmpty(StringBuilder builder, String pre, Object item, String post) {
+  public static boolean appendNonEmpty(
+      StringBuilder builder, String pre, Object item, String post) {
     if (item == null) {
-      return;
+      return false;
     }
     String text = item.toString();
     if (!text.isEmpty()) {
@@ -72,7 +73,9 @@
       if (post != null) {
         builder.append(post);
       }
+      return true;
     }
+    return false;
   }
 
   public static StringBuilder appendIndent(StringBuilder builder, String subject, int indent) {
diff --git a/src/test/java/com/android/tools/r8/TestBase.java b/src/test/java/com/android/tools/r8/TestBase.java
index bf80acc..6f93df4 100644
--- a/src/test/java/com/android/tools/r8/TestBase.java
+++ b/src/test/java/com/android/tools/r8/TestBase.java
@@ -12,8 +12,10 @@
 import com.android.tools.r8.ToolHelper.ArtCommandBuilder;
 import com.android.tools.r8.ToolHelper.DexVm;
 import com.android.tools.r8.ToolHelper.ProcessResult;
+import com.android.tools.r8.cf.code.CfInstruction;
 import com.android.tools.r8.code.Instruction;
 import com.android.tools.r8.errors.Unreachable;
+import com.android.tools.r8.graph.CfCode;
 import com.android.tools.r8.graph.DexCode;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.SmaliWriter;
@@ -706,6 +708,11 @@
     }
   }
 
+  protected ProcessResult runOnVMRaw(AndroidApp app, Class<?> mainClass, Backend backend)
+      throws IOException {
+    return runOnVMRaw(app, mainClass.getTypeName(), backend);
+  }
+
   protected ProcessResult runOnVMRaw(AndroidApp app, String mainClass, Backend backend)
       throws IOException {
     switch (backend) {
diff --git a/src/test/java/com/android/tools/r8/ToolHelper.java b/src/test/java/com/android/tools/r8/ToolHelper.java
index f5eaa25..481c50c 100644
--- a/src/test/java/com/android/tools/r8/ToolHelper.java
+++ b/src/test/java/com/android/tools/r8/ToolHelper.java
@@ -949,7 +949,7 @@
   }
 
   public static ProcessResult runJava(Class clazz) throws Exception {
-    String main = clazz.getCanonicalName();
+    String main = clazz.getTypeName();
     Path path = getClassPathForTests();
     return runJava(path, main);
   }
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 99222d0..b6cdb48 100644
--- a/src/test/java/com/android/tools/r8/debug/DebugTestBase.java
+++ b/src/test/java/com/android/tools/r8/debug/DebugTestBase.java
@@ -3,6 +3,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.debug;
 
+import com.android.tools.r8.TestBase;
 import com.android.tools.r8.ToolHelper;
 import com.android.tools.r8.ToolHelper.ArtCommandBuilder;
 import com.android.tools.r8.ToolHelper.DexVm;
@@ -79,7 +80,7 @@
  * The protocol messages are described here:
  * https://docs.oracle.com/javase/8/docs/platform/jpda/jdwp/jdwp-protocol.html
  */
-public abstract class DebugTestBase {
+public abstract class DebugTestBase extends TestBase {
 
   // Set to true to enable verbose logs
   private static final boolean DEBUG_TESTS = false;
diff --git a/src/test/java/com/android/tools/r8/ir/InlineTest.java b/src/test/java/com/android/tools/r8/ir/InlineTest.java
index 04b6dc0..a459a9c 100644
--- a/src/test/java/com/android/tools/r8/ir/InlineTest.java
+++ b/src/test/java/com/android/tools/r8/ir/InlineTest.java
@@ -6,6 +6,7 @@
 
 import static org.junit.Assert.assertEquals;
 
+import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.graph.DexApplication;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.ir.code.BasicBlock;
@@ -73,17 +74,18 @@
 
     InternalOptions options = new InternalOptions();
     DexApplication application = buildApplication(builder, options);
+    AppInfo appInfo = new AppInfo(application);
 
     // Return the processed method for inspection.
     ValueNumberGenerator valueNumberGenerator = new ValueNumberGenerator();
     DexEncodedMethod method = getMethod(application, signature);
-    IRCode code = method.buildInliningIRForTesting(new InternalOptions(), valueNumberGenerator);
+    IRCode code = method.buildInliningIRForTesting(options, valueNumberGenerator, appInfo);
 
     DexEncodedMethod methodA = getMethod(application, signatureA);
-    IRCode codeA = methodA.buildInliningIRForTesting(new InternalOptions(), valueNumberGenerator);
+    IRCode codeA = methodA.buildInliningIRForTesting(options, valueNumberGenerator, appInfo);
 
     DexEncodedMethod methodB = getMethod(application, signatureB);
-    IRCode codeB = methodB.buildInliningIRForTesting(new InternalOptions(), valueNumberGenerator);
+    IRCode codeB = methodB.buildInliningIRForTesting(options, valueNumberGenerator, appInfo);
 
     return new TestApplication(application, method, code,
         ImmutableList.of(codeA, codeB), valueNumberGenerator, options);
@@ -156,14 +158,15 @@
 
     InternalOptions options = new InternalOptions();
     DexApplication application = buildApplication(builder, options);
+    AppInfo appInfo = new AppInfo(application);
 
     // Return the processed method for inspection.
     ValueNumberGenerator valueNumberGenerator = new ValueNumberGenerator();
     DexEncodedMethod method = getMethod(application, signature);
-    IRCode code = method.buildInliningIRForTesting(new InternalOptions(), valueNumberGenerator);
+    IRCode code = method.buildInliningIRForTesting(options, valueNumberGenerator, appInfo);
 
     DexEncodedMethod methodA = getMethod(application, signatureA);
-    IRCode codeA = methodA.buildInliningIRForTesting(new InternalOptions(), valueNumberGenerator);
+    IRCode codeA = methodA.buildInliningIRForTesting(options, valueNumberGenerator, appInfo);
 
     return new TestApplication(application, method, code,
         ImmutableList.of(codeA), valueNumberGenerator, options);
@@ -236,23 +239,24 @@
 
     InternalOptions options = new InternalOptions();
     DexApplication application = buildApplication(builder, options);
+    AppInfo appInfo = new AppInfo(application);
 
     // Return the processed method for inspection.
     ValueNumberGenerator valueNumberGenerator = new ValueNumberGenerator();
     DexEncodedMethod method = getMethod(application, signature);
-    IRCode code = method.buildInliningIRForTesting(new InternalOptions(), valueNumberGenerator);
+    IRCode code = method.buildInliningIRForTesting(options, valueNumberGenerator, appInfo);
 
     // Build three copies of a and b for inlining three times.
     List<IRCode> additionalCode = new ArrayList<>();
     for (int i = 0; i < 3; i++) {
       DexEncodedMethod methodA = getMethod(application, signatureA);
-      IRCode codeA = methodA.buildInliningIRForTesting(new InternalOptions(), valueNumberGenerator);
+      IRCode codeA = methodA.buildInliningIRForTesting(options, valueNumberGenerator, appInfo);
       additionalCode.add(codeA);
     }
 
     for (int i = 0; i < 3; i++) {
       DexEncodedMethod methodB = getMethod(application, signatureB);
-      IRCode codeB = methodB.buildInliningIRForTesting(new InternalOptions(), valueNumberGenerator);
+      IRCode codeB = methodB.buildInliningIRForTesting(options, valueNumberGenerator, appInfo);
       additionalCode.add(codeB);
     }
 
@@ -372,17 +376,18 @@
 
     InternalOptions options = new InternalOptions();
     DexApplication application = buildApplication(builder, options);
+    AppInfo appInfo = new AppInfo(application);
 
     // Return the processed method for inspection.
     ValueNumberGenerator valueNumberGenerator = new ValueNumberGenerator();
     DexEncodedMethod method = getMethod(application, signature);
-    IRCode code = method.buildInliningIRForTesting(new InternalOptions(), valueNumberGenerator);
+    IRCode code = method.buildInliningIRForTesting(options, valueNumberGenerator, appInfo);
 
     DexEncodedMethod methodA = getMethod(application, signatureA);
-    IRCode codeA = methodA.buildInliningIRForTesting(new InternalOptions(), valueNumberGenerator);
+    IRCode codeA = methodA.buildInliningIRForTesting(options, valueNumberGenerator, appInfo);
 
     DexEncodedMethod methodB = getMethod(application, signatureB);
-    IRCode codeB = methodB.buildInliningIRForTesting(new InternalOptions(), valueNumberGenerator);
+    IRCode codeB = methodB.buildInliningIRForTesting(options, valueNumberGenerator, appInfo);
 
     return new TestApplication(application, method, code,
         ImmutableList.of(codeA, codeB), valueNumberGenerator, options);
@@ -486,17 +491,18 @@
 
     InternalOptions options = new InternalOptions();
     DexApplication application = buildApplication(builder, options);
+    AppInfo appInfo = new AppInfo(application);
 
     // Return the processed method for inspection.
     ValueNumberGenerator valueNumberGenerator = new ValueNumberGenerator();
     DexEncodedMethod method = getMethod(application, signature);
-    IRCode code = method.buildInliningIRForTesting(new InternalOptions(), valueNumberGenerator);
+    IRCode code = method.buildInliningIRForTesting(options, valueNumberGenerator, appInfo);
 
     DexEncodedMethod methodA = getMethod(application, signatureA);
-    IRCode codeA = methodA.buildInliningIRForTesting(new InternalOptions(), valueNumberGenerator);
+    IRCode codeA = methodA.buildInliningIRForTesting(options, valueNumberGenerator, appInfo);
 
     DexEncodedMethod methodB = getMethod(application, signatureB);
-    IRCode codeB = methodB.buildInliningIRForTesting(new InternalOptions(), valueNumberGenerator);
+    IRCode codeB = methodB.buildInliningIRForTesting(options, valueNumberGenerator, appInfo);
 
     return new TestApplication(application, method, code,
         ImmutableList.of(codeA, codeB), valueNumberGenerator, options);
@@ -599,17 +605,18 @@
 
     InternalOptions options = new InternalOptions();
     DexApplication application = buildApplication(builder, options);
+    AppInfo appInfo = new AppInfo(application);
 
     // Return the processed method for inspection.
     ValueNumberGenerator valueNumberGenerator = new ValueNumberGenerator();
     DexEncodedMethod method = getMethod(application, signature);
-    IRCode code = method.buildInliningIRForTesting(new InternalOptions(), valueNumberGenerator);
+    IRCode code = method.buildInliningIRForTesting(options, valueNumberGenerator, appInfo);
 
     DexEncodedMethod methodA = getMethod(application, signatureA);
-    IRCode codeA = methodA.buildInliningIRForTesting(new InternalOptions(), valueNumberGenerator);
+    IRCode codeA = methodA.buildInliningIRForTesting(options, valueNumberGenerator, appInfo);
 
     DexEncodedMethod methodB = getMethod(application, signatureB);
-    IRCode codeB = methodB.buildInliningIRForTesting(new InternalOptions(), valueNumberGenerator);
+    IRCode codeB = methodB.buildInliningIRForTesting(options, valueNumberGenerator, appInfo);
 
     return new TestApplication(application, method, code,
         ImmutableList.of(codeA, codeB), valueNumberGenerator, options);
@@ -713,23 +720,24 @@
 
     InternalOptions options = new InternalOptions();
     DexApplication application = buildApplication(builder, options);
+    AppInfo appInfo = new AppInfo(application);
 
     // Return the processed method for inspection.
     ValueNumberGenerator valueNumberGenerator = new ValueNumberGenerator();
     DexEncodedMethod method = getMethod(application, signature);
-    IRCode code = method.buildInliningIRForTesting(new InternalOptions(), valueNumberGenerator);
+    IRCode code = method.buildInliningIRForTesting(options, valueNumberGenerator, appInfo);
 
     // Build three copies of a and b for inlining three times.
     List<IRCode> additionalCode = new ArrayList<>();
     for (int i = 0; i < 3; i++) {
       DexEncodedMethod methodA = getMethod(application, signatureA);
-      IRCode codeA = methodA.buildInliningIRForTesting(new InternalOptions(), valueNumberGenerator);
+      IRCode codeA = methodA.buildInliningIRForTesting(options, valueNumberGenerator, appInfo);
       additionalCode.add(codeA);
     }
 
     for (int i = 0; i < 3; i++) {
       DexEncodedMethod methodB = getMethod(application, signatureB);
-      IRCode codeB = methodB.buildInliningIRForTesting(new InternalOptions(), valueNumberGenerator);
+      IRCode codeB = methodB.buildInliningIRForTesting(options, valueNumberGenerator, appInfo);
       additionalCode.add(codeB);
     }
 
@@ -872,23 +880,24 @@
 
     InternalOptions options = new InternalOptions();
     DexApplication application = buildApplication(builder, options);
+    AppInfo appInfo = new AppInfo(application);
 
     // Return the processed method for inspection.
     ValueNumberGenerator valueNumberGenerator = new ValueNumberGenerator();
     DexEncodedMethod method = getMethod(application, signature);
-    IRCode code = method.buildInliningIRForTesting(new InternalOptions(), valueNumberGenerator);
+    IRCode code = method.buildInliningIRForTesting(options, valueNumberGenerator, appInfo);
 
     // Build three copies of a and b for inlining three times.
     List<IRCode> additionalCode = new ArrayList<>();
     for (int i = 0; i < 3; i++) {
       DexEncodedMethod methodA = getMethod(application, signatureA);
-      IRCode codeA = methodA.buildInliningIRForTesting(new InternalOptions(), valueNumberGenerator);
+      IRCode codeA = methodA.buildInliningIRForTesting(options, valueNumberGenerator, appInfo);
       additionalCode.add(codeA);
     }
 
     for (int i = 0; i < 3; i++) {
       DexEncodedMethod methodB = getMethod(application, signatureB);
-      IRCode codeB = methodB.buildInliningIRForTesting(new InternalOptions(), valueNumberGenerator);
+      IRCode codeB = methodB.buildInliningIRForTesting(options, valueNumberGenerator, appInfo);
       additionalCode.add(codeB);
     }
 
@@ -1121,17 +1130,18 @@
 
     InternalOptions options = new InternalOptions();
     DexApplication application = buildApplication(builder, options);
+    AppInfo appInfo = new AppInfo(application);
 
     // Return the processed method for inspection.
     ValueNumberGenerator valueNumberGenerator = new ValueNumberGenerator();
     DexEncodedMethod method = getMethod(application, signature);
-    IRCode code = method.buildInliningIRForTesting(new InternalOptions(), valueNumberGenerator);
+    IRCode code = method.buildInliningIRForTesting(options, valueNumberGenerator, appInfo);
 
     DexEncodedMethod methodA = getMethod(application, signatureA);
-    IRCode codeA = methodA.buildInliningIRForTesting(new InternalOptions(), valueNumberGenerator);
+    IRCode codeA = methodA.buildInliningIRForTesting(options, valueNumberGenerator, appInfo);
 
     DexEncodedMethod methodB = getMethod(application, signatureB);
-    IRCode codeB = methodB.buildInliningIRForTesting(new InternalOptions(), valueNumberGenerator);
+    IRCode codeB = methodB.buildInliningIRForTesting(options, valueNumberGenerator, appInfo);
 
     return new TestApplication(application, method, code,
         ImmutableList.of(codeA, codeB), valueNumberGenerator, options);
diff --git a/src/test/java/com/android/tools/r8/ir/SplitBlockTest.java b/src/test/java/com/android/tools/r8/ir/SplitBlockTest.java
index 0cf2f53..86e1d78 100644
--- a/src/test/java/com/android/tools/r8/ir/SplitBlockTest.java
+++ b/src/test/java/com/android/tools/r8/ir/SplitBlockTest.java
@@ -10,6 +10,7 @@
 
 import com.android.tools.r8.graph.DexApplication;
 import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.Add;
 import com.android.tools.r8.ir.code.BasicBlock;
 import com.android.tools.r8.ir.code.ConstNumber;
@@ -20,7 +21,6 @@
 import com.android.tools.r8.ir.code.Position;
 import com.android.tools.r8.ir.code.Value;
 import com.android.tools.r8.ir.code.ValueNumberGenerator;
-import com.android.tools.r8.ir.code.ValueType;
 import com.android.tools.r8.smali.SmaliBuilder;
 import com.android.tools.r8.smali.SmaliBuilder.MethodSignature;
 import com.android.tools.r8.utils.InternalOptions;
@@ -364,8 +364,10 @@
       BasicBlock newReturnBlock = iterator.split(code);
       // Modify the code to make the inserted block add the constant 10 to the original return
       // value.
-      Value newConstValue = new Value(test.valueNumberGenerator.next(), ValueType.INT, null);
-      Value newReturnValue = new Value(test.valueNumberGenerator.next(), ValueType.INT, null);
+      Value newConstValue =
+          new Value(test.valueNumberGenerator.next(), TypeLatticeElement.INT, null);
+      Value newReturnValue =
+          new Value(test.valueNumberGenerator.next(), TypeLatticeElement.INT, null);
       Value oldReturnValue = newReturnBlock.listIterator().next().asReturn().returnValue();
       newReturnBlock.listIterator().next().asReturn().returnValue().replaceUsers(newReturnValue);
       Instruction constInstruction = new ConstNumber(newConstValue, 10);
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 c618dad..109a6cb 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
@@ -120,9 +120,9 @@
       DexType mainClass = appInfo.dexItemFactory.createType(
           DescriptorUtils.javaTypeToDescriptor(NonNullAfterInvoke.class.getCanonicalName()));
       Map<Class<? extends Instruction>, TypeLatticeElement> expectedLattices = ImmutableMap.of(
-          InvokeVirtual.class, fromDexType(appInfo, appInfo.dexItemFactory.stringType, true),
-          NonNull.class, fromDexType(appInfo, appInfo.dexItemFactory.stringType, false),
-          NewInstance.class, fromDexType(appInfo, assertionErrorType, false));
+          InvokeVirtual.class, fromDexType(appInfo.dexItemFactory.stringType, appInfo, true),
+          NonNull.class, fromDexType(appInfo.dexItemFactory.stringType, appInfo, false),
+          NewInstance.class, fromDexType(assertionErrorType, appInfo, false));
       forEachOutValue(irCode, (v, l) -> verifyClassTypeLattice(expectedLattices, mainClass, v, l));
     });
   }
@@ -136,9 +136,9 @@
       DexType mainClass = appInfo.dexItemFactory.createType(
           DescriptorUtils.javaTypeToDescriptor(NonNullAfterInvoke.class.getCanonicalName()));
       Map<Class<? extends Instruction>, TypeLatticeElement> expectedLattices = ImmutableMap.of(
-          InvokeVirtual.class, fromDexType(appInfo, appInfo.dexItemFactory.stringType, true),
-          NonNull.class, fromDexType(appInfo, appInfo.dexItemFactory.stringType, false),
-          NewInstance.class, fromDexType(appInfo, assertionErrorType, false));
+          InvokeVirtual.class, fromDexType(appInfo.dexItemFactory.stringType, appInfo, true),
+          NonNull.class, fromDexType(appInfo.dexItemFactory.stringType, appInfo, false),
+          NewInstance.class, fromDexType(assertionErrorType, appInfo, false));
       forEachOutValue(irCode, (v, l) -> verifyClassTypeLattice(expectedLattices, mainClass, v, l));
     });
   }
@@ -153,8 +153,8 @@
           DescriptorUtils.javaTypeToDescriptor(NonNullAfterArrayAccess.class.getCanonicalName()));
       Map<Class<? extends Instruction>, TypeLatticeElement> expectedLattices = ImmutableMap.of(
           // An element inside a non-null array could be null.
-          ArrayGet.class, fromDexType(appInfo, appInfo.dexItemFactory.stringType, true),
-          NewInstance.class, fromDexType(appInfo, assertionErrorType, false));
+          ArrayGet.class, fromDexType(appInfo.dexItemFactory.stringType, appInfo, true),
+          NewInstance.class, fromDexType(assertionErrorType, appInfo, false));
       forEachOutValue(irCode, (v, l) -> {
         if (l.isArrayType()) {
           ArrayTypeLatticeElement lattice = l.asArrayTypeLatticeElement();
@@ -179,8 +179,8 @@
           DescriptorUtils.javaTypeToDescriptor(NonNullAfterArrayAccess.class.getCanonicalName()));
       Map<Class<? extends Instruction>, TypeLatticeElement> expectedLattices = ImmutableMap.of(
           // An element inside a non-null array could be null.
-          ArrayGet.class, fromDexType(appInfo, appInfo.dexItemFactory.stringType, true),
-          NewInstance.class, fromDexType(appInfo, assertionErrorType, false));
+          ArrayGet.class, fromDexType(appInfo.dexItemFactory.stringType, appInfo, true),
+          NewInstance.class, fromDexType(assertionErrorType, appInfo, false));
       forEachOutValue(irCode, (v, l) -> {
         if (l.isArrayType()) {
           ArrayTypeLatticeElement lattice = l.asArrayTypeLatticeElement();
@@ -206,11 +206,11 @@
       DexType testClass = appInfo.dexItemFactory.createType(
           DescriptorUtils.javaTypeToDescriptor(FieldAccessTest.class.getCanonicalName()));
       Map<Class<? extends Instruction>, TypeLatticeElement> expectedLattices = ImmutableMap.of(
-          Argument.class, fromDexType(appInfo, testClass, true),
-          NonNull.class, fromDexType(appInfo, testClass, false),
+          Argument.class, fromDexType(testClass, appInfo, true),
+          NonNull.class, fromDexType(testClass, appInfo, false),
           // instance may not be initialized.
-          InstanceGet.class, fromDexType(appInfo, appInfo.dexItemFactory.stringType, true),
-          NewInstance.class, fromDexType(appInfo, assertionErrorType, false));
+          InstanceGet.class, fromDexType(appInfo.dexItemFactory.stringType, appInfo, true),
+          NewInstance.class, fromDexType(assertionErrorType, appInfo, false));
       forEachOutValue(irCode, (v, l) -> verifyClassTypeLattice(expectedLattices, mainClass, v, l));
     });
   }
@@ -226,11 +226,11 @@
       DexType testClass = appInfo.dexItemFactory.createType(
           DescriptorUtils.javaTypeToDescriptor(FieldAccessTest.class.getCanonicalName()));
       Map<Class<? extends Instruction>, TypeLatticeElement> expectedLattices = ImmutableMap.of(
-          Argument.class, fromDexType(appInfo, testClass, true),
-          NonNull.class, fromDexType(appInfo, testClass, false),
+          Argument.class, fromDexType(testClass, appInfo, true),
+          NonNull.class, fromDexType(testClass, appInfo, false),
           // instance may not be initialized.
-          InstanceGet.class, fromDexType(appInfo, appInfo.dexItemFactory.stringType, true),
-          NewInstance.class, fromDexType(appInfo, assertionErrorType, false));
+          InstanceGet.class, fromDexType(appInfo.dexItemFactory.stringType, appInfo, true),
+          NewInstance.class, fromDexType(assertionErrorType, appInfo, false));
       forEachOutValue(irCode, (v, l) -> 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 75cef4d..fd92348 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
@@ -58,11 +58,10 @@
 @RunWith(Parameterized.class)
 public class TypeAnalysisTest extends SmaliTestBase {
   private static final InternalOptions TEST_OPTIONS = new InternalOptions();
-  private static final TypeLatticeElement NULL =
-      ReferenceTypeLatticeElement.getNullTypeLatticeElement();
-  private static final TypeLatticeElement SINGLE = SingleTypeLatticeElement.getInstance();
-  private static final TypeLatticeElement INT = IntTypeLatticeElement.getInstance();
-  private static final TypeLatticeElement LONG = LongTypeLatticeElement.getInstance();
+  private static final TypeLatticeElement NULL = TypeLatticeElement.NULL;
+  private static final TypeLatticeElement SINGLE = TypeLatticeElement.SINGLE;
+  private static final TypeLatticeElement INT = TypeLatticeElement.INT;
+  private static final TypeLatticeElement LONG = TypeLatticeElement.LONG;
 
   private final String dirName;
   private final String smaliFileName;
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 eb2c54b..0898891 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
@@ -59,15 +59,23 @@
   }
 
   private TopTypeLatticeElement top() {
-    return TopTypeLatticeElement.getInstance();
+    return TypeLatticeElement.TOP;
   }
 
   private BottomTypeLatticeElement bottom() {
-    return BottomTypeLatticeElement.getInstance();
+    return TypeLatticeElement.BOTTOM;
+  }
+
+  private SingleTypeLatticeElement single() {
+    return TypeLatticeElement.SINGLE;
+  }
+
+  private WideTypeLatticeElement wide() {
+    return TypeLatticeElement.WIDE;
   }
 
   private TypeLatticeElement element(DexType type) {
-    return TypeLatticeElement.fromDexType(appInfo, type, true);
+    return TypeLatticeElement.fromDexType(type, appInfo, true);
   }
 
   private ArrayTypeLatticeElement array(int nesting, DexType base) {
@@ -101,6 +109,22 @@
   }
 
   @Test
+  public void joinDifferentKindsIsTop() {
+    assertEquals(
+        top(),
+        join(element(factory.intType), element(factory.stringType)));
+    assertEquals(
+        top(),
+        join(element(factory.stringType), element(factory.doubleType)));
+    assertEquals(
+        top(),
+        join(single(), element(factory.objectType)));
+    assertEquals(
+        top(),
+        join(element(factory.objectType), wide()));
+  }
+
+  @Test
   public void joinBottomIsUnit() {
     DexType charSequence = factory.createType("Ljava/lang/CharSequence;");
     assertEquals(
@@ -115,6 +139,19 @@
   }
 
   @Test
+  public void joinPrimitiveTypes() {
+    assertEquals(
+        single(),
+        join(element(factory.intType), element(factory.floatType)));
+    assertEquals(
+        wide(),
+        join(element(factory.longType), element(factory.doubleType)));
+    assertEquals(
+        top(),
+        join(element(factory.intType), element(factory.longType)));
+  }
+
+  @Test
   public void joinClassTypes() {
     DexType charSequence = factory.createType("Ljava/lang/CharSequence;");
     assertEquals(
@@ -297,6 +334,11 @@
         join(
             array(1, factory.intType),
             array(1, factory.floatType)));
+    assertEquals(
+        element(factory.objectType),
+        join(
+            array(1, factory.longType),
+            array(1, factory.intType)));
   }
 
   @Test
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/ConstantRemovalTest.java b/src/test/java/com/android/tools/r8/ir/optimize/ConstantRemovalTest.java
index 2b92ab1..fb8e674 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/ConstantRemovalTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/ConstantRemovalTest.java
@@ -5,6 +5,7 @@
 
 import static org.junit.Assert.assertEquals;
 
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.BasicBlock;
 import com.android.tools.r8.ir.code.ConstNumber;
 import com.android.tools.r8.ir.code.Div;
@@ -16,7 +17,6 @@
 import com.android.tools.r8.ir.code.Return;
 import com.android.tools.r8.ir.code.Value;
 import com.android.tools.r8.ir.code.ValueNumberGenerator;
-import com.android.tools.r8.ir.code.ValueType;
 import com.android.tools.r8.ir.regalloc.LinearScanRegisterAllocator;
 import com.android.tools.r8.ir.regalloc.LiveIntervals;
 import com.android.tools.r8.utils.InternalOptions;
@@ -69,14 +69,14 @@
     block.setNumber(0);
     Position position = Position.testingPosition();
 
-    Value v3 = new Value(3, ValueType.LONG, null);
+    Value v3 = new Value(3, TypeLatticeElement.LONG, null);
     v3.setNeedsRegister(true);
     new MockLiveIntervals(v3);
     Instruction instruction = new ConstNumber(v3, 0);
     instruction.setPosition(position);
     block.add(instruction);
 
-    Value v0 = new Value(0, ValueType.LONG, null);
+    Value v0 = new Value(0, TypeLatticeElement.LONG, null);
     v0.setNeedsRegister(true);
     new MockLiveIntervals(v0);
     instruction = new ConstNumber(v0, 10);
@@ -87,14 +87,14 @@
     instruction.setPosition(position);
     block.add(instruction);
 
-    Value v2 = new Value(2, ValueType.INT, null);
+    Value v2 = new Value(2, TypeLatticeElement.INT, null);
     v2.setNeedsRegister(true);
     new MockLiveIntervals(v2);
     instruction = new ConstNumber(v2, 10);
     instruction.setPosition(position);
     block.add(instruction);
 
-    Value v1 = new Value(1, ValueType.INT, null);
+    Value v1 = new Value(1, TypeLatticeElement.INT, null);
     v1.setNeedsRegister(true);
     new MockLiveIntervals(v1);
     instruction = new Move(v1 ,v2);
@@ -105,7 +105,7 @@
     instruction.setPosition(position);
     block.add(instruction);
 
-    Value v0_2 = new Value(0, ValueType.LONG, null);
+    Value v0_2 = new Value(0, TypeLatticeElement.LONG, null);
     v0_2.setNeedsRegister(true);
     new MockLiveIntervals(v0_2);
     instruction = new ConstNumber(v0_2, 10);
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/TrivialGotoEliminationTest.java b/src/test/java/com/android/tools/r8/ir/optimize/TrivialGotoEliminationTest.java
index 6470876..d254847 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/TrivialGotoEliminationTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/TrivialGotoEliminationTest.java
@@ -6,6 +6,8 @@
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertTrue;
 
+import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.Argument;
 import com.android.tools.r8.ir.code.BasicBlock;
 import com.android.tools.r8.ir.code.ConstNumber;
@@ -19,7 +21,6 @@
 import com.android.tools.r8.ir.code.Throw;
 import com.android.tools.r8.ir.code.Value;
 import com.android.tools.r8.ir.code.ValueNumberGenerator;
-import com.android.tools.r8.ir.code.ValueType;
 import com.android.tools.r8.utils.InternalOptions;
 import com.google.common.collect.ImmutableList;
 import java.util.LinkedList;
@@ -49,7 +50,7 @@
     block2.setFilledForTesting();
     BasicBlock block1 = new BasicBlock();
     block1.setNumber(1);
-    Value value = new Value(0, ValueType.INT, null);
+    Value value = new Value(0, TypeLatticeElement.INT, null);
     Instruction number = new ConstNumber(value, 0);
     number.setPosition(position);
     block1.add(number);
@@ -110,7 +111,7 @@
 
     BasicBlock block0 = new BasicBlock();
     block0.setNumber(0);
-    Value value = new Value(0, ValueType.OBJECT, null);
+    Value value = new Value(0, TypeLatticeElement.fromDexType(DexItemFactory.catchAllType), null);
     instruction = new Argument(value);
     instruction.setPosition(position);
     block0.add(instruction);
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/checkcast/CheckCastDebugTest.java b/src/test/java/com/android/tools/r8/ir/optimize/checkcast/CheckCastDebugTest.java
new file mode 100644
index 0000000..6d6b4c7
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/checkcast/CheckCastDebugTest.java
@@ -0,0 +1,55 @@
+// 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.checkcast;
+
+import com.android.tools.r8.NeverInline;
+
+class A {
+  @NeverInline
+  @Override
+  public String toString() {
+    return "A";
+  }
+}
+
+class B extends A {
+  @NeverInline
+  @Override
+  public String toString() {
+    return super.toString() + "B";
+  }
+}
+
+class C extends B {
+  @NeverInline
+  @Override
+  public String toString() {
+    return super.toString() + "C";
+  }
+}
+
+class CheckCastDebugTest {
+  @NeverInline
+  static void differentLocals() {
+    Object obj = new C();
+    A a = (A) obj;
+    B b = (B) a;
+    C c = (C) b;
+    System.out.println(c.toString());
+  }
+
+  @NeverInline
+  static void sameLocal() {
+    Object obj = new C();
+    obj = (A) obj;
+    obj = (B) obj;
+    obj = (C) obj;
+    System.out.println(obj.toString());
+  }
+
+  public static void main(String[] args) {
+    differentLocals();
+    sameLocal();
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/checkcast/CheckCastDebugTestRunner.java b/src/test/java/com/android/tools/r8/ir/optimize/checkcast/CheckCastDebugTestRunner.java
new file mode 100644
index 0000000..1eddbd3
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/checkcast/CheckCastDebugTestRunner.java
@@ -0,0 +1,170 @@
+// 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.checkcast;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertThat;
+
+import com.android.tools.r8.ClassFileConsumer;
+import com.android.tools.r8.CompilationMode;
+import com.android.tools.r8.DexIndexedConsumer;
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.R8Command;
+import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.debug.CfDebugTestConfig;
+import com.android.tools.r8.debug.DebugTestBase;
+import com.android.tools.r8.debug.DebugTestConfig;
+import com.android.tools.r8.debug.DexDebugTestConfig;
+import com.android.tools.r8.origin.Origin;
+import com.android.tools.r8.utils.AndroidApp;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import com.android.tools.r8.utils.codeinspector.InstructionSubject;
+import com.android.tools.r8.utils.codeinspector.MethodSubject;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Streams;
+import java.nio.file.Path;
+import java.util.Arrays;
+import java.util.Collection;
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class CheckCastDebugTestRunner extends DebugTestBase {
+  private static final Class<?> MAIN = CheckCastDebugTest.class;
+  private final Backend backend;
+
+  private Path r8Out;
+  private CodeInspector inspector;
+
+  @Parameterized.Parameters(name = "Backend: {0}")
+  public static Collection<Backend> data() {
+    return Arrays.asList(Backend.values());
+  }
+
+  public CheckCastDebugTestRunner(Backend backend) {
+    this.backend = backend;
+  }
+
+  private static int testCounter = 0;
+
+  @Before
+  public void setUp() throws Exception {
+    AndroidApp app = readClasses(NeverInline.class, A.class, B.class, C.class, MAIN);
+    r8Out = temp.newFile(String.format("r8Out-%s-%d.zip", backend, testCounter++)).toPath();
+    R8Command.Builder builder = ToolHelper.prepareR8CommandBuilder(app);
+    if (backend == Backend.DEX) {
+      builder.setProgramConsumer(new DexIndexedConsumer.ArchiveConsumer(r8Out));
+    } else {
+      assert backend == Backend.CF;
+      builder.setProgramConsumer(new ClassFileConsumer.ArchiveConsumer(r8Out));
+    }
+    builder.addProguardConfiguration(
+        ImmutableList.of(
+            "-dontobfuscate",
+            keepMainProguardConfigurationWithInliningAnnotation(MAIN)),
+        Origin.unknown());
+    builder.setMode(CompilationMode.DEBUG);
+    ToolHelper.allowTestProguardOptions(builder);
+    ToolHelper.runR8(builder.build(), o -> o.enableVerticalClassMerging = false);
+    inspector = new CodeInspector(r8Out);
+    ClassSubject classSubject = inspector.clazz(MAIN);
+    assertThat(classSubject, isPresent());
+  }
+
+  @Test
+  public void test_differentLocals() throws Throwable {
+    ClassSubject classSubject = inspector.clazz(MAIN);
+    MethodSubject method = classSubject.method("void", "differentLocals", ImmutableList.of());
+    assertThat(method, isPresent());
+    long count =
+        Streams.stream(method.iterateInstructions(InstructionSubject::isCheckCast)).count();
+    assertEquals(1, count);
+
+    DebugTestConfig config = backend == Backend.CF
+        ? new CfDebugTestConfig()
+        : new DexDebugTestConfig();
+    config.addPaths(r8Out);
+    runDebugTest(config, MAIN.getCanonicalName(),
+        // Object obj = new C();
+        breakpoint(MAIN.getCanonicalName(), "differentLocals", "()V", 35),
+        run(),
+        checkNoLocal("obj"),
+        checkNoLocal("a"),
+        checkNoLocal("b"),
+        checkNoLocal("c"),
+        // A a = (A) obj;
+        breakpoint(MAIN.getCanonicalName(), "differentLocals", "()V", 36),
+        run(),
+        checkLocal("obj"),
+        checkNoLocal("a"),
+        checkNoLocal("b"),
+        checkNoLocal("c"),
+        // B b = (B) a;
+        breakpoint(MAIN.getCanonicalName(), "differentLocals", "()V", 37),
+        run(),
+        checkLocal("obj"),
+        checkLocal("a"),
+        checkNoLocal("b"),
+        checkNoLocal("c"),
+        // C c = (C) b;
+        breakpoint(MAIN.getCanonicalName(), "differentLocals", "()V", 38),
+        run(),
+        checkLocal("obj"),
+        checkLocal("a"),
+        checkLocal("b"),
+        checkNoLocal("c"),
+        // System.out.println(c.toString());
+        breakpoint(MAIN.getCanonicalName(), "differentLocals", "()V", 39),
+        run(),
+        checkLocal("obj"),
+        checkLocal("a"),
+        checkLocal("b"),
+        checkLocal("c"),
+        run()
+    );
+  }
+
+  @Test
+  public void test_sameLocal() throws Throwable {
+    ClassSubject classSubject = inspector.clazz(MAIN);
+    MethodSubject method = classSubject.method("void", "sameLocal", ImmutableList.of());
+    assertThat(method, isPresent());
+    long count =
+        Streams.stream(method.iterateInstructions(InstructionSubject::isCheckCast)).count();
+    assertEquals(1, count);
+
+    DebugTestConfig config = backend == Backend.CF
+        ? new CfDebugTestConfig()
+        : new DexDebugTestConfig();
+    config.addPaths(r8Out);
+    runDebugTest(config, MAIN.getCanonicalName(),
+        // Object obj = new C();
+        breakpoint(MAIN.getCanonicalName(), "sameLocal", "()V", 44),
+        run(),
+        checkNoLocal("obj"),
+        // obj = (A) obj;
+        breakpoint(MAIN.getCanonicalName(), "sameLocal", "()V", 45),
+        run(),
+        checkLocal("obj"),
+        // obj = (B) obj;
+        breakpoint(MAIN.getCanonicalName(), "sameLocal", "()V", 46),
+        run(),
+        checkLocal("obj"),
+        // obj = (C) obj;
+        breakpoint(MAIN.getCanonicalName(), "sameLocal", "()V", 47),
+        run(),
+        checkLocal("obj"),
+        // System.out.println(obj.toString());
+        breakpoint(MAIN.getCanonicalName(), "sameLocal", "()V", 48),
+        run(),
+        checkLocal("obj"),
+        run()
+    );
+  }
+
+}
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/checkcast/CheckCastRemovalTest.java b/src/test/java/com/android/tools/r8/ir/optimize/checkcast/CheckCastRemovalTest.java
index b141955..c953515 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/checkcast/CheckCastRemovalTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/checkcast/CheckCastRemovalTest.java
@@ -99,7 +99,7 @@
   }
 
   @Test
-  public void downCasts() throws Exception {
+  public void downCasts_noLocal() throws Exception {
     JasminBuilder builder = new JasminBuilder();
     // C < B < A
     ClassBuilder a = builder.addClass("A");
@@ -133,6 +133,91 @@
   }
 
   @Test
+  public void downCasts_differentLocals() throws Exception {
+    JasminBuilder builder = new JasminBuilder();
+    // C < B < A
+    ClassBuilder a = builder.addClass("A");
+    a.addDefaultConstructor();
+    ClassBuilder b = builder.addClass("B", "A");
+    b.addDefaultConstructor();
+    ClassBuilder c = builder.addClass("C", "B");
+    c.addDefaultConstructor();
+    ClassBuilder classBuilder = builder.addClass(CLASS_NAME);
+    MethodSignature main = classBuilder.addMainMethod(
+        ".limit stack 3",
+        ".limit locals 3",
+        ".var 0 is a LA; from Label1 to Label2",
+        ".var 1 is b LB; from Label1 to Label2",
+        ".var 2 is c LC; from Label1 to Label2",
+        "Label1:",
+        "new A",
+        "dup",
+        "invokespecial A/<init>()V",
+        "astore_0",
+        "aload_0",
+        "checkcast B", // Gone
+        "astore_1",
+        "aload_1",
+        "checkcast C", // Should be kept to preserve cast exception
+        "astore_2",
+        "Label2:",
+        "return");
+
+    List<String> pgConfigs = ImmutableList.of(
+        "-keep class " + CLASS_NAME + " { *; }",
+        "-keep class A { *; }",
+        "-keep class B { *; }",
+        "-keep class C { *; }",
+        "-dontoptimize",
+        "-dontshrink");
+    AndroidApp app = compileWithR8InDebugMode(builder, pgConfigs, null, backend);
+
+    checkCheckCasts(app, main, "C");
+    checkRuntimeException(builder, app, CLASS_NAME, "ClassCastException");
+  }
+
+  @Test
+  public void downCasts_sameLocal() throws Exception {
+    JasminBuilder builder = new JasminBuilder();
+    // C < B < A
+    ClassBuilder a = builder.addClass("A");
+    a.addDefaultConstructor();
+    ClassBuilder b = builder.addClass("B", "A");
+    b.addDefaultConstructor();
+    ClassBuilder c = builder.addClass("C", "B");
+    c.addDefaultConstructor();
+    ClassBuilder classBuilder = builder.addClass(CLASS_NAME);
+    MethodSignature main = classBuilder.addMainMethod(
+        ".limit stack 3",
+        ".limit locals 1",
+        ".var 0 is a LA; from Label1 to Label2",
+        "Label1:",
+        "new A",
+        "dup",
+        "invokespecial A/<init>()V",
+        "astore_0",
+        "aload_0",
+        "checkcast B", // Gone
+        "astore_0",
+        "aload_0",
+        "checkcast C", // Should be kept to preserve cast exception
+        "Label2:",
+        "return");
+
+    List<String> pgConfigs = ImmutableList.of(
+        "-keep class " + CLASS_NAME + " { *; }",
+        "-keep class A { *; }",
+        "-keep class B { *; }",
+        "-keep class C { *; }",
+        "-dontoptimize",
+        "-dontshrink");
+    AndroidApp app = compileWithR8InDebugMode(builder, pgConfigs, null, backend);
+
+    checkCheckCasts(app, main, "C");
+    checkRuntimeException(builder, app, CLASS_NAME, "ClassCastException");
+  }
+
+  @Test
   public void bothUpAndDowncast() throws Exception {
     JasminBuilder builder = new JasminBuilder();
     ClassBuilder classBuilder = builder.addClass(CLASS_NAME);
@@ -180,7 +265,7 @@
         "-dontshrink");
     AndroidApp app = compileWithR8(builder, pgConfigs, null, backend);
 
-    checkCheckCasts(app, main, "Example");
+    checkCheckCasts(app, main, null);
     checkRuntimeException(builder, app, CLASS_NAME, "NullPointerException");
   }
 
@@ -201,6 +286,7 @@
       assertTrue(!found && instruction.isCheckCast(maybeType));
       found = true;
     }
+    assertTrue(found);
   }
 
   private void checkRuntime(JasminBuilder builder, AndroidApp app, String className)
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/checkcast/RemoveCheckCastAfterClassInlining.java b/src/test/java/com/android/tools/r8/ir/optimize/checkcast/RemoveCheckCastAfterClassInlining.java
new file mode 100644
index 0000000..d52725e
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/checkcast/RemoveCheckCastAfterClassInlining.java
@@ -0,0 +1,79 @@
+// 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.checkcast;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.CoreMatchers.not;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.code.Instruction;
+import com.android.tools.r8.graph.DexCode;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.utils.AndroidApp;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import com.android.tools.r8.utils.codeinspector.MethodSubject;
+import com.google.common.collect.ImmutableList;
+import org.junit.Test;
+
+public class RemoveCheckCastAfterClassInlining extends TestBase {
+
+  @Test
+  public void test() throws Exception {
+    AndroidApp input = readClasses(Lambda.class, Lambda.Consumer.class);
+    AndroidApp output =
+        compileWithR8(
+            input,
+            keepMainProguardConfiguration(Lambda.class),
+            options -> options.enableMinification = false);
+
+    // Extract main method.
+    CodeInspector inspector = new CodeInspector(output);
+    ClassSubject classSubject = inspector.clazz(Lambda.class);
+    MethodSubject methodSubject = classSubject.mainMethod();
+    assertThat(methodSubject, isPresent());
+
+    DexEncodedMethod method = methodSubject.getMethod();
+    assertTrue(method.hasCode());
+
+    DexCode code = method.getCode().asDexCode();
+    int numberOfConstStringInstructions = 0;
+    for (Instruction instruction : code.instructions) {
+      // Make sure that we do not load a const-string and then subsequently use a check-cast
+      // instruction to check if it is actually a string.
+      assertFalse(instruction.isCheckCast());
+      if (instruction.isConstString()) {
+        numberOfConstStringInstructions++;
+      }
+    }
+
+    // Sanity check that load() was actually inlined.
+    assertThat(
+        classSubject.method("void", "load", ImmutableList.of(Lambda.Consumer.class.getName())),
+        not(isPresent()));
+    assertEquals(2, numberOfConstStringInstructions);
+  }
+}
+
+class Lambda {
+
+  interface Consumer<T> {
+    void accept(T value);
+  }
+
+  public static void main(String... args) {
+    load(s -> System.out.println(s));
+    // Other code…
+    load(s -> System.out.println(s));
+  }
+
+  public static void load(Consumer<String> c) {
+    c.accept("Hello!");
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/ir/regalloc/IdenticalAfterRegisterAllocationTest.java b/src/test/java/com/android/tools/r8/ir/regalloc/IdenticalAfterRegisterAllocationTest.java
index 8102882..6d824ec 100644
--- a/src/test/java/com/android/tools/r8/ir/regalloc/IdenticalAfterRegisterAllocationTest.java
+++ b/src/test/java/com/android/tools/r8/ir/regalloc/IdenticalAfterRegisterAllocationTest.java
@@ -6,12 +6,12 @@
 import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertTrue;
 
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.Add;
 import com.android.tools.r8.ir.code.ConstNumber;
 import com.android.tools.r8.ir.code.NumericType;
 import com.android.tools.r8.ir.code.Position;
 import com.android.tools.r8.ir.code.Value;
-import com.android.tools.r8.ir.code.ValueType;
 import com.android.tools.r8.utils.InternalOptions;
 import org.junit.Test;
 
@@ -47,13 +47,13 @@
   @Test
   public void equalityOfConstantOperands() {
     RegisterAllocator allocator = new MockRegisterAllocator();
-    Value value0 = new Value(0, ValueType.INT, null);
+    Value value0 = new Value(0, TypeLatticeElement.INT, null);
     ConstNumber const0 = new ConstNumber(value0, 0);
-    Value value1 = new Value(1, ValueType.INT, null);
+    Value value1 = new Value(1, TypeLatticeElement.INT, null);
     ConstNumber const1 = new ConstNumber(value1, 1);
-    Value value2 = new Value(2, ValueType.INT, null);
+    Value value2 = new Value(2, TypeLatticeElement.INT, null);
     ConstNumber const2 = new ConstNumber(value2, 2);
-    Value value3 = new Value(2, ValueType.INT, null);
+    Value value3 = new Value(2, TypeLatticeElement.INT, null);
     Add add0 = new Add(NumericType.INT, value3, value0, value1);
     add0.setPosition(Position.none());
     Add add1 = new Add(NumericType.INT, value3, value0, value2);
diff --git a/src/test/java/com/android/tools/r8/ir/regalloc/Regress68656641.java b/src/test/java/com/android/tools/r8/ir/regalloc/Regress68656641.java
index 9866b34..ddbe2c8 100644
--- a/src/test/java/com/android/tools/r8/ir/regalloc/Regress68656641.java
+++ b/src/test/java/com/android/tools/r8/ir/regalloc/Regress68656641.java
@@ -4,10 +4,10 @@
 package com.android.tools.r8.ir.regalloc;
 
 import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.IRCode;
 import com.android.tools.r8.ir.code.Value;
 import com.android.tools.r8.ir.code.ValueNumberGenerator;
-import com.android.tools.r8.ir.code.ValueType;
 import com.android.tools.r8.smali.SmaliBuilder;
 import com.android.tools.r8.smali.SmaliBuilder.MethodSignature;
 import com.android.tools.r8.smali.SmaliTestBase;
@@ -61,18 +61,21 @@
     MyRegisterAllocator allocator = new MyRegisterAllocator(code, options);
     // Setup live an inactive live interval with ranges [0, 10[ and [20, 30[ with only
     // uses in the first interval and which is linked to another interval.
-    LiveIntervals inactiveIntervals = new LiveIntervals(new Value(0, ValueType.INT, null));
+    LiveIntervals inactiveIntervals =
+        new LiveIntervals(new Value(0, TypeLatticeElement.INT, null));
     inactiveIntervals.addRange(new LiveRange(0, 10));
     inactiveIntervals.addUse(new LiveIntervalsUse(0, 10));
     inactiveIntervals.addUse(new LiveIntervalsUse(4, 10));
     inactiveIntervals.addRange(new LiveRange(20, 30));
     inactiveIntervals.setRegister(0);
-    LiveIntervals linked = new LiveIntervals(new Value(1, ValueType.INT, null));
+    LiveIntervals linked =
+        new LiveIntervals(new Value(1, TypeLatticeElement.INT, null));
     linked.setRegister(1);
     inactiveIntervals.link(linked);
     allocator.addInactiveIntervals(inactiveIntervals);
     // Setup an unhandled interval that overlaps the inactive interval.
-    LiveIntervals unhandledIntervals = new LiveIntervals(new Value(2, ValueType.INT, null));
+    LiveIntervals unhandledIntervals =
+        new LiveIntervals(new Value(2, TypeLatticeElement.INT, null));
     unhandledIntervals.addRange(new LiveRange(12, 24));
     // Split the overlapping inactive intervals and check that after the split, the second
     // part of the inactive interval is unhandled and will therefore get a new register
diff --git a/src/test/java/com/android/tools/r8/jasmin/JasminTestBase.java b/src/test/java/com/android/tools/r8/jasmin/JasminTestBase.java
index f106793..cfc49fe 100644
--- a/src/test/java/com/android/tools/r8/jasmin/JasminTestBase.java
+++ b/src/test/java/com/android/tools/r8/jasmin/JasminTestBase.java
@@ -5,6 +5,7 @@
 
 import static org.junit.Assert.fail;
 
+import com.android.tools.r8.CompilationMode;
 import com.android.tools.r8.OutputMode;
 import com.android.tools.r8.R8Command;
 import com.android.tools.r8.TestBase;
@@ -106,6 +107,21 @@
     return ToolHelper.runR8(builder.build(), optionsConsumer);
   }
 
+  protected AndroidApp compileWithR8InDebugMode(
+      JasminBuilder builder,
+      List<String> proguardConfigs,
+      Consumer<InternalOptions> optionsConsumer,
+      Backend backend)
+      throws Exception {
+    R8Command command =
+        ToolHelper.prepareR8CommandBuilder(builder.build(), emptyConsumer(backend))
+            .addLibraryFiles(runtimeJar(backend))
+            .addProguardConfiguration(proguardConfigs, Origin.unknown())
+            .setMode(CompilationMode.DEBUG)
+            .build();
+    return ToolHelper.runR8(command, optionsConsumer);
+  }
+
   protected AndroidApp compileWithR8(
       JasminBuilder builder,
       List<String> proguardConfigs,
diff --git a/src/test/java/com/android/tools/r8/kotlin/KotlinClassInlinerTest.java b/src/test/java/com/android/tools/r8/kotlin/KotlinClassInlinerTest.java
index 67afdd7..6b7a7c2 100644
--- a/src/test/java/com/android/tools/r8/kotlin/KotlinClassInlinerTest.java
+++ b/src/test/java/com/android/tools/r8/kotlin/KotlinClassInlinerTest.java
@@ -10,7 +10,6 @@
 import static org.junit.Assert.assertTrue;
 
 import com.android.tools.r8.ToolHelper.KotlinTargetVersion;
-import com.android.tools.r8.code.InvokeStatic;
 import com.android.tools.r8.code.NewInstance;
 import com.android.tools.r8.code.SgetObject;
 import com.android.tools.r8.graph.DexClass;
@@ -19,9 +18,12 @@
 import com.android.tools.r8.naming.MemberNaming.MethodSignature;
 import com.android.tools.r8.utils.codeinspector.ClassSubject;
 import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import com.android.tools.r8.utils.codeinspector.InstructionSubject;
+import com.android.tools.r8.utils.codeinspector.MethodSubject;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Lists;
 import com.google.common.collect.Sets;
+import com.google.common.collect.Streams;
 import java.util.Collection;
 import java.util.List;
 import java.util.Set;
@@ -229,8 +231,8 @@
   private List<String> collectStaticCalls(ClassSubject clazz, String methodName, String... params) {
     assertNotNull(clazz);
     MethodSignature signature = new MethodSignature(methodName, "void", params);
-    DexCode code = clazz.method(signature).getMethod().getCode().asDexCode();
-    return filterInstructionKind(code, InvokeStatic.class)
+    MethodSubject method = clazz.method(signature);
+    return Streams.stream(method.iterateInstructions(InstructionSubject::isInvokeStatic))
         .map(insn -> insn.getMethod().toSourceString())
         .sorted()
         .collect(Collectors.toList());
diff --git a/src/test/java/com/android/tools/r8/memberrebinding/IndirectSuperInterfaceTest.java b/src/test/java/com/android/tools/r8/memberrebinding/IndirectSuperInterfaceTest.java
new file mode 100644
index 0000000..b280242
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/memberrebinding/IndirectSuperInterfaceTest.java
@@ -0,0 +1,95 @@
+// 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.memberrebinding;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.R8;
+import com.android.tools.r8.R8Command;
+import com.android.tools.r8.R8Command.Builder;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.ToolHelper.ProcessResult;
+import com.android.tools.r8.origin.Origin;
+import com.android.tools.r8.utils.AndroidAppConsumers;
+import com.google.common.collect.ImmutableList;
+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 IndirectSuperInterfaceTest extends TestBase {
+
+  public interface Interface {
+    @NeverInline
+    default void foo() {
+      System.out.print("Interface::foo ");
+    }
+  }
+
+  public static class A implements Interface {
+    // Intentionally empty.
+  }
+
+  public static class B extends A {
+    @Override
+    public void foo() {
+      System.out.print("B::foo ");
+      super.foo();
+    }
+
+    public static void main(String[] args) {
+      new B().foo();
+    }
+  }
+
+  private final Backend backend;
+
+  @Parameters(name = "{0}")
+  public static Backend[] setup() {
+    return new Backend[] {Backend.CF, Backend.DEX};
+  }
+
+  public IndirectSuperInterfaceTest(Backend backend) {
+    this.backend = backend;
+  }
+
+  @Test
+  public void test() throws Exception {
+    String expected = "B::foo Interface::foo ";
+    String reference = runOnJava(B.class);
+    assertEquals(expected, reference);
+
+    AndroidAppConsumers sink = new AndroidAppConsumers();
+    Builder builder =
+        R8Command.builder()
+            .addClassProgramData(ToolHelper.getClassAsBytes(Interface.class), Origin.unknown())
+            .addClassProgramData(ToolHelper.getClassAsBytes(A.class), Origin.unknown())
+            .addClassProgramData(ToolHelper.getClassAsBytes(B.class), Origin.unknown())
+            .setProgramConsumer(sink.wrapProgramConsumer(emptyConsumer(backend)))
+            .addLibraryFiles(runtimeJar(backend))
+            .addProguardConfiguration(
+                ImmutableList.of(
+                    "-keep class " + Interface.class.getTypeName(),
+                    "-keep class " + A.class.getTypeName(),
+                    keepMainProguardConfigurationWithInliningAnnotation(B.class)),
+                Origin.unknown());
+    ToolHelper.allowTestProguardOptions(builder);
+    if (backend == Backend.DEX) {
+      builder.setMinApiLevel(ToolHelper.getMinApiLevelForDexVm().getLevel());
+    }
+    R8.run(builder.build());
+
+    ProcessResult result = runOnVMRaw(sink.build(), B.class, backend);
+
+    // TODO(b/117407667): Assert the test does not fail once fixed.
+    assertTrue(result.toString(), result.exitCode == (backend == Backend.DEX ? 0 : 1));
+    if (result.exitCode == 0) {
+      assertEquals(reference, result.stdout);
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/naming/EnumMinification.java b/src/test/java/com/android/tools/r8/naming/EnumMinification.java
new file mode 100644
index 0000000..a8708eb
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/naming/EnumMinification.java
@@ -0,0 +1,77 @@
+// 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.naming;
+
+import static org.hamcrest.CoreMatchers.containsString;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertThat;
+
+import com.android.tools.r8.R8Command;
+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.ProcessResult;
+import com.android.tools.r8.origin.Origin;
+import com.android.tools.r8.utils.AndroidApp;
+import com.google.common.collect.ImmutableList;
+import java.util.Arrays;
+import java.util.Collection;
+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 EnumMinification extends TestBase {
+
+  private Backend backend;
+
+  @Parameters(name = "Backend: {0}")
+  public static Collection<Backend> data() {
+    return Arrays.asList(Backend.values());
+  }
+
+  public EnumMinification(Backend backend) {
+    this.backend = backend;
+  }
+
+  @Test
+  public void test() throws Exception {
+    AndroidApp output =
+        ToolHelper.runR8(
+            R8Command.builder()
+                .addClassProgramData(ToolHelper.getClassAsBytes(Main.class), Origin.unknown())
+                .addClassProgramData(ToolHelper.getClassAsBytes(Enum.class), Origin.unknown())
+                .addProguardConfiguration(
+                    ImmutableList.of(keepMainProguardConfiguration(Main.class)), Origin.unknown())
+                .setProgramConsumer(emptyConsumer(backend))
+                .build());
+
+    // TODO(117299356): valueOf on enum fails for minified enums.
+    ProcessResult result = runOnVMRaw(output, Main.class, backend);
+    assertEquals(1, result.exitCode);
+    assertThat(
+        result.stderr,
+        containsString(
+            backend == Backend.DEX
+                ? ToolHelper.getDexVm().isNewerThan(DexVm.ART_4_4_4_HOST)
+                    ? "java.lang.NoSuchMethodException"
+                    : "java.lang.NullPointerException"
+                : "java.lang.IllegalArgumentException"));
+  }
+}
+
+class Main {
+
+  public static void main(String[] args) {
+    Enum e = Enum.valueOf("VALUE1");
+    System.out.println(e);
+  }
+}
+
+enum Enum {
+  VALUE1,
+  VALUE2
+}
diff --git a/src/test/java/com/android/tools/r8/naming/MinifierClassSignatureTest.java b/src/test/java/com/android/tools/r8/naming/MinifierClassSignatureTest.java
index 3240365..8d62033 100644
--- a/src/test/java/com/android/tools/r8/naming/MinifierClassSignatureTest.java
+++ b/src/test/java/com/android/tools/r8/naming/MinifierClassSignatureTest.java
@@ -498,7 +498,7 @@
     testSingleClass("Outer", "X", diagnostics -> {
       assertEquals(1, diagnostics.warnings.size());
       DiagnosticsChecker.checkDiagnostic(diagnostics.warnings.get(0), this::isOriginUnknown,
-          "Invalid signature for class Outer", "Expected L at position 1");
+          "Invalid signature 'X' for class Outer", "Expected L at position 1");
     }, inspector -> noSignatureAttribute(inspector.clazz("Outer")));
   }
 
@@ -507,7 +507,7 @@
     testSingleClass("Outer", "<L", diagnostics -> {
       assertEquals(1, diagnostics.warnings.size());
       DiagnosticsChecker.checkDiagnostic(diagnostics.warnings.get(0), this::isOriginUnknown,
-          "Invalid signature for class Outer", "Unexpected end of signature at position 3");
+          "Invalid signature '<L' for class Outer", "Unexpected end of signature at position 3");
     }, inspector -> noSignatureAttribute(inspector.clazz("Outer")));
   }
 
@@ -516,7 +516,7 @@
     testSingleClass("Outer$ExtendsInner", "X", diagnostics -> {
       assertEquals(1, diagnostics.warnings.size());
       DiagnosticsChecker.checkDiagnostic(diagnostics.warnings.get(0), this::isOriginUnknown,
-          "Invalid signature for class Outer$ExtendsInner", "Expected L at position 1");
+          "Invalid signature 'X' for class Outer$ExtendsInner", "Expected L at position 1");
     }, inspector -> noSignatureAttribute(inspector.clazz("Outer$ExtendsInner")));
   }
 
@@ -525,7 +525,7 @@
     testSingleClass("Outer$Inner$ExtendsInnerInner", "X", diagnostics -> {
       assertEquals(1, diagnostics.warnings.size());
       DiagnosticsChecker.checkDiagnostic(diagnostics.warnings.get(0), this::isOriginUnknown,
-          "Invalid signature for class Outer$Inner$ExtendsInnerInner",
+          "Invalid signature 'X' for class Outer$Inner$ExtendsInnerInner",
           "Expected L at position 1");
     }, inspector -> noSignatureAttribute(inspector.clazz("Outer$Inner$ExtendsInnerInner")));
   }
@@ -548,8 +548,11 @@
     String signature = "LOuter<TT;>.com/example/Inner;";
     testSingleClass("Outer$ExtendsInner", signature, diagnostics -> {
       assertEquals(1, diagnostics.warnings.size());
-      DiagnosticsChecker.checkDiagnostic(diagnostics.warnings.get(0), this::isOriginUnknown,
-          "Invalid signature for class Outer$ExtendsInner", "Expected ; at position 16");
+      DiagnosticsChecker.checkDiagnostic(
+          diagnostics.warnings.get(0),
+          this::isOriginUnknown,
+          "Invalid signature '" + signature + "' for class Outer$ExtendsInner",
+          "Expected ; at position 16");
     }, inspector -> {
       noSignatureAttribute(inspector.clazz("Outer$ExtendsInner"));
     });
diff --git a/src/test/java/com/android/tools/r8/naming/MinifierFieldSignatureTest.java b/src/test/java/com/android/tools/r8/naming/MinifierFieldSignatureTest.java
index 4c81632..f73b8d2 100644
--- a/src/test/java/com/android/tools/r8/naming/MinifierFieldSignatureTest.java
+++ b/src/test/java/com/android/tools/r8/naming/MinifierFieldSignatureTest.java
@@ -278,7 +278,7 @@
       assertEquals(1, diagnostics.warnings.size());
       // TODO(sgjesse): The position 2 reported here is one off.
       DiagnosticsChecker.checkDiagnostic(diagnostics.warnings.get(0), this::isOriginUnknown,
-          "Invalid signature for field",
+          "Invalid signature 'X' for field",
           "java.lang.String Fields.anX",
           "Expected L, [ or T at position 2");
     }, inspector -> noSignatureAttribute(lookupAnX(inspector)));
diff --git a/src/test/java/com/android/tools/r8/naming/MinifierMethodSignatureTest.java b/src/test/java/com/android/tools/r8/naming/MinifierMethodSignatureTest.java
index a1ab483..d9d4774 100644
--- a/src/test/java/com/android/tools/r8/naming/MinifierMethodSignatureTest.java
+++ b/src/test/java/com/android/tools/r8/naming/MinifierMethodSignatureTest.java
@@ -299,7 +299,7 @@
     testSingleMethod("generic", "X", diagnostics -> {
       assertEquals(1, diagnostics.warnings.size());
       DiagnosticsChecker.checkDiagnostic(diagnostics.warnings.get(0), this::isOriginUnknown,
-          "Invalid signature for method",
+          "Invalid signature 'X' for method",
           "java.lang.Throwable Methods.generic(java.lang.Throwable, Methods$Inner)",
           "Expected ( at position 1");
     }, inspector -> noSignatureAttribute(lookupGeneric(inspector)));
diff --git a/src/test/java/com/android/tools/r8/naming/NamingTestBase.java b/src/test/java/com/android/tools/r8/naming/NamingTestBase.java
index 932c09b..e340c98 100644
--- a/src/test/java/com/android/tools/r8/naming/NamingTestBase.java
+++ b/src/test/java/com/android/tools/r8/naming/NamingTestBase.java
@@ -75,20 +75,17 @@
 
     ExecutorService executor = ThreadUtils.getExecutorService(1);
 
-    AppInfoWithSubtyping appInfo = appView.appInfo();
-    RootSet rootSet = new RootSetBuilder(appInfo, program, configuration.getRules(), options)
-        .run(executor);
+    RootSet rootSet =
+        new RootSetBuilder(appView, program, configuration.getRules(), options).run(executor);
 
     if (options.proguardConfiguration.isAccessModificationAllowed()) {
       ClassAndMemberPublicizer.run(executor, timing, program, appView, rootSet);
       rootSet =
-          new RootSetBuilder(appInfo, program, configuration.getRules(), options).run(executor);
+          new RootSetBuilder(appView, program, configuration.getRules(), options).run(executor);
     }
 
-    Enqueuer enqueuer =
-        new Enqueuer(
-            appInfo, GraphLense.getIdentityLense(), options, options.forceProguardCompatibility);
-    appInfo = enqueuer.traceApplication(rootSet, executor, timing);
+    Enqueuer enqueuer = new Enqueuer(appView, options, options.forceProguardCompatibility);
+    AppInfoWithSubtyping appInfo = enqueuer.traceApplication(rootSet, executor, timing);
     return new Minifier(appInfo.withLiveness(), rootSet, Collections.emptySet(), options)
         .run(timing);
   }
diff --git a/src/test/java/com/android/tools/r8/resolution/SingleTargetLookupTest.java b/src/test/java/com/android/tools/r8/resolution/SingleTargetLookupTest.java
index fbf4e68..deb91d8 100644
--- a/src/test/java/com/android/tools/r8/resolution/SingleTargetLookupTest.java
+++ b/src/test/java/com/android/tools/r8/resolution/SingleTargetLookupTest.java
@@ -6,6 +6,7 @@
 import com.android.tools.r8.AsmTestBase;
 import com.android.tools.r8.dex.ApplicationReader;
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
+import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexApplication;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexItemFactory;
@@ -102,18 +103,18 @@
     InternalOptions options = new InternalOptions();
     AndroidApp app = readClassesAndAsmDump(CLASSES, ASM_CLASSES);
     DexApplication application = new ApplicationReader(app, options, timing).read().toDirect();
-    AppInfoWithSubtyping appInfoWithSubtyping = new AppInfoWithSubtyping(application);
+    AppView<? extends AppInfoWithSubtyping> appView =
+        new AppView<>(new AppInfoWithSubtyping(application), GraphLense.getIdentityLense());
 
     ExecutorService executor = Executors.newSingleThreadExecutor();
-    RootSet rootSet = new RootSetBuilder(appInfoWithSubtyping, application,
-        buildKeepRuleForClass(Main.class, application.dexItemFactory), options).run(executor);
-    appInfo =
-        new Enqueuer(
-                appInfoWithSubtyping,
-                GraphLense.getIdentityLense(),
-                options,
-                options.forceProguardCompatibility)
-            .traceApplication(rootSet, executor, timing);
+    RootSet rootSet =
+        new RootSetBuilder(
+                appView,
+                application,
+                buildKeepRuleForClass(Main.class, application.dexItemFactory),
+                options)
+            .run(executor);
+    appInfo = new Enqueuer(appView, options).traceApplication(rootSet, executor, timing);
     // We do not run the tree pruner to ensure that the hierarchy is as designed and not modified
     // due to liveness.
   }
diff --git a/src/test/java/com/android/tools/r8/shaking/forceproguardcompatibility/ProguardCompatibilityTestBase.java b/src/test/java/com/android/tools/r8/shaking/forceproguardcompatibility/ProguardCompatibilityTestBase.java
index 24986e1..44527a2 100644
--- a/src/test/java/com/android/tools/r8/shaking/forceproguardcompatibility/ProguardCompatibilityTestBase.java
+++ b/src/test/java/com/android/tools/r8/shaking/forceproguardcompatibility/ProguardCompatibilityTestBase.java
@@ -63,6 +63,14 @@
         || shrinker == Shrinker.R8_CF;
   }
 
+  protected static Backend toBackend(Shrinker shrinker) {
+    if (generatesDex(shrinker)) {
+      return Backend.DEX;
+    }
+    assert generatesCf(shrinker);
+    return Backend.CF;
+  }
+
   protected AndroidApp runShrinker(
       Shrinker mode, List<Class> programClasses, Iterable<String> proguardConfigs)
       throws Exception {
diff --git a/src/test/java/com/android/tools/r8/shaking/forceproguardcompatibility/defaultctor/ExternalizableTest.java b/src/test/java/com/android/tools/r8/shaking/forceproguardcompatibility/defaultctor/ExternalizableTest.java
new file mode 100644
index 0000000..fe2a93f
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/forceproguardcompatibility/defaultctor/ExternalizableTest.java
@@ -0,0 +1,345 @@
+// 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.forceproguardcompatibility.defaultctor;
+
+import static com.android.tools.r8.shaking.forceproguardcompatibility.defaultctor.ExternalizableDataClass.TYPE_1;
+import static com.android.tools.r8.shaking.forceproguardcompatibility.defaultctor.ExternalizableDataClass.TYPE_2;
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.CoreMatchers.containsString;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotEquals;
+import static org.junit.Assert.assertThat;
+
+import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.ToolHelper.ProcessResult;
+import com.android.tools.r8.shaking.forceproguardcompatibility.ProguardCompatibilityTestBase;
+import com.android.tools.r8.utils.AndroidApp;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import com.android.tools.r8.utils.codeinspector.MethodSubject;
+import com.google.common.collect.ImmutableList;
+import java.io.ByteArrayInputStream;
+import java.io.ByteArrayOutputStream;
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.Externalizable;
+import java.io.IOException;
+import java.io.InvalidClassException;
+import java.io.InvalidObjectException;
+import java.io.ObjectInput;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutput;
+import java.io.ObjectOutputStream;
+import java.io.ObjectStreamException;
+import java.io.Serializable;
+import java.util.Collection;
+import java.util.List;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+final class ExternalizableDataClass implements Externalizable {
+  static final byte TYPE_1 = 1;
+  static final byte TYPE_2 = 2;
+
+  private byte byteField;
+  private Object objectField;
+
+  // Default constructor for deserialization
+  public ExternalizableDataClass() {
+  }
+
+  // Constructor for serialization
+  public ExternalizableDataClass(byte byteField, Object objectField) {
+    this.byteField = byteField;
+    this.objectField = objectField;
+  }
+
+  @Override
+  public void writeExternal(ObjectOutput objectOutput) throws IOException {
+    writeInternal(byteField, objectField, objectOutput);
+  }
+
+  private static void writeInternal(byte b, Object obj, DataOutput out) throws IOException {
+    out.writeByte(b);
+    switch (b) {
+      case TYPE_1:
+        ((Delegate1) obj).delegateWrite(out);
+        break;
+      case TYPE_2:
+        ((Delegate2) obj).delegateWrite(out);
+        break;
+      default:
+        throw new InvalidClassException("Unknown type: " + b);
+    }
+  }
+
+  @Override
+  public void readExternal(ObjectInput objectInput) throws IOException {
+    byteField = objectInput.readByte();
+    objectField = readInternal(byteField, objectInput);
+  }
+
+  private static Object readInternal(byte type, DataInput in) throws IOException {
+    switch (type) {
+      case TYPE_1: return Delegate1.delegateRead(in);
+      case TYPE_2: return Delegate2.delegateRead(in);
+      default:
+        throw new InvalidClassException("Unknown type: " + type);
+    }
+  }
+
+  private Object readResolve() {
+    return objectField;
+  }
+
+  @Override
+  public String toString() {
+    return "{ type: " + byteField + ", obj: " + objectField.toString() + " }";
+  }
+}
+
+final class Delegate1 implements Serializable {
+  private int intField;
+
+  private Object writeReplace() {
+    return new ExternalizableDataClass(TYPE_1, this);
+  }
+
+  static Delegate1 of(int intField) {
+    Delegate1 instance = new Delegate1();
+    instance.intField = intField;
+    return instance;
+  }
+
+  void delegateWrite(DataOutput out) throws IOException {
+    out.writeInt(intField);
+  }
+
+  static Object delegateRead(DataInput in) throws IOException {
+    int i = in.readInt();
+    return Delegate1.of(i);
+  }
+
+  private Object readResolve() throws ObjectStreamException {
+    throw new InvalidObjectException("Deserialization via serialization delegate");
+  }
+
+  @Override
+  public String toString() {
+    return "(" + intField + ")";
+  }
+}
+
+final class Delegate2 implements Serializable {
+  private String stringField;
+
+  private Object writeReplace() {
+    return new ExternalizableDataClass(TYPE_2, this);
+  }
+
+  static Delegate2 of(String stringField) {
+    Delegate2 instance = new Delegate2();
+    instance.stringField = stringField;
+    return instance;
+  }
+
+  void delegateWrite(DataOutput out) throws IOException {
+    out.writeUTF(stringField);
+  }
+
+  static Object delegateRead(DataInput in) throws IOException {
+    String s = in.readUTF();
+    return Delegate2.of(s);
+  }
+
+  private Object readResolve() throws ObjectStreamException {
+    throw new InvalidObjectException("Deserialization via serialization delegate");
+  }
+
+  @Override
+  public String toString() {
+    return "<" + stringField + ">";
+  }
+}
+
+class ExternalizableTestMain {
+  public static void main(String[] args) throws Exception {
+    Delegate2 data2 = Delegate2.of("MessageToSerialize");
+    // "Before: <MessageToSerialize>"
+    System.out.println("Before: " + data2.toString());
+
+    // Serialization
+    ByteArrayOutputStream out = new ByteArrayOutputStream();
+    ObjectOutputStream objectOutputStream = new ObjectOutputStream(out);
+    objectOutputStream.writeObject(data2);
+    objectOutputStream.close();
+
+    byte[] byteArray = out.toByteArray();
+
+    // Deserialization
+    ByteArrayInputStream in = new ByteArrayInputStream(byteArray);
+    ObjectInputStream objectInputStream = new ObjectInputStream(in);
+    Object copy = objectInputStream.readObject();
+    assert copy instanceof Delegate2;
+    // "After: <MessageToSerialize>"
+    System.out.println("After: " + copy.toString());
+  }
+}
+
+class NonSerializableSuperClass {
+  protected String tag;
+
+  // Default constructor for deserialization
+  public NonSerializableSuperClass() {
+    this.tag = null;
+  }
+
+  public NonSerializableSuperClass(String tag) {
+    this.tag = tag;
+  }
+
+  @Override
+  public String toString() {
+    return tag == null ? "NULL" : tag;
+  }
+}
+
+class SerializableDataClass extends NonSerializableSuperClass implements Serializable {
+  private String extraTag;
+
+  public SerializableDataClass() {
+    super();
+    this.extraTag = null;
+  }
+
+  public SerializableDataClass(String tag, String extraTag) {
+    super(tag);
+    this.extraTag = extraTag;
+  }
+
+  @Override
+  public String toString() {
+    return super.toString() + ", " + (extraTag == null ? "NULL" : extraTag);
+  }
+}
+
+class SerializableTestMain {
+  public static void main(String[] args) throws Exception {
+    SerializableDataClass data = new SerializableDataClass("TagToSerialize", "ExtraToSerialize");
+    // "Before: TagToSerialize, ExtraToSerialize"
+    System.out.println("Before: " + data.toString());
+
+    // Serialization
+    ByteArrayOutputStream out = new ByteArrayOutputStream();
+    ObjectOutputStream objectOutputStream = new ObjectOutputStream(out);
+    objectOutputStream.writeObject(data);
+    objectOutputStream.close();
+
+    byte[] byteArray = out.toByteArray();
+
+    // Deserialization
+    ByteArrayInputStream in = new ByteArrayInputStream(byteArray);
+    ObjectInputStream objectInputStream = new ObjectInputStream(in);
+    Object copy = objectInputStream.readObject();
+    assert copy instanceof SerializableDataClass;
+    // "After: NULL, ExtraToSerialize"
+    System.out.println("After: " + copy.toString());
+  }
+}
+
+@RunWith(Parameterized.class)
+public class ExternalizableTest extends ProguardCompatibilityTestBase {
+  private final static List<Class> CLASSES_FOR_EXTERNALIZABLE = ImmutableList.of(
+      ExternalizableDataClass.class, Delegate1.class, Delegate2.class, ExternalizableTestMain.class
+  );
+
+  private final static List<Class> CLASSES_FOR_SERIALIZABLE = ImmutableList.of(
+      NonSerializableSuperClass.class, SerializableDataClass.class, SerializableTestMain.class
+  );
+
+  private final Shrinker shrinker;
+
+  @Parameterized.Parameters(name = "Shrinker: {0}")
+  public static Collection<Object> data() {
+    return ImmutableList.of(
+        Shrinker.PROGUARD6_THEN_D8, Shrinker.PROGUARD6, Shrinker.R8, Shrinker.R8_CF);
+  }
+
+  public ExternalizableTest(Shrinker shrinker) {
+    this.shrinker = shrinker;
+  }
+
+  @Test
+  public void testExternalizable() throws Exception {
+    // TODO(b/116735204): R8 should keep default ctor() of classes that implement Externalizable
+    if (isR8(shrinker)) {
+      return;
+    }
+
+    String javaOutput = runOnJava(ExternalizableTestMain.class);
+
+    List<String> config = ImmutableList.of(
+        keepMainProguardConfiguration(ExternalizableTestMain.class),
+        // https://www.guardsquare.com/en/products/proguard/manual/examples#serializable
+        "-keepclassmembers class * implements java.io.Serializable {",
+        //"  private static final java.io.ObjectStreamField[] serialPersistentFields;",
+        "  private void writeObject(java.io.ObjectOutputStream);",
+        "  private void readObject(java.io.ObjectInputStream);",
+        "  java.lang.Object writeReplace();",
+        "  java.lang.Object readResolve();",
+        "}");
+
+    AndroidApp processedApp = runShrinker(shrinker, CLASSES_FOR_EXTERNALIZABLE, config);
+
+    // TODO(b/117302947): Need to update ART binary.
+    if (generatesCf(shrinker)) {
+      String output = runOnVM(
+          processedApp, ExternalizableTestMain.class.getCanonicalName(), toBackend(shrinker));
+      assertEquals(javaOutput.trim(), output.trim());
+    }
+
+    CodeInspector codeInspector = new CodeInspector(processedApp, proguardMap);
+    ClassSubject classSubject = codeInspector.clazz(ExternalizableDataClass.class);
+    assertThat(classSubject, isPresent());
+    MethodSubject init = classSubject.init(ImmutableList.of());
+    assertThat(init, isPresent());
+  }
+
+  @Test
+  public void testSerializable() throws Exception {
+    // TODO(b/116735204): R8 should keep default ctor() of first non-serializable superclass of
+    // serializable class.
+    if (isR8(shrinker)) {
+      return;
+    }
+
+    String javaOutput = runOnJava(SerializableTestMain.class);
+
+    List<String> config = ImmutableList.of(
+        keepMainProguardConfiguration(SerializableTestMain.class),
+        // https://www.guardsquare.com/en/products/proguard/manual/examples#serializable
+        "-keepclassmembers class * implements java.io.Serializable {",
+        //"  private static final java.io.ObjectStreamField[] serialPersistentFields;",
+        "  private void writeObject(java.io.ObjectOutputStream);",
+        "  private void readObject(java.io.ObjectInputStream);",
+        "  java.lang.Object writeReplace();",
+        "  java.lang.Object readResolve();",
+        "}");
+
+    AndroidApp processedApp = runShrinker(shrinker, CLASSES_FOR_SERIALIZABLE, config);
+    // TODO(b/117302947): Need to update ART binary.
+    if (generatesCf(shrinker)) {
+      String output = runOnVM(
+          processedApp, SerializableTestMain.class.getCanonicalName(), toBackend(shrinker));
+      assertEquals(javaOutput.trim(), output.trim());
+    }
+
+    CodeInspector codeInspector = new CodeInspector(processedApp, proguardMap);
+    ClassSubject classSubject = codeInspector.clazz(NonSerializableSuperClass.class);
+    assertThat(classSubject, isPresent());
+    MethodSubject init = classSubject.init(ImmutableList.of());
+    assertThat(init, isPresent());
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/shaking/whyareyoukeeping/WhyAreYouKeepingTest.java b/src/test/java/com/android/tools/r8/shaking/whyareyoukeeping/WhyAreYouKeepingTest.java
index 1a74018..1f06e72 100644
--- a/src/test/java/com/android/tools/r8/shaking/whyareyoukeeping/WhyAreYouKeepingTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/whyareyoukeeping/WhyAreYouKeepingTest.java
@@ -33,7 +33,7 @@
     String expected = String.join(System.lineSeparator(), ImmutableList.of(
         "com.android.tools.r8.shaking.whyareyoukeeping.A",
         "|- is live because referenced in keep rule:",
-        "|    -keep  class com.android.tools.r8.shaking.whyareyoukeeping.A {",
+        "|    -keep class com.android.tools.r8.shaking.whyareyoukeeping.A {",
         "|      *;",
         "|    };",
         ""));
diff --git a/src/test/java/com/android/tools/r8/utils/codeinspector/CfInstructionSubject.java b/src/test/java/com/android/tools/r8/utils/codeinspector/CfInstructionSubject.java
index 3203f9c..dedb839 100644
--- a/src/test/java/com/android/tools/r8/utils/codeinspector/CfInstructionSubject.java
+++ b/src/test/java/com/android/tools/r8/utils/codeinspector/CfInstructionSubject.java
@@ -24,6 +24,8 @@
 import com.android.tools.r8.cf.code.CfStackInstruction;
 import com.android.tools.r8.cf.code.CfSwitch;
 import com.android.tools.r8.cf.code.CfThrow;
+import com.android.tools.r8.graph.DexField;
+import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.ir.code.ValueType;
 import org.objectweb.asm.Opcodes;
 
@@ -40,6 +42,41 @@
   }
 
   @Override
+  public boolean isInstancePut() {
+    return instruction instanceof CfFieldInstruction
+        && ((CfFieldInstruction) instruction).getOpcode() == Opcodes.PUTFIELD;
+  }
+
+  @Override
+  public boolean isStaticPut() {
+    return instruction instanceof CfFieldInstruction
+        && ((CfFieldInstruction) instruction).getOpcode() == Opcodes.PUTSTATIC;
+  }
+
+  @Override
+  public boolean isInstanceGet() {
+    return instruction instanceof CfFieldInstruction
+        && ((CfFieldInstruction) instruction).getOpcode() == Opcodes.GETFIELD;
+  }
+
+  @Override
+  public boolean isStaticGet() {
+    return instruction instanceof CfFieldInstruction
+        && ((CfFieldInstruction) instruction).getOpcode() == Opcodes.GETSTATIC;
+  }
+
+  @Override
+  public DexField getField() {
+    assert isFieldAccess();
+    return ((CfFieldInstruction) instruction).getField();
+  }
+
+  @Override
+  public boolean isInvoke() {
+    return instruction instanceof CfInvoke || instruction instanceof CfInvokeDynamic;
+  }
+
+  @Override
   public boolean isInvokeVirtual() {
     return instruction instanceof CfInvoke
         && ((CfInvoke) instruction).getOpcode() == Opcodes.INVOKEVIRTUAL;
@@ -58,6 +95,12 @@
   }
 
   @Override
+  public DexMethod getMethod() {
+    assert isInvoke();
+    return ((CfInvoke) instruction).getMethod();
+  }
+
+  @Override
   public boolean isNop() {
     return instruction instanceof CfNop;
   }
@@ -105,40 +148,11 @@
   }
 
   @Override
-  public boolean isInvoke() {
-    return instruction instanceof CfInvoke || instruction instanceof CfInvokeDynamic;
-  }
-
-  @Override
   public boolean isNewInstance() {
     return instruction instanceof CfNew;
   }
 
   @Override
-  public boolean isInstancePut() {
-    return instruction instanceof CfFieldInstruction
-        && ((CfFieldInstruction) instruction).getOpcode() == Opcodes.PUTFIELD;
-  }
-
-  @Override
-  public boolean isStaticPut() {
-    return instruction instanceof CfFieldInstruction
-        && ((CfFieldInstruction) instruction).getOpcode() == Opcodes.PUTSTATIC;
-  }
-
-  @Override
-  public boolean isInstanceGet() {
-    return instruction instanceof CfFieldInstruction
-        && ((CfFieldInstruction) instruction).getOpcode() == Opcodes.GETFIELD;
-  }
-
-  @Override
-  public boolean isStaticGet() {
-    return instruction instanceof CfFieldInstruction
-        && ((CfFieldInstruction) instruction).getOpcode() == Opcodes.GETSTATIC;
-  }
-
-  @Override
   public boolean isCheckCast() {
     return instruction instanceof CfCheckCast;
   }
diff --git a/src/test/java/com/android/tools/r8/utils/codeinspector/DexInstructionSubject.java b/src/test/java/com/android/tools/r8/utils/codeinspector/DexInstructionSubject.java
index 4ea699a..e1d74c1 100644
--- a/src/test/java/com/android/tools/r8/utils/codeinspector/DexInstructionSubject.java
+++ b/src/test/java/com/android/tools/r8/utils/codeinspector/DexInstructionSubject.java
@@ -67,6 +67,8 @@
 import com.android.tools.r8.code.SputShort;
 import com.android.tools.r8.code.SputWide;
 import com.android.tools.r8.code.Throw;
+import com.android.tools.r8.graph.DexField;
+import com.android.tools.r8.graph.DexMethod;
 
 public class DexInstructionSubject implements InstructionSubject {
   protected final Instruction instruction;
@@ -81,6 +83,65 @@
   }
 
   @Override
+  public boolean isInstanceGet() {
+    return instruction instanceof Iget
+        || instruction instanceof IgetBoolean
+        || instruction instanceof IgetByte
+        || instruction instanceof IgetShort
+        || instruction instanceof IgetChar
+        || instruction instanceof IgetWide
+        || instruction instanceof IgetObject;
+  }
+
+  @Override
+  public boolean isInstancePut() {
+    return instruction instanceof Iput
+        || instruction instanceof IputBoolean
+        || instruction instanceof IputByte
+        || instruction instanceof IputShort
+        || instruction instanceof IputChar
+        || instruction instanceof IputWide
+        || instruction instanceof IputObject;
+  }
+
+  @Override
+  public boolean isStaticGet() {
+    return instruction instanceof Sget
+        || instruction instanceof SgetBoolean
+        || instruction instanceof SgetByte
+        || instruction instanceof SgetShort
+        || instruction instanceof SgetChar
+        || instruction instanceof SgetWide
+        || instruction instanceof SgetObject;
+  }
+
+  @Override
+  public boolean isStaticPut() {
+    return instruction instanceof Sput
+        || instruction instanceof SputBoolean
+        || instruction instanceof SputByte
+        || instruction instanceof SputShort
+        || instruction instanceof SputChar
+        || instruction instanceof SputWide
+        || instruction instanceof SputObject;
+  }
+
+  @Override
+  public DexField getField() {
+    assert isFieldAccess();
+    return instruction.getField();
+  }
+
+  @Override
+  public boolean isInvoke() {
+    return isInvokeVirtual()
+        || isInvokeInterface()
+        || isInvokeDirect()
+        || isInvokeSuper()
+        || isInvokeStatic();
+  }
+
+  @Override
   public boolean isInvokeVirtual() {
     return instruction instanceof InvokeVirtual || instruction instanceof InvokeVirtualRange;
   }
@@ -95,6 +156,20 @@
     return instruction instanceof InvokeStatic || instruction instanceof InvokeStaticRange;
   }
 
+  public boolean isInvokeSuper() {
+    return instruction instanceof InvokeSuper || instruction instanceof InvokeSuperRange;
+  }
+
+  public boolean isInvokeDirect() {
+    return instruction instanceof InvokeDirect || instruction instanceof InvokeDirectRange;
+  }
+
+  @Override
+  public DexMethod getMethod() {
+    assert isInvoke();
+    return instruction.getMethod();
+  }
+
   @Override
   public boolean isNop() {
     return instruction instanceof Nop;
@@ -147,15 +222,6 @@
   }
 
   @Override
-  public boolean isInvoke() {
-    return isInvokeVirtual()
-        || isInvokeInterface()
-        || isInvokeDirect()
-        || isInvokeSuper()
-        || isInvokeStatic();
-  }
-
-  @Override
   public boolean isNewInstance() {
     return instruction instanceof NewInstance;
   }
@@ -170,63 +236,11 @@
     return isCheckCast() && ((CheckCast) instruction).getType().toString().equals(type);
   }
 
-  public boolean isInvokeSuper() {
-    return instruction instanceof InvokeSuper || instruction instanceof InvokeSuperRange;
-  }
-
-  public boolean isInvokeDirect() {
-    return instruction instanceof InvokeDirect || instruction instanceof InvokeDirectRange;
-  }
-
   public boolean isConst4() {
     return instruction instanceof Const4;
   }
 
   @Override
-  public boolean isInstanceGet() {
-    return instruction instanceof Iget
-        || instruction instanceof IgetBoolean
-        || instruction instanceof IgetByte
-        || instruction instanceof IgetShort
-        || instruction instanceof IgetChar
-        || instruction instanceof IgetWide
-        || instruction instanceof IgetObject;
-  }
-
-  @Override
-  public boolean isInstancePut() {
-    return instruction instanceof Iput
-        || instruction instanceof IputBoolean
-        || instruction instanceof IputByte
-        || instruction instanceof IputShort
-        || instruction instanceof IputChar
-        || instruction instanceof IputWide
-        || instruction instanceof IputObject;
-  }
-
-  @Override
-  public boolean isStaticGet() {
-    return instruction instanceof Sget
-        || instruction instanceof SgetBoolean
-        || instruction instanceof SgetByte
-        || instruction instanceof SgetShort
-        || instruction instanceof SgetChar
-        || instruction instanceof SgetWide
-        || instruction instanceof SgetObject;
-  }
-
-  @Override
-  public boolean isStaticPut() {
-    return instruction instanceof Sput
-        || instruction instanceof SputBoolean
-        || instruction instanceof SputByte
-        || instruction instanceof SputShort
-        || instruction instanceof SputChar
-        || instruction instanceof SputWide
-        || instruction instanceof SputObject;
-  }
-
-  @Override
   public boolean isIf() {
     return instruction instanceof IfEq
         || instruction instanceof IfEqz
diff --git a/src/test/java/com/android/tools/r8/utils/codeinspector/InstructionSubject.java b/src/test/java/com/android/tools/r8/utils/codeinspector/InstructionSubject.java
index e7eaa60..fb0e0d3 100644
--- a/src/test/java/com/android/tools/r8/utils/codeinspector/InstructionSubject.java
+++ b/src/test/java/com/android/tools/r8/utils/codeinspector/InstructionSubject.java
@@ -4,6 +4,9 @@
 
 package com.android.tools.r8.utils.codeinspector;
 
+import com.android.tools.r8.graph.DexField;
+import com.android.tools.r8.graph.DexMethod;
+
 public interface InstructionSubject {
 
   enum JumboStringMode {
@@ -13,12 +16,26 @@
 
   boolean isFieldAccess();
 
+  boolean isInstancePut();
+
+  boolean isStaticPut();
+
+  boolean isInstanceGet();
+
+  boolean isStaticGet();
+
+  DexField getField();
+
+  boolean isInvoke();
+
   boolean isInvokeVirtual();
 
   boolean isInvokeInterface();
 
   boolean isInvokeStatic();
 
+  DexMethod getMethod();
+
   boolean isNop();
 
   boolean isConstString(JumboStringMode jumboStringMode);
@@ -37,18 +54,8 @@
 
   boolean isThrow();
 
-  boolean isInvoke();
-
   boolean isNewInstance();
 
-  boolean isInstancePut();
-
-  boolean isStaticPut();
-
-  boolean isInstanceGet();
-
-  boolean isStaticGet();
-
   boolean isCheckCast();
 
   boolean isCheckCast(String type);
diff --git a/tools/test.py b/tools/test.py
index 6c15ea5..b57d00f 100755
--- a/tools/test.py
+++ b/tools/test.py
@@ -23,32 +23,32 @@
 
 def ParseOptions():
   result = optparse.OptionParser()
-  result.add_option('--no_internal',
+  result.add_option('--no-internal', '--no_internal',
       help='Do not run Google internal tests.',
       default=False, action='store_true')
-  result.add_option('--archive_failures',
+  result.add_option('--archive-failures', '--archive_failures',
       help='Upload test results to cloud storage on failure.',
       default=False, action='store_true')
-  result.add_option('--only_internal',
+  result.add_option('--only-internal', '--only_internal',
       help='Only run Google internal tests.',
       default=False, action='store_true')
-  result.add_option('--all_tests',
+  result.add_option('--all-tests', '--all_tests',
       help='Run tests in all configurations.',
       default=False, action='store_true')
   result.add_option('-v', '--verbose',
       help='Print test stdout to, well, stdout.',
       default=False, action='store_true')
-  result.add_option('--dex_vm',
+  result.add_option('--dex-vm', '--dex_vm',
       help='The android version of the vm to use. "all" will run the tests on '
            'all art vm versions (stopping after first failed execution)',
       default="default",
       choices=ALL_ART_VMS + ["all"])
-  result.add_option('--dex_vm_kind',
+  result.add_option('--dex-vm-kind', '--dex_vm_kind',
                     help='Whether to use host or target version of runtime',
                     default="host",
                     nargs=1,
                     choices=["host", "target"])
-  result.add_option('--one_line_per_test',
+  result.add_option('--one-line-per-test', '--one_line_per_test',
       help='Print a line before a tests starts and after it ends to stdout.',
       default=False, action='store_true')
   result.add_option('--tool',
@@ -58,32 +58,32 @@
   result.add_option('--jctf',
       help='Run JCTF tests with: "r8" (default) or "d8".',
       default=False, action='store_true')
-  result.add_option('--only_jctf',
+  result.add_option('--only-jctf', '--only_jctf',
       help='Run only JCTF tests with: "r8" (default) or "d8".',
       default=False, action='store_true')
-  result.add_option('--jctf_compile_only',
+  result.add_option('--jctf-compile-only', '--jctf_compile_only',
       help="Don't run, only compile JCTF tests.",
       default=False, action='store_true')
-  result.add_option('--aosp_jar',
+  result.add_option('--aosp-jar', '--aosp_jar',
       help='Run aosp_jar test.',
       default=False, action='store_true')
-  result.add_option('--disable_assertions',
+  result.add_option('--disable-assertions', '--disable_assertions',
       help='Disable assertions when running tests.',
       default=False, action='store_true')
-  result.add_option('--with_code_coverage',
+  result.add_option('--with-code-coverage', '--with_code_coverage',
       help='Enable code coverage with Jacoco.',
       default=False, action='store_true')
-  result.add_option('--test_dir',
+  result.add_option('--test-dir', '--test_dir',
       help='Use a custom directory for the test artifacts instead of a'
           ' temporary (which is automatically removed after the test).'
           ' Note that the directory will not be cleared before the test.')
-  result.add_option('--java_home',
+  result.add_option('--java-home', '--java_home',
       help='Use a custom java version to run tests.')
-  result.add_option('--generate_golden_files_to',
+  result.add_option('--generate-golden-files-to', '--generate_golden_files_to',
       help='Store dex files produced by tests in the specified directory.'
            ' It is aimed to be read on platforms with no host runtime available'
            ' for comparison.')
-  result.add_option('--use_golden_files_in',
+  result.add_option('--use-golden-files-in', '--use_golden_files_in',
       help='Download golden files hierarchy for this commit in the specified'
            ' location and use them instead of executing on host runtime.')