diff --git a/build.gradle b/build.gradle
index 7ff46eb..272fcdd 100644
--- a/build.gradle
+++ b/build.gradle
@@ -255,9 +255,10 @@
 }
 
 def r8LibPath = "$buildDir/libs/r8lib.jar"
+def r8LibExludeDepsPath = "$buildDir/libs/r8lib-exclude-deps.jar"
 def r8LibGeneratedKeepRulesPath = "$buildDir/generated/keep.txt"
+def r8LibGeneratedKeepRulesExcludeDepsPath = "$buildDir/generated/keep-exclude-deps.txt"
 def r8LibTestPath = "$buildDir/classes/r8libtest"
-def r8TestsJarPath = "$buildDir/libs/r8tests.jar"
 
 def osString = OperatingSystem.current().isLinux() ? "linux" :
         OperatingSystem.current().isMacOsX() ? "mac" : "windows"
@@ -363,8 +364,7 @@
             def outputDir = "${entry.key}/${entryFile}"
             def gzFile = "${outputDir}.tar.gz"
             def sha1File = "${gzFile}.sha1"
-            inputs.file sha1File
-            outputs.file gzFile
+            inputs.files files(sha1File, gzFile)
             outputs.dir outputDir
             executable "bash"
             args "-c", "tools/download_from_x20.py ${sha1File}"
@@ -674,7 +674,6 @@
 }
 
 task testJar(type: ShadowJar, dependsOn: testClasses) {
-    outputs.upToDateWhen { false }
     baseName = "r8tests"
     from sourceSets.test.output
     if (!project.hasProperty('exclude_deps')) {
@@ -682,24 +681,30 @@
     }
 }
 
-task generateR8LibKeepRules(type: Exec) {
-    doFirst {
-        standardOutput new FileOutputStream(r8LibGeneratedKeepRulesPath)
+task testJarNoDeps(type: ShadowJar, dependsOn: testClasses) {
+    baseName = "r8tests-exclude-deps"
+    from sourceSets.test.output
+}
+
+def generateR8LibKeepRules(name, r8Source, testSource, output) {
+    return tasks.create("generateR8LibKeepRules_" + name, Exec) {
+        doFirst {
+            standardOutput new FileOutputStream(output)
+        }
+        dependsOn r8WithRelocatedDeps
+        dependsOn r8Source
+        dependsOn testSource
+        dependsOn downloadOpenJDKrt
+        inputs.files ([r8WithRelocatedDeps.outputs, r8Source.outputs, testSource.outputs])
+        outputs.file output
+        commandLine baseR8CommandLine([
+                "printuses",
+                "--keeprules",
+                "third_party/openjdk/openjdk-rt-1.8/rt.jar",
+                r8Source.outputs.files[0],
+                testSource.outputs.files[0]])
+        workingDir = projectDir
     }
-    def libSourceTask = project.hasProperty('exclude_deps') ? R8NoManifestNoDeps : R8NoManifest
-    dependsOn r8WithRelocatedDeps
-    dependsOn libSourceTask
-    dependsOn testJar
-    dependsOn downloadOpenJDKrt
-    inputs.files ([r8WithRelocatedDeps.outputs, libSourceTask.outputs, testJar.outputs])
-    outputs.file r8LibGeneratedKeepRulesPath
-    commandLine baseR8CommandLine([
-            "printuses",
-            "--keeprules",
-            "third_party/openjdk/openjdk-rt-1.8/rt.jar",
-            libSourceTask.outputs.files[0],
-            testJar.outputs.files[0]])
-    workingDir = projectDir
 }
 
 task R8LibApiOnly {
@@ -707,29 +712,40 @@
     outputs.file r8LibPath
 }
 
-task R8LibNoDeps {
-    dependsOn r8LibCreateTask(
-            "NoDeps",
-            "src/main/keep.txt",
-            R8NoManifestNoDeps,
-            r8LibPath,
-            ["--pg-conf", generateR8LibKeepRules.outputs.files[0]],
-            repackageDepsNoRelocate.outputs.files
-    ).dependsOn(repackageDepsNoRelocate, generateR8LibKeepRules)
-    outputs.file r8LibPath
-}
-
 task R8Lib {
+    def genRulesTask = generateR8LibKeepRules(
+            "Main",
+            R8NoManifest,
+            testJar,
+            r8LibGeneratedKeepRulesPath)
     dependsOn r8LibCreateTask(
             "Main",
             "src/main/keep.txt",
             R8NoManifest,
             r8LibPath,
-            ["--pg-conf", generateR8LibKeepRules.outputs.files[0]]
-    ).dependsOn(generateR8LibKeepRules)
+            ["--pg-conf", genRulesTask.outputs.files[0]]
+    ).dependsOn(genRulesTask)
     outputs.file r8LibPath
 }
 
+task R8LibNoDeps {
+    def genRulesTask = generateR8LibKeepRules(
+            "NoDeps",
+            R8NoManifestNoDeps,
+            testJarNoDeps,
+            r8LibGeneratedKeepRulesExcludeDepsPath
+    )
+    dependsOn r8LibCreateTask(
+            "NoDeps",
+            "src/main/keep.txt",
+            R8NoManifestNoDeps,
+            r8LibExludeDepsPath,
+            ["--pg-conf", genRulesTask.outputs.files[0]],
+            repackageDepsNoRelocate.outputs.files
+    ).dependsOn(repackageDepsNoRelocate, genRulesTask)
+    outputs.file r8LibExludeDepsPath
+}
+
 task CompatDxLib {
     dependsOn r8LibCreateTask(
             "CompatDx", "src/main/keep-compatdx.txt", CompatDx, "build/libs/compatdxlib.jar")
@@ -1413,7 +1429,7 @@
 
 task configureTestForR8Lib(type: Copy) {
     dependsOn testJar
-    inputs.file r8TestsJarPath
+    inputs.file "$buildDir/libs/r8tests.jar"
     if (getR8LibTask() != null) {
         dependsOn getR8LibTask()
         delete r8LibTestPath
diff --git a/src/main/java/com/android/tools/r8/Version.java b/src/main/java/com/android/tools/r8/Version.java
index 7686444..87886de 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.22-dev";
+  public static final String LABEL = "1.5.0-dev";
 
   private Version() {
   }
diff --git a/src/main/java/com/android/tools/r8/cf/TypeVerificationHelper.java b/src/main/java/com/android/tools/r8/cf/TypeVerificationHelper.java
index 53907db..2349a3b 100644
--- a/src/main/java/com/android/tools/r8/cf/TypeVerificationHelper.java
+++ b/src/main/java/com/android/tools/r8/cf/TypeVerificationHelper.java
@@ -8,6 +8,7 @@
 import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.Nullability;
 import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.Argument;
 import com.android.tools.r8.ir.code.ConstNumber;
@@ -219,7 +220,7 @@
   }
 
   private TypeLatticeElement getLatticeElement(DexType type) {
-    return TypeLatticeElement.fromDexType(type, true, appInfo);
+    return TypeLatticeElement.fromDexType(type, Nullability.maybeNull(), appInfo);
   }
 
   public Map<Value, TypeInfo> computeVerificationTypes() {
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 4934336..4db858b 100644
--- a/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
+++ b/src/main/java/com/android/tools/r8/graph/DexEncodedMethod.java
@@ -684,9 +684,7 @@
   public DexEncodedMethod toStaticMethodWithoutThis() {
     checkIfObsolete();
     assert !accessFlags.isStatic();
-    Builder builder = builder(this);
-    builder.setStatic();
-    builder.withoutThisParameter();
+    Builder builder = builder(this).setStatic().unsetOptimizationInfo().withoutThisParameter();
     setObsolete();
     return builder.build();
   }
@@ -1256,17 +1254,24 @@
       this.method = method;
     }
 
-    public void setStatic() {
+    public Builder setStatic() {
       this.accessFlags.setStatic();
+      return this;
     }
 
-    public void withoutThisParameter() {
+    public Builder unsetOptimizationInfo() {
+      optimizationInfo = DefaultOptimizationInfoImpl.DEFAULT_INSTANCE;
+      return this;
+    }
+
+    public Builder withoutThisParameter() {
       assert code != null;
       if (code.isDexCode()) {
         code = code.asDexCode().withoutThisParameter();
       } else {
         throw new Unreachable("Code " + code.getClass().getSimpleName() + " is not supported.");
       }
+      return this;
     }
 
     public void setCode(Code code) {
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 acf3e05..72c6903 100644
--- a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
+++ b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
@@ -3,6 +3,8 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.graph;
 
+import static com.android.tools.r8.ir.analysis.type.Nullability.maybeNull;
+
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.dex.Marker;
 import com.android.tools.r8.graph.DexDebugEvent.AdvanceLine;
@@ -17,6 +19,7 @@
 import com.android.tools.r8.graph.DexMethodHandle.MethodHandleType;
 import com.android.tools.r8.ir.analysis.type.ArrayTypeLatticeElement;
 import com.android.tools.r8.ir.analysis.type.ClassTypeLatticeElement;
+import com.android.tools.r8.ir.analysis.type.Nullability;
 import com.android.tools.r8.ir.analysis.type.ReferenceTypeLatticeElement;
 import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.Position;
@@ -993,40 +996,43 @@
   }
 
   public ReferenceTypeLatticeElement createReferenceTypeLatticeElement(
-      DexType type, boolean isNullable, AppInfo appInfo) {
-    ReferenceTypeLatticeElement typeLattice = referenceTypeLatticeElements.get(type);
-    if (typeLattice != null) {
-      return isNullable == typeLattice.isNullable() ? typeLattice
-          : typeLattice.getOrCreateDualLattice();
+      DexType type, Nullability nullability, AppInfo appInfo) {
+    ReferenceTypeLatticeElement primary = referenceTypeLatticeElements.get(type);
+    if (primary != null) {
+      return nullability == primary.nullability()
+          ? primary
+          : primary.getOrCreateVariant(nullability);
     }
     synchronized (type) {
-      typeLattice = referenceTypeLatticeElements.get(type);
-      if (typeLattice == null) {
+      primary = referenceTypeLatticeElements.get(type);
+      if (primary == null) {
         if (type.isClassType()) {
           if (!type.isUnknown() && type.isInterface()) {
-            typeLattice = new ClassTypeLatticeElement(
-                appInfo.dexItemFactory.objectType, isNullable, ImmutableSet.of(type));
+            primary = new ClassTypeLatticeElement(objectType, maybeNull(), ImmutableSet.of(type));
           } else {
             // In theory, `interfaces` is the least upper bound of implemented interfaces.
             // It is expensive to walk through type hierarchy; collect implemented interfaces; and
             // compute the least upper bound of two interface sets. Hence, lazy computations.
             // Most likely during lattice join. See {@link ClassTypeLatticeElement#getInterfaces}.
-            typeLattice = new ClassTypeLatticeElement(type, isNullable, appInfo);
+            primary = new ClassTypeLatticeElement(type, maybeNull(), appInfo);
           }
         } else {
           assert type.isArrayType();
           DexType elementType = type.toArrayElementType(this);
           TypeLatticeElement elementTypeLattice =
-              TypeLatticeElement.fromDexType(elementType, true, appInfo, true);
-          typeLattice = new ArrayTypeLatticeElement(elementTypeLattice, isNullable);
+              TypeLatticeElement.fromDexType(elementType, maybeNull(), appInfo, true);
+          primary = new ArrayTypeLatticeElement(elementTypeLattice, maybeNull());
         }
-        referenceTypeLatticeElements.put(type, typeLattice);
+        referenceTypeLatticeElements.put(type, primary);
       }
+      // Make sure that canonicalized version is MAYBE_NULL variant.
+      assert primary.nullability().isMaybeNull();
     }
-    // The call to getOrCreateDualLattice can't be under the DexType synchronized block, since that
+    // The call to getOrCreateVariant can't be under the DexType synchronized block, since that
     // can create deadlocks with ClassTypeLatticeElement::getInterfaces (both lock on the lattice).
-    return isNullable == typeLattice.isNullable() ? typeLattice
-        : typeLattice.getOrCreateDualLattice();
+    return nullability == primary.nullability()
+        ? primary
+        : primary.getOrCreateVariant(nullability);
   }
 
   private static <S extends PresortedComparable<S>> void assignSortedIndices(Collection<S> items,
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/TypeChecker.java b/src/main/java/com/android/tools/r8/ir/analysis/TypeChecker.java
index be7709c..53a6245 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/TypeChecker.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/TypeChecker.java
@@ -73,7 +73,7 @@
             : instruction.asStaticPut().inValue();
     TypeLatticeElement valueType = value.getTypeLattice();
     TypeLatticeElement fieldType = TypeLatticeElement.fromDexType(
-        instruction.getField().type, valueType.isNullable(), appInfo);
+        instruction.getField().type, valueType.nullability(), appInfo);
     if (isSubtypeOf(valueType, fieldType)) {
       return true;
     }
@@ -91,13 +91,14 @@
   public boolean check(Throw instruction) {
     TypeLatticeElement valueType = instruction.exception().getTypeLattice();
     TypeLatticeElement throwableType = TypeLatticeElement.fromDexType(
-        appInfo.dexItemFactory.throwableType, valueType.isNullable(), appInfo);
+        appInfo.dexItemFactory.throwableType, valueType.nullability(), appInfo);
     return isSubtypeOf(valueType, throwableType);
   }
 
   private boolean isSubtypeOf(
       TypeLatticeElement expectedSubtype, TypeLatticeElement expectedSupertype) {
-    return expectedSubtype.lessThanOrEqual(expectedSupertype, appInfo)
+    return (expectedSubtype.isNullType() && expectedSupertype.isReference())
+        || expectedSubtype.lessThanOrEqual(expectedSupertype, appInfo)
         || expectedSubtype.isBasedOnMissingClass(appInfo);
   }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/ArrayTypeLatticeElement.java b/src/main/java/com/android/tools/r8/ir/analysis/type/ArrayTypeLatticeElement.java
index 6bb13a7..a88a71d 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
@@ -3,6 +3,9 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.analysis.type;
 
+import static com.android.tools.r8.ir.analysis.type.Nullability.definitelyNotNull;
+import static com.android.tools.r8.ir.analysis.type.Nullability.maybeNull;
+
 import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexType;
@@ -11,8 +14,9 @@
 
   private final TypeLatticeElement memberTypeLattice;
 
-  public ArrayTypeLatticeElement(TypeLatticeElement memberTypeLattice, boolean isNullable) {
-    super(isNullable, null);
+  public ArrayTypeLatticeElement(
+      TypeLatticeElement memberTypeLattice, Nullability nullability) {
+    super(nullability, null);
     this.memberTypeLattice = memberTypeLattice;
   }
 
@@ -55,28 +59,21 @@
   }
 
   @Override
-  public ReferenceTypeLatticeElement getOrCreateDualLattice() {
-    if (dual != null) {
-      return dual;
+  ReferenceTypeLatticeElement createVariant(Nullability nullability) {
+    if (this.nullability == nullability) {
+      return this;
     }
-    synchronized (this) {
-      if (dual == null) {
-        ArrayTypeLatticeElement dual =
-            new ArrayTypeLatticeElement(memberTypeLattice, !isNullable());
-        linkDualLattice(this, dual);
-      }
-    }
-    return this.dual;
+    return new ArrayTypeLatticeElement(memberTypeLattice, nullability);
   }
 
   @Override
   public TypeLatticeElement asNullable() {
-    return isNullable() ? this : getOrCreateDualLattice();
+    return nullability.isNullable() ? this : getOrCreateVariant(maybeNull());
   }
 
   @Override
   public TypeLatticeElement asNonNullable() {
-    return !isNullable() ? this : getOrCreateDualLattice();
+    return nullability.isDefinitelyNotNull() ? this : getOrCreateVariant(definitelyNotNull());
   }
 
   @Override
@@ -108,7 +105,7 @@
       return false;
     }
     ArrayTypeLatticeElement other = (ArrayTypeLatticeElement) o;
-    if (isNullable() != other.isNullable()) {
+    if (nullability() != other.nullability()) {
       return false;
     }
     if (type != null && other.type != null && !type.equals(other.type)) {
@@ -129,21 +126,21 @@
       // Return null indicating the join is the same as the member to avoid object allocation.
       return null;
     }
-    boolean isNullable = isNullable() || other.isNullable();
+    Nullability nullability = nullability().join(other.nullability());
     if (aMember.isArrayType() && bMember.isArrayType()) {
       ReferenceTypeLatticeElement join =
           aMember.asArrayTypeLatticeElement().join(bMember.asArrayTypeLatticeElement(), appInfo);
-      return join == null ? null : new ArrayTypeLatticeElement(join, isNullable);
+      return join == null ? null : new ArrayTypeLatticeElement(join, nullability);
     }
     if (aMember.isClassType() && bMember.isClassType()) {
       ClassTypeLatticeElement join =
           aMember.asClassTypeLatticeElement().join(bMember.asClassTypeLatticeElement(), appInfo);
-      return join == null ? null : new ArrayTypeLatticeElement(join, isNullable);
+      return join == null ? null : new ArrayTypeLatticeElement(join, nullability);
     }
     if (aMember.isPrimitive() || bMember.isPrimitive()) {
-      return objectClassType(appInfo, isNullable);
+      return objectClassType(appInfo, nullability);
     }
-    return objectArrayType(appInfo, isNullable);
+    return objectArrayType(appInfo, nullability);
   }
 
 }
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 e86d66f..c44aa34 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
@@ -9,13 +9,9 @@
 public class BottomTypeLatticeElement extends TypeLatticeElement {
   private static final BottomTypeLatticeElement INSTANCE = new BottomTypeLatticeElement();
 
-  private BottomTypeLatticeElement() {
-    super(true);
-  }
-
   @Override
-  public TypeLatticeElement asNullable() {
-    return this;
+  public Nullability nullability() {
+    return Nullability.maybeNull();
   }
 
   static BottomTypeLatticeElement getInstance() {
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 c25395d..34ef919 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,6 +3,9 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.analysis.type;
 
+import static com.android.tools.r8.ir.analysis.type.Nullability.definitelyNotNull;
+import static com.android.tools.r8.ir.analysis.type.Nullability.maybeNull;
+
 import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexType;
@@ -20,17 +23,22 @@
   private Set<DexType> lazyInterfaces;
   private AppInfo appInfoForLazyInterfacesComputation;
 
-  public ClassTypeLatticeElement(DexType classType, boolean isNullable, Set<DexType> interfaces) {
-    this(classType, isNullable, interfaces, null);
+  public ClassTypeLatticeElement(
+      DexType classType, Nullability nullability, Set<DexType> interfaces) {
+    this(classType, nullability, interfaces, null);
   }
 
-  public ClassTypeLatticeElement(DexType classType, boolean isNullable, AppInfo appInfo) {
-    this(classType, isNullable, null, appInfo);
+  public ClassTypeLatticeElement(
+      DexType classType, Nullability nullability, AppInfo appInfo) {
+    this(classType, nullability, null, appInfo);
   }
 
   private ClassTypeLatticeElement(
-      DexType classType, boolean isNullable, Set<DexType> interfaces, AppInfo appInfo) {
-    super(isNullable, classType);
+      DexType classType,
+      Nullability nullability,
+      Set<DexType> interfaces,
+      AppInfo appInfo) {
+    super(nullability, classType);
     assert classType.isClassType();
     appInfoForLazyInterfacesComputation = appInfo;
     lazyInterfaces = interfaces;
@@ -57,29 +65,22 @@
   }
 
   @Override
-  public ReferenceTypeLatticeElement getOrCreateDualLattice() {
-    if (dual != null) {
-      return dual;
+  ReferenceTypeLatticeElement createVariant(Nullability nullability) {
+    if (this.nullability == nullability) {
+      return this;
     }
-    synchronized (this) {
-      if (dual == null) {
-        ClassTypeLatticeElement dual =
-            new ClassTypeLatticeElement(
-                type, !isNullable(), lazyInterfaces, appInfoForLazyInterfacesComputation);
-        linkDualLattice(this, dual);
-      }
-    }
-    return this.dual;
+    return new ClassTypeLatticeElement(
+        type, nullability, lazyInterfaces, appInfoForLazyInterfacesComputation);
   }
 
   @Override
   public TypeLatticeElement asNullable() {
-    return isNullable() ? this : getOrCreateDualLattice();
+    return nullability.isNullable() ? this : getOrCreateVariant(maybeNull());
   }
 
   @Override
   public TypeLatticeElement asNonNullable() {
-    return !isNullable() ? this : getOrCreateDualLattice();
+    return nullability.isDefinitelyNotNull() ? this : getOrCreateVariant(definitelyNotNull());
   }
 
   @Override
@@ -126,8 +127,8 @@
     if (lubItfs == null) {
       lubItfs = computeLeastUpperBoundOfInterfaces(appInfo, c1lubItfs, c2lubItfs);
     }
-    boolean isNullable = isNullable() || other.isNullable();
-    return new ClassTypeLatticeElement(lubType, isNullable, lubItfs);
+    Nullability nullability = nullability().join(other.nullability());
+    return new ClassTypeLatticeElement(lubType, nullability, lubItfs);
   }
 
   private enum InterfaceMarker {
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
deleted file mode 100644
index caad0a2..0000000
--- a/src/main/java/com/android/tools/r8/ir/analysis/type/NullLatticeElement.java
+++ /dev/null
@@ -1,65 +0,0 @@
-// 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/Nullability.java b/src/main/java/com/android/tools/r8/ir/analysis/type/Nullability.java
new file mode 100644
index 0000000..c91374d
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/Nullability.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.analysis.type;
+
+import com.android.tools.r8.errors.Unreachable;
+
+/**
+ * Encodes the following lattice.
+ *
+ * <pre>
+ *          MAYBE NULL
+ *          /        \
+ *   DEFINITELY     DEFINITELY
+ *      NULL         NOT NULL
+ * </pre>
+ */
+public class Nullability {
+
+  private static final Nullability DEFINITELY_NULL = new Nullability();
+  private static final Nullability DEFINITELY_NOT_NULL = new Nullability();
+  private static final Nullability MAYBE_NULL = new Nullability();
+
+  private Nullability() {}
+
+  public boolean isDefinitelyNull() {
+    return this == DEFINITELY_NULL;
+  }
+
+  public boolean isDefinitelyNotNull() {
+    return this == DEFINITELY_NOT_NULL;
+  }
+
+  public boolean isMaybeNull() {
+    return this == MAYBE_NULL;
+  }
+
+  public Nullability join(Nullability other) {
+    if (this == other) {
+      return this;
+    }
+    return MAYBE_NULL;
+  }
+
+  public boolean lessThanOrEqual(Nullability other) {
+    return join(other) == other;
+  }
+
+  public boolean isNullable() {
+    return this == MAYBE_NULL || this == DEFINITELY_NULL;
+  }
+
+  public static Nullability definitelyNull() {
+    return DEFINITELY_NULL;
+  }
+
+  public static Nullability definitelyNotNull() {
+    return DEFINITELY_NOT_NULL;
+  }
+
+  public static Nullability maybeNull() {
+    return MAYBE_NULL;
+  }
+
+  @Override
+  public String toString() {
+    if (this == MAYBE_NULL) {
+      return "@Nullable";
+    }
+    if (this == DEFINITELY_NULL) {
+      return "@Null";
+    }
+    if (this == DEFINITELY_NOT_NULL) {
+      return "@NotNull";
+    }
+    throw new Unreachable("Unknown Nullability.");
+  }
+}
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 4c633f5..50b1513 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
@@ -14,13 +14,9 @@
  */
 public abstract class PrimitiveTypeLatticeElement extends TypeLatticeElement {
 
-  PrimitiveTypeLatticeElement() {
-    super(false);
-  }
-
   @Override
-  public TypeLatticeElement asNullable() {
-    return TypeLatticeElement.TOP;
+  public Nullability nullability() {
+    return Nullability.definitelyNotNull();
   }
 
   @Override
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 0db0ca4..2baaa52 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/type/ReferenceTypeLatticeElement.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/ReferenceTypeLatticeElement.java
@@ -11,29 +11,77 @@
 
 public class ReferenceTypeLatticeElement extends TypeLatticeElement {
   private static final ReferenceTypeLatticeElement NULL_INSTANCE =
-      new ReferenceTypeLatticeElement(true, DexItemFactory.nullValueType);
+      new ReferenceTypeLatticeElement(
+          Nullability.definitelyNull(), DexItemFactory.nullValueType);
 
   // TODO(b/72693244): Consider moving this to ClassTypeLatticeElement.
   final DexType type;
 
-  // Link between maybe-null and definitely-not-null reference type lattices.
-  ReferenceTypeLatticeElement dual;
+  final Nullability nullability;
+  // On-demand link between maybe-null (primary) and definitely-null reference type lattices.
+  private ReferenceTypeLatticeElement primaryOrNullVariant;
+  // On-demand link between maybe-null (primary) and definitely-not-null reference type lattices.
+  // This link will be null for non-primary variants.
+  private ReferenceTypeLatticeElement nonNullVariant;
 
-  public ReferenceTypeLatticeElement getOrCreateDualLattice() {
-    throw new Unreachable("Should be defined/used by class/array types.");
-  }
-
-  static void linkDualLattice(ReferenceTypeLatticeElement t1, ReferenceTypeLatticeElement t2) {
-    assert t1.dual == null && t2.dual == null;
-    t1.dual = t2;
-    t2.dual = t1;
-  }
-
-  ReferenceTypeLatticeElement(boolean isNullable, DexType type) {
-    super(isNullable);
+  ReferenceTypeLatticeElement(Nullability nullability, DexType type) {
+    this.nullability = nullability;
     this.type = type;
   }
 
+  public ReferenceTypeLatticeElement getOrCreateVariant(Nullability variantNullability) {
+    if (nullability == variantNullability) {
+      return this;
+    }
+    ReferenceTypeLatticeElement primary = nullability.isMaybeNull() ? this : primaryOrNullVariant;
+    synchronized (this) {
+      // If the link towards the factory-created, canonicalized MAYBE_NULL variant doesn't exist,
+      // we are in the middle of join() computation.
+      if (primary == null) {
+        primary = createVariant(Nullability.maybeNull());
+        linkVariant(primary, this);
+      }
+    }
+    if (variantNullability.isMaybeNull()) {
+      return primary;
+    }
+    synchronized (primary) {
+      ReferenceTypeLatticeElement variant =
+          variantNullability.isDefinitelyNull()
+              ? primary.primaryOrNullVariant
+              : primary.nonNullVariant;
+      if (variant == null) {
+        variant = createVariant(variantNullability);
+        linkVariant(primary, variant);
+      }
+      return variant;
+    }
+  }
+
+  ReferenceTypeLatticeElement createVariant(Nullability nullability) {
+    throw new Unreachable("Should be defined by class/array type lattice element");
+  }
+
+  private static void linkVariant(
+      ReferenceTypeLatticeElement primary, ReferenceTypeLatticeElement variant) {
+    assert primary.nullability().isMaybeNull();
+    assert variant.primaryOrNullVariant == null && variant.nonNullVariant == null;
+    variant.primaryOrNullVariant = primary;
+    if (variant.nullability().isDefinitelyNotNull()) {
+      assert primary.nonNullVariant == null;
+      primary.nonNullVariant = variant;
+    } else {
+      assert variant.nullability().isDefinitelyNull();
+      assert primary.primaryOrNullVariant == null;
+      primary.primaryOrNullVariant = variant;
+    }
+  }
+
+  @Override
+  public Nullability nullability() {
+    return nullability;
+  }
+
   static ReferenceTypeLatticeElement getNullTypeLatticeElement() {
     return NULL_INSTANCE;
   }
@@ -60,7 +108,7 @@
 
   @Override
   public String toString() {
-    return isNullableString() + type.toString();
+    return nullability.toString() + " " + type.toString();
   }
 
   @Override
@@ -72,7 +120,7 @@
       return false;
     }
     ReferenceTypeLatticeElement other = (ReferenceTypeLatticeElement) o;
-    if (this.isNullable() != other.isNullable()) {
+    if (nullability() != other.nullability()) {
       return false;
     }
     if (!type.equals(other.type)) {
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 5221ae3..d0d0c79 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
@@ -9,13 +9,9 @@
 public class TopTypeLatticeElement extends TypeLatticeElement {
   private static final TopTypeLatticeElement INSTANCE = new TopTypeLatticeElement();
 
-  private TopTypeLatticeElement() {
-    super(true);
-  }
-
   @Override
-  public TypeLatticeElement asNullable() {
-    return this;
+  public Nullability nullability() {
+    return Nullability.maybeNull();
   }
 
   static TopTypeLatticeElement getInstance() {
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 dd6a952..00f4af5 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
@@ -3,6 +3,8 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.analysis.type;
 
+import static com.android.tools.r8.ir.analysis.type.Nullability.definitelyNotNull;
+import static com.android.tools.r8.ir.analysis.type.Nullability.maybeNull;
 import static com.android.tools.r8.ir.analysis.type.TypeLatticeElement.fromDexType;
 
 import com.android.tools.r8.graph.AppInfo;
@@ -94,10 +96,10 @@
           // Receiver
           derived = fromDexType(encodedMethod.method.holder,
               // Now we try inlining even when the receiver could be null.
-              encodedMethod != context, appInfo);
+              encodedMethod == context ? definitelyNotNull() : maybeNull(), appInfo);
         } else {
           DexType argType = encodedMethod.method.proto.parameters.values[argumentsSeen];
-          derived = fromDexType(argType, true, appInfo);
+          derived = fromDexType(argType, maybeNull(), appInfo);
         }
         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 14aad66..1544570 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
@@ -28,33 +28,20 @@
   public static final ReferenceTypeLatticeElement NULL =
       ReferenceTypeLatticeElement.getNullTypeLatticeElement();
 
-  // TODO(b/72693244): Switch to NullLatticeElement.
-  private final boolean isNullable;
-
-  TypeLatticeElement(boolean isNullable) {
-    this.isNullable = isNullable;
-  }
-
   public boolean isNullable() {
-    return isNullable;
+    return nullability().isNullable();
   }
 
-  public NullLatticeElement nullElement() {
-    if (isNullType()) {
-      return NullLatticeElement.definitelyNull();
-    }
-    if (!isNullable()) {
-      return NullLatticeElement.definitelyNotNull();
-    }
-    return NullLatticeElement.maybeNull();
-  }
+  public abstract Nullability nullability();
 
   /**
    * Defines how to join with null or switch to nullable lattice element.
    *
    * @return {@link TypeLatticeElement} a result of joining with null.
    */
-  public abstract TypeLatticeElement asNullable();
+  public TypeLatticeElement asNullable() {
+    return isNullable() ? this : TOP;
+  }
 
   /**
    * Defines how to switch to non-nullable lattice element.
@@ -65,10 +52,6 @@
     return BOTTOM;
   }
 
-  String isNullableString() {
-    return isNullable() ? "" : "@NonNull ";
-  }
-
   /**
    * Computes the least upper bound of the current and the other elements.
    *
@@ -107,9 +90,8 @@
     // From now on, this and other are precise reference types, i.e., either ArrayType or ClassType.
     assert isReference() && other.isReference();
     assert isPreciseType() && other.isPreciseType();
-    boolean isNullable = isNullable() || other.isNullable();
     if (getClass() != other.getClass()) {
-      return objectClassType(appInfo, isNullable);
+      return objectClassType(appInfo, nullability().join(other.nullability()));
     }
     // From now on, getClass() == other.getClass()
     if (isArrayType()) {
@@ -136,10 +118,10 @@
   }
 
   public static TypeLatticeElement joinTypes(
-      Iterable<DexType> types, boolean isNullable, AppInfo appInfo) {
+      Iterable<DexType> types, Nullability nullability, AppInfo appInfo) {
     TypeLatticeElement result = BOTTOM;
     for (DexType type : types) {
-      result = result.join(fromDexType(type, isNullable, appInfo), appInfo);
+      result = result.join(fromDexType(type, nullability, appInfo), appInfo);
     }
     return result;
   }
@@ -301,7 +283,7 @@
    * subtype of Throwable.
    */
   public boolean isDefinitelyNull() {
-    return nullElement().isDefinitelyNull();
+    return nullability().isDefinitelyNull();
   }
 
   public int requiredRegisters() {
@@ -309,40 +291,48 @@
     return isWide() ? 2 : 1;
   }
 
-  static ClassTypeLatticeElement objectClassType(AppInfo appInfo, boolean isNullable) {
-    return fromDexType(appInfo.dexItemFactory.objectType, isNullable, appInfo)
+  public static ClassTypeLatticeElement objectClassType(AppInfo appInfo, Nullability nullability) {
+    return fromDexType(appInfo.dexItemFactory.objectType, nullability, appInfo)
         .asClassTypeLatticeElement();
   }
 
-  static ArrayTypeLatticeElement objectArrayType(AppInfo appInfo, boolean isNullable) {
+  static ArrayTypeLatticeElement objectArrayType(AppInfo appInfo, Nullability nullability) {
     return fromDexType(
         appInfo.dexItemFactory.createArrayType(1, appInfo.dexItemFactory.objectType),
-        isNullable,
+        nullability,
         appInfo)
         .asArrayTypeLatticeElement();
   }
 
-  public static TypeLatticeElement classClassType(AppInfo appInfo) {
-    return fromDexType(appInfo.dexItemFactory.classType, false, appInfo);
+  public static ClassTypeLatticeElement classClassType(AppInfo appInfo, Nullability nullability) {
+    return fromDexType(appInfo.dexItemFactory.classType, nullability, appInfo)
+        .asClassTypeLatticeElement();
   }
 
-  public static TypeLatticeElement stringClassType(AppInfo appInfo) {
-    return fromDexType(appInfo.dexItemFactory.stringType, false, appInfo);
-  }
-
-  public static TypeLatticeElement fromDexType(DexType type, boolean isNullable, AppInfo appInfo) {
-    return fromDexType(type, isNullable, appInfo, false);
+  public static ClassTypeLatticeElement stringClassType(AppInfo appInfo, Nullability nullability) {
+    return fromDexType(appInfo.dexItemFactory.stringType, nullability, appInfo)
+        .asClassTypeLatticeElement();
   }
 
   public static TypeLatticeElement fromDexType(
-      DexType type, boolean isNullable, AppInfo appInfo, boolean asArrayElementType) {
+      DexType type, Nullability nullability, AppInfo appInfo) {
+    return fromDexType(type, nullability, appInfo, false);
+  }
+
+  public static TypeLatticeElement fromDexType(
+      DexType type,
+      Nullability nullability,
+      AppInfo appInfo,
+      boolean asArrayElementType) {
     if (type == DexItemFactory.nullValueType) {
+      assert !nullability.isDefinitelyNotNull();
       return NULL;
     }
     if (type.isPrimitiveType()) {
       return PrimitiveTypeLatticeElement.fromDexType(type, asArrayElementType);
     }
-    return appInfo.dexItemFactory.createReferenceTypeLatticeElement(type, isNullable, appInfo);
+    return appInfo.dexItemFactory.createReferenceTypeLatticeElement(
+        type, nullability, appInfo);
   }
 
   public boolean isValueTypeCompatible(TypeLatticeElement other) {
@@ -352,7 +342,7 @@
   }
 
   public TypeLatticeElement checkCast(AppInfo appInfo, DexType castType) {
-    TypeLatticeElement castTypeLattice = fromDexType(castType, isNullable(), appInfo);
+    TypeLatticeElement castTypeLattice = fromDexType(castType, nullability(), appInfo);
     if (lessThanOrEqual(castTypeLattice, appInfo)) {
       return this;
     }
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 1dcd217..a06227e 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
@@ -12,6 +12,7 @@
 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.Nullability;
 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;
@@ -1299,7 +1300,8 @@
 
   public static BasicBlock createRethrowBlock(
       IRCode code, Position position, DexType guard, AppInfo appInfo, InternalOptions options) {
-    TypeLatticeElement guardTypeLattice = TypeLatticeElement.fromDexType(guard, false, appInfo);
+    TypeLatticeElement guardTypeLattice =
+        TypeLatticeElement.fromDexType(guard, Nullability.definitelyNotNull(), appInfo);
     BasicBlock block = new BasicBlock();
     MoveException moveException = new MoveException(
         new Value(code.valueNumberGenerator.next(), guardTypeLattice, null),
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 1f9c5e6..04f56f5 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
@@ -370,8 +370,9 @@
     int i = 0;
     if (downcast != null) {
       Value receiver = invoke.inValues().get(0);
-      TypeLatticeElement castTypeLattice = TypeLatticeElement.fromDexType(
-          downcast, receiver.getTypeLattice().isNullable(), appInfo);
+      TypeLatticeElement castTypeLattice =
+          TypeLatticeElement.fromDexType(
+              downcast, receiver.getTypeLattice().nullability(), appInfo);
       CheckCast castInstruction =
           new CheckCast(code.createValue(castTypeLattice), receiver, downcast);
       castInstruction.setPosition(invoke.getPosition());
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 596fdb8..2578384 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
@@ -128,7 +128,7 @@
 
     TypeLatticeElement outType = outValue().getTypeLattice();
     TypeLatticeElement castType =
-        TypeLatticeElement.fromDexType(getType(), inType.isNullable(), appInfo);
+        TypeLatticeElement.fromDexType(getType(), inType.nullability(), appInfo);
 
     if (inType.lessThanOrEqual(castType, appInfo)) {
       // Cast can be removed. Check that it is sound to replace all users of the out-value by the
@@ -145,7 +145,7 @@
       assert castType.asNullable().equals(outType.asNullable());
 
       // Check soundness of null information.
-      assert inType.nullElement().lessThanOrEqual(outType.nullElement());
+      assert inType.nullability().lessThanOrEqual(outType.nullability());
 
       // Since we cannot remove the cast the in-value must be different from null.
       assert !inType.isNullType();
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 0b8ef55..bd57f29 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
@@ -11,6 +11,7 @@
 import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.Nullability;
 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;
@@ -112,7 +113,7 @@
 
   @Override
   public TypeLatticeElement evaluate(AppInfo appInfo) {
-    return TypeLatticeElement.fromDexType(appInfo.dexItemFactory.classType, false, appInfo);
+    return TypeLatticeElement.classClassType(appInfo, Nullability.definitelyNotNull());
   }
 
   @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 e0b57f1..2aa7f47 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
@@ -10,6 +10,7 @@
 import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.graph.DexMethodHandle;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.Nullability;
 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;
@@ -99,7 +100,8 @@
 
   @Override
   public TypeLatticeElement evaluate(AppInfo appInfo) {
-    return TypeLatticeElement.fromDexType(appInfo.dexItemFactory.methodHandleType, false, appInfo);
+    return TypeLatticeElement.fromDexType(
+        appInfo.dexItemFactory.methodHandleType, Nullability.definitelyNotNull(), appInfo);
   }
 
   @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 fb23503..dd2b4ac 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
@@ -10,6 +10,7 @@
 import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.graph.DexProto;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.Nullability;
 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;
@@ -99,7 +100,8 @@
 
   @Override
   public TypeLatticeElement evaluate(AppInfo appInfo) {
-    return TypeLatticeElement.fromDexType(appInfo.dexItemFactory.methodTypeType, false, appInfo);
+    return TypeLatticeElement.fromDexType(
+        appInfo.dexItemFactory.methodTypeType, Nullability.definitelyNotNull(), appInfo);
   }
 
   @Override
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 18f467c..04e9a1b 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
@@ -10,6 +10,7 @@
 import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.graph.DexString;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.Nullability;
 import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.BasicBlock.ThrowingInfo;
 import com.android.tools.r8.ir.conversion.CfBuilder;
@@ -133,6 +134,6 @@
 
   @Override
   public TypeLatticeElement evaluate(AppInfo appInfo) {
-    return TypeLatticeElement.fromDexType(appInfo.dexItemFactory.stringType, false, appInfo);
+    return TypeLatticeElement.stringClassType(appInfo, Nullability.definitelyNotNull());
   }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/DexItemBasedConstString.java b/src/main/java/com/android/tools/r8/ir/code/DexItemBasedConstString.java
index 2b54a4b..fa4e6c5 100644
--- a/src/main/java/com/android/tools/r8/ir/code/DexItemBasedConstString.java
+++ b/src/main/java/com/android/tools/r8/ir/code/DexItemBasedConstString.java
@@ -10,6 +10,7 @@
 import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.graph.DexReference;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.Nullability;
 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;
@@ -125,6 +126,6 @@
 
   @Override
   public TypeLatticeElement evaluate(AppInfo appInfo) {
-    return TypeLatticeElement.stringClassType(appInfo);
+    return TypeLatticeElement.stringClassType(appInfo, Nullability.definitelyNotNull());
   }
 }
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 f961b80..8e0d572 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
@@ -811,6 +811,11 @@
     return new ConstNumber(out, 0);
   }
 
+  public ConstNumber createConstNull(DebugLocalInfo local) {
+    Value out = createValue(TypeLatticeElement.NULL, local);
+    return new ConstNumber(out, 0);
+  }
+
   public boolean doAllThrowingInstructionsHavePositions() {
     return allThrowingInstructionsHavePositions;
   }
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 bcc9cef..d292aca 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
@@ -20,6 +20,7 @@
 import com.android.tools.r8.graph.DexField;
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.Nullability;
 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;
@@ -133,7 +134,7 @@
 
   @Override
   public TypeLatticeElement evaluate(AppInfo appInfo) {
-    return TypeLatticeElement.fromDexType(getField().type, true, appInfo);
+    return TypeLatticeElement.fromDexType(getField().type, Nullability.maybeNull(), appInfo);
   }
 
   @Override
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 db87c13..48e2659 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
@@ -15,6 +15,7 @@
 import com.android.tools.r8.graph.DexMethodHandle.MethodHandleType;
 import com.android.tools.r8.graph.DexProto;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.Nullability;
 import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import java.util.List;
@@ -266,6 +267,6 @@
     if (returnType.isVoidType()) {
       throw new Unreachable("void methods have no type.");
     }
-    return TypeLatticeElement.fromDexType(returnType, true, appInfo);
+    return TypeLatticeElement.fromDexType(returnType, Nullability.maybeNull(), appInfo);
   }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeMultiNewArray.java b/src/main/java/com/android/tools/r8/ir/code/InvokeMultiNewArray.java
index 2f28110..0c0171f 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeMultiNewArray.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeMultiNewArray.java
@@ -9,6 +9,7 @@
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.Nullability;
 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;
@@ -67,7 +68,7 @@
 
   @Override
   public TypeLatticeElement evaluate(AppInfo appInfo) {
-    return TypeLatticeElement.fromDexType(type, false, appInfo);
+    return TypeLatticeElement.fromDexType(type, Nullability.definitelyNotNull(), appInfo);
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeNewArray.java b/src/main/java/com/android/tools/r8/ir/code/InvokeNewArray.java
index c49650a..fbb7307 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeNewArray.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeNewArray.java
@@ -10,6 +10,7 @@
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.Nullability;
 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;
@@ -97,7 +98,7 @@
 
   @Override
   public TypeLatticeElement evaluate(AppInfo appInfo) {
-    return TypeLatticeElement.fromDexType(type, false, appInfo);
+    return TypeLatticeElement.fromDexType(type, Nullability.definitelyNotNull(), appInfo);
   }
 
   @Override
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 fae3557..325016e 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
@@ -8,6 +8,7 @@
 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.Nullability;
 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;
@@ -102,7 +103,8 @@
 
   @Override
   public TypeLatticeElement evaluate(AppInfo appInfo) {
-    return TypeLatticeElement.fromDexType(exceptionType, false, appInfo);
+    return TypeLatticeElement.fromDexType(
+        exceptionType, Nullability.definitelyNotNull(), appInfo);
   }
 
   public DexType getExceptionType() {
diff --git a/src/main/java/com/android/tools/r8/ir/code/NewArrayEmpty.java b/src/main/java/com/android/tools/r8/ir/code/NewArrayEmpty.java
index 09ea5af..c010973 100644
--- a/src/main/java/com/android/tools/r8/ir/code/NewArrayEmpty.java
+++ b/src/main/java/com/android/tools/r8/ir/code/NewArrayEmpty.java
@@ -10,6 +10,7 @@
 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.Nullability;
 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,6 +108,6 @@
 
   @Override
   public TypeLatticeElement evaluate(AppInfo appInfo) {
-    return TypeLatticeElement.fromDexType(type, false, appInfo);
+    return TypeLatticeElement.fromDexType(type, Nullability.definitelyNotNull(), appInfo);
   }
 }
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 747966c..fca7b7e 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
@@ -9,6 +9,7 @@
 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.Nullability;
 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;
@@ -102,7 +103,7 @@
 
   @Override
   public TypeLatticeElement evaluate(AppInfo appInfo) {
-    return TypeLatticeElement.fromDexType(clazz, false, appInfo);
+    return TypeLatticeElement.fromDexType(clazz, Nullability.definitelyNotNull(), appInfo);
   }
 
   @Override
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 d85e602..20f10a4 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,6 +5,7 @@
 
 import com.android.tools.r8.cf.TypeVerificationHelper.TypeInfo;
 import com.android.tools.r8.graph.AppInfo;
+import com.android.tools.r8.ir.analysis.type.Nullability;
 import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 
 public class StackValue extends Value {
@@ -21,7 +22,8 @@
 
   public static StackValue create(TypeInfo typeInfo, int height, AppInfo appInfo) {
     return new StackValue(
-        typeInfo, TypeLatticeElement.fromDexType(typeInfo.getDexType(), true, appInfo), height);
+        typeInfo, TypeLatticeElement.fromDexType(
+            typeInfo.getDexType(), Nullability.maybeNull(), appInfo), 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 4ea7fe8..af9c5c6 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
@@ -18,6 +18,7 @@
 import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.graph.DexField;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.Nullability;
 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;
@@ -142,7 +143,7 @@
 
   @Override
   public TypeLatticeElement evaluate(AppInfo appInfo) {
-    return TypeLatticeElement.fromDexType(getField().type, true, appInfo);
+    return TypeLatticeElement.fromDexType(getField().type, Nullability.maybeNull(), appInfo);
   }
 
   @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 b5a77c3..f95b988 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
@@ -775,7 +775,7 @@
   public boolean isNeverNull() {
     return neverNull
         || (definition != null && definition.isNonNull())
-        || (typeLattice.isReference() && typeLattice.nullElement().isDefinitelyNotNull());
+        || (typeLattice.isReference() && typeLattice.nullability().isDefinitelyNotNull());
   }
 
   public boolean canBeNull() {
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 88148f0..a745659 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,6 +22,7 @@
 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.Nullability;
 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;
@@ -358,7 +359,8 @@
         builder.addBooleanNonThisArgument(argumentRegister++);
       } else {
         TypeLatticeElement typeLattice =
-            TypeLatticeElement.fromDexType(type, true, builder.getAppInfo());
+            TypeLatticeElement.fromDexType(
+                type, Nullability.maybeNull(), builder.getAppInfo());
         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 24487aa..78e5e7e 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
@@ -41,6 +41,7 @@
 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.Nullability;
 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;
@@ -312,7 +313,7 @@
   private List<TypeLatticeElement> computeArgumentTypes(AppInfo appInfo) {
     List<TypeLatticeElement> types = new ArrayList<>(proto.parameters.size());
     for (DexType type : proto.parameters.values) {
-      types.add(TypeLatticeElement.fromDexType(type, true, appInfo));
+      types.add(TypeLatticeElement.fromDexType(type, Nullability.maybeNull(), appInfo));
     }
     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 835399c..4035611 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
@@ -4,6 +4,9 @@
 
 package com.android.tools.r8.ir.conversion;
 
+import static com.android.tools.r8.ir.analysis.type.Nullability.definitelyNotNull;
+import static com.android.tools.r8.ir.analysis.type.Nullability.maybeNull;
+
 import com.android.tools.r8.ApiLevelException;
 import com.android.tools.r8.errors.CompilationError;
 import com.android.tools.r8.errors.InternalCompilerError;
@@ -25,6 +28,7 @@
 import com.android.tools.r8.graph.GraphLense;
 import com.android.tools.r8.graph.GraphLense.RewrittenPrototypeDescription;
 import com.android.tools.r8.graph.GraphLense.RewrittenPrototypeDescription.RemovedArgumentInfo;
+import com.android.tools.r8.ir.analysis.type.Nullability;
 import com.android.tools.r8.ir.analysis.type.PrimitiveTypeLatticeElement;
 import com.android.tools.r8.ir.analysis.type.TypeAnalysis;
 import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
@@ -174,8 +178,8 @@
     return appInfo;
   }
 
-  public TypeLatticeElement getTypeLattice(DexType type, boolean nullable) {
-    return TypeLatticeElement.fromDexType(type, nullable, appInfo);
+  public TypeLatticeElement getTypeLattice(DexType type, Nullability nullability) {
+    return TypeLatticeElement.fromDexType(type, nullability, appInfo);
   }
 
   // SSA construction uses a worklist of basic blocks reachable from the entry and their
@@ -815,7 +819,7 @@
     Position position = source.getCanonicalDebugPositionAtOffset(moveExceptionItem.targetOffset);
     if (moveExceptionDest >= 0) {
       TypeLatticeElement typeLattice =
-          TypeLatticeElement.fromDexType(moveExceptionItem.guard, false, appInfo);
+          TypeLatticeElement.fromDexType(moveExceptionItem.guard, definitelyNotNull(), appInfo);
       Value out = writeRegister(moveExceptionDest, typeLattice, ThrowingInfo.NO_THROW, null);
       MoveException moveException = new MoveException(out, moveExceptionItem.guard, options);
       moveException.setPosition(position);
@@ -876,8 +880,9 @@
     assert removedArgumentInfo == null; // Removal of receiver not yet supported.
     DebugLocalInfo local = getOutgoingLocal(register);
     boolean receiverCouldBeNull = context != null && context != method;
+    Nullability nullability = receiverCouldBeNull ? maybeNull() : definitelyNotNull();
     TypeLatticeElement receiver =
-        TypeLatticeElement.fromDexType(method.method.getHolder(), receiverCouldBeNull, appInfo);
+        TypeLatticeElement.fromDexType(method.method.getHolder(), nullability, appInfo);
     Value value = writeRegister(register, receiver, ThrowingInfo.NO_THROW, local);
     addInstruction(new Argument(value));
     value.markAsThis(receiverCouldBeNull);
@@ -1048,7 +1053,7 @@
   public void addCheckCast(int value, DexType type) {
     Value in = readRegister(value, ValueTypeConstraint.OBJECT);
     TypeLatticeElement castTypeLattice =
-        TypeLatticeElement.fromDexType(type, in.getTypeLattice().isNullable(), appInfo);
+        TypeLatticeElement.fromDexType(type, in.getTypeLattice().nullability(), appInfo);
     Value out = writeRegister(value, castTypeLattice, ThrowingInfo.CAN_THROW);
     CheckCast instruction = new CheckCast(out, in, type);
     assert instruction.instructionTypeCanThrow();
@@ -1092,7 +1097,8 @@
   }
 
   public void addConstClass(int dest, DexType type) {
-    TypeLatticeElement typeLattice = TypeLatticeElement.classClassType(appInfo);
+    TypeLatticeElement typeLattice =
+        TypeLatticeElement.classClassType(appInfo, definitelyNotNull());
     Value out = writeRegister(dest, typeLattice, ThrowingInfo.CAN_THROW);
     ConstClass instruction = new ConstClass(out, type);
     assert instruction.instructionTypeCanThrow();
@@ -1107,7 +1113,8 @@
           null /* sourceString */);
     }
     TypeLatticeElement typeLattice =
-        TypeLatticeElement.fromDexType(appInfo.dexItemFactory.methodHandleType, false, appInfo);
+        TypeLatticeElement.fromDexType(
+            appInfo.dexItemFactory.methodHandleType, definitelyNotNull(), appInfo);
     Value out = writeRegister(dest, typeLattice, ThrowingInfo.CAN_THROW);
     ConstMethodHandle instruction = new ConstMethodHandle(out, methodHandle);
     add(instruction);
@@ -1121,14 +1128,16 @@
           null /* sourceString */);
     }
     TypeLatticeElement typeLattice =
-        TypeLatticeElement.fromDexType(appInfo.dexItemFactory.methodTypeType, false, appInfo);
+        TypeLatticeElement.fromDexType(
+            appInfo.dexItemFactory.methodTypeType, definitelyNotNull(), appInfo);
     Value out = writeRegister(dest, typeLattice, ThrowingInfo.CAN_THROW);
     ConstMethodType instruction = new ConstMethodType(out, methodType);
     add(instruction);
   }
 
   public void addConstString(int dest, DexString string) {
-    TypeLatticeElement typeLattice = TypeLatticeElement.stringClassType(appInfo);
+    TypeLatticeElement typeLattice =
+        TypeLatticeElement.stringClassType(appInfo, definitelyNotNull());
     ThrowingInfo throwingInfo =
         options.isGeneratingClassFiles() ? ThrowingInfo.NO_THROW : ThrowingInfo.CAN_THROW;
     add(new ConstString(writeRegister(dest, typeLattice, throwingInfo), string, throwingInfo));
@@ -1136,7 +1145,8 @@
 
   public void addDexItemBasedConstString(int dest, DexReference item) {
     assert method.getOptimizationInfo().useIdentifierNameString();
-    TypeLatticeElement typeLattice = TypeLatticeElement.stringClassType(appInfo);
+    TypeLatticeElement typeLattice =
+        TypeLatticeElement.stringClassType(appInfo, definitelyNotNull());
     Value out = writeRegister(dest, typeLattice, ThrowingInfo.CAN_THROW);
     DexItemBasedConstString instruction = new DexItemBasedConstString(out, item);
     add(instruction);
@@ -1322,7 +1332,9 @@
   public void addInstanceGet(int dest, int object, DexField field) {
     Value in = readRegister(object, ValueTypeConstraint.OBJECT);
     Value out = writeRegister(
-        dest, TypeLatticeElement.fromDexType(field.type, true, appInfo), ThrowingInfo.CAN_THROW);
+        dest,
+        TypeLatticeElement.fromDexType(field.type, maybeNull(), appInfo),
+        ThrowingInfo.CAN_THROW);
     out.setKnownToBeBoolean(field.type == getFactory().booleanType);
     InstanceGet instruction = new InstanceGet(out, in, field);
     assert instruction.instructionTypeCanThrow();
@@ -1608,7 +1620,9 @@
     DexType outType = invoke.getReturnType();
     Value outValue =
         writeRegister(
-            dest, TypeLatticeElement.fromDexType(outType, true, appInfo), ThrowingInfo.CAN_THROW);
+            dest,
+            TypeLatticeElement.fromDexType(outType, maybeNull(), appInfo),
+            ThrowingInfo.CAN_THROW);
     outValue.setKnownToBeBoolean(outType.isBooleanType());
     invoke.setOutValue(outValue);
   }
@@ -1638,7 +1652,8 @@
   public void addNewArrayEmpty(int dest, int size, DexType type) {
     assert type.isArrayType();
     Value in = readRegister(size, ValueTypeConstraint.INT);
-    TypeLatticeElement arrayTypeLattice = TypeLatticeElement.fromDexType(type, false, appInfo);
+    TypeLatticeElement arrayTypeLattice =
+        TypeLatticeElement.fromDexType(type, definitelyNotNull(), appInfo);
     Value out = writeRegister(dest, arrayTypeLattice, ThrowingInfo.CAN_THROW);
     NewArrayEmpty instruction = new NewArrayEmpty(out, in, type);
     assert instruction.instructionTypeCanThrow();
@@ -1652,7 +1667,8 @@
   }
 
   public void addNewInstance(int dest, DexType type) {
-    TypeLatticeElement instanceType = TypeLatticeElement.fromDexType(type, false, appInfo);
+    TypeLatticeElement instanceType =
+        TypeLatticeElement.fromDexType(type, definitelyNotNull(), appInfo);
     Value out = writeRegister(dest, instanceType, ThrowingInfo.CAN_THROW);
     NewInstance instruction = new NewInstance(type, out);
     assert instruction.instructionTypeCanThrow();
@@ -1684,7 +1700,9 @@
 
   public void addStaticGet(int dest, DexField field) {
     Value out = writeRegister(
-        dest, TypeLatticeElement.fromDexType(field.type, true, appInfo), ThrowingInfo.CAN_THROW);
+        dest,
+        TypeLatticeElement.fromDexType(field.type, maybeNull(), appInfo),
+        ThrowingInfo.CAN_THROW);
     out.setKnownToBeBoolean(field.type == getFactory().booleanType);
     StaticGet instruction = new StaticGet(out, field);
     assert instruction.instructionTypeCanThrow();
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 42e501a..1387f75 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.Nullability;
 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;
@@ -373,7 +374,8 @@
       builder.addThisArgument(slot.register);
     }
     for (Type type : parameterTypes) {
-      TypeLatticeElement typeLattice = builder.getTypeLattice(application.getType(type), true);
+      TypeLatticeElement typeLattice =
+          builder.getTypeLattice(application.getType(type), Nullability.maybeNull());
       Slot slot = state.readLocal(argumentRegister, type);
       if (type == Type.BOOLEAN_TYPE) {
         builder.addBooleanNonThisArgument(slot.register);
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 5814486..08e4ee5 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.Nullability;
 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;
@@ -283,7 +284,8 @@
     if (lambdaInstanceValue == null) {
       // The out value might be empty in case it was optimized out.
       lambdaInstanceValue = code.createValue(
-          TypeLatticeElement.fromDexType(lambdaClass.type, true, appInfo));
+          TypeLatticeElement.fromDexType(
+              lambdaClass.type, Nullability.maybeNull(), appInfo));
     }
 
     // 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 2be7320..8bad12a 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
@@ -4,6 +4,8 @@
 
 package com.android.tools.r8.ir.desugar;
 
+import static com.android.tools.r8.ir.analysis.type.Nullability.definitelyNotNull;
+
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.errors.CompilationError;
 import com.android.tools.r8.graph.AppInfo;
@@ -338,7 +340,8 @@
 
       // new-instance v0, StringBuilder
       TypeLatticeElement stringBuilderTypeLattice =
-          TypeLatticeElement.fromDexType(factory.stringBuilderType, false, appInfo);
+          TypeLatticeElement.fromDexType(
+              factory.stringBuilderType, definitelyNotNull(), appInfo);
       Value sbInstance = code.createValue(stringBuilderTypeLattice);
       appendInstruction(new NewInstance(factory.stringBuilderType, sbInstance));
 
@@ -360,7 +363,8 @@
       Value concatValue = invokeCustom.outValue();
       if (concatValue == null) {
         // The out value might be empty in case it was optimized out.
-        concatValue = code.createValue(TypeLatticeElement.stringClassType(appInfo));
+        concatValue =
+            code.createValue(TypeLatticeElement.stringClassType(appInfo, definitelyNotNull()));
       }
 
       // Replace the instruction.
@@ -438,7 +442,8 @@
 
       @Override
       Value getOrCreateValue() {
-        Value value = code.createValue(TypeLatticeElement.stringClassType(appInfo));
+        Value value =
+            code.createValue(TypeLatticeElement.stringClassType(appInfo, definitelyNotNull()));
         ThrowingInfo throwingInfo =
             code.options.isGeneratingClassFiles() ? ThrowingInfo.NO_THROW : ThrowingInfo.CAN_THROW;
         appendInstruction(new ConstString(value, factory.createString(str), throwingInfo));
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 5c1fae1..5938781 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
@@ -4,6 +4,8 @@
 
 package com.android.tools.r8.ir.optimize;
 
+import static com.android.tools.r8.ir.analysis.type.Nullability.definitelyNotNull;
+import static com.android.tools.r8.ir.analysis.type.Nullability.maybeNull;
 import static com.android.tools.r8.ir.optimize.ReflectionOptimizer.ClassNameComputationInfo.ClassNameComputationOption.CANONICAL_NAME;
 import static com.android.tools.r8.ir.optimize.ReflectionOptimizer.ClassNameComputationInfo.ClassNameComputationOption.NAME;
 import static com.android.tools.r8.ir.optimize.ReflectionOptimizer.ClassNameComputationInfo.ClassNameComputationOption.SIMPLE_NAME;
@@ -13,6 +15,7 @@
 import com.android.tools.r8.errors.CompilationError;
 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.DebugLocalInfo;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexEncodedField;
@@ -154,6 +157,7 @@
 
   public final IRConverter converter;
   private final AppInfo appInfo;
+  private final AppView<? extends AppInfo> appView;
   private final DexItemFactory dexItemFactory;
   private final Set<DexMethod> libraryMethodsReturningReceiver;
   private final InternalOptions options;
@@ -164,6 +168,7 @@
       InternalOptions options) {
     this.converter = converter;
     this.appInfo = converter.appInfo;
+    this.appView = converter.appView;
     this.options = options;
     this.dexItemFactory = appInfo.dexItemFactory;
     this.libraryMethodsReturningReceiver = libraryMethodsReturningReceiver;
@@ -1570,20 +1575,31 @@
     }
   }
 
-  private boolean checkArgumentType(InvokeMethod invoke, DexMethod target, int argumentIndex) {
-    DexType returnType = invoke.getInvokedMethod().proto.returnType;
+  private boolean checkArgumentType(InvokeMethod invoke, int argumentIndex) {
     // TODO(sgjesse): Insert cast if required.
-    if (invoke.isInvokeStatic()) {
-      return invoke.getInvokedMethod().proto.parameters.values[argumentIndex] == returnType;
+    TypeLatticeElement returnType =
+        TypeLatticeElement.fromDexType(
+            invoke.getInvokedMethod().proto.returnType, maybeNull(), appInfo);
+    TypeLatticeElement argumentType =
+        TypeLatticeElement.fromDexType(
+            getArgumentType(invoke, argumentIndex), maybeNull(), appInfo);
+    if (appView != null && appView.enableWholeProgramOptimizations()) {
+      return argumentType.lessThanOrEqual(returnType, appInfo);
     } else {
-      if (argumentIndex == 0) {
-        return invoke.getInvokedMethod().getHolder() == returnType;
-      } else {
-        return invoke.getInvokedMethod().proto.parameters.values[argumentIndex - 1] == returnType;
-      }
+      return argumentType.equals(returnType);
     }
   }
 
+  private DexType getArgumentType(InvokeMethod invoke, int argumentIndex) {
+    if (invoke.isInvokeStatic()) {
+      return invoke.getInvokedMethod().proto.parameters.values[argumentIndex];
+    }
+    if (argumentIndex == 0) {
+      return invoke.getInvokedMethod().getHolder();
+    }
+    return invoke.getInvokedMethod().proto.parameters.values[argumentIndex - 1];
+  }
+
   // Replace result uses for methods where something is known about what is returned.
   public void rewriteMoveResult(IRCode code) {
     if (options.isGeneratingClassFiles()) {
@@ -1599,7 +1615,7 @@
         InvokeMethod invoke = current.asInvokeMethod();
         if (invoke.outValue() != null && !invoke.outValue().hasLocalInfo()) {
           if (libraryMethodsReturningReceiver.contains(invoke.getInvokedMethod())) {
-            if (checkArgumentType(invoke, invoke.getInvokedMethod(), 0)) {
+            if (checkArgumentType(invoke, 0)) {
               invoke.outValue().replaceUsers(invoke.arguments().get(0));
               invoke.setOutValue(null);
             }
@@ -1613,8 +1629,7 @@
               if (definition != null && definition.getOptimizationInfo().returnsArgument()) {
                 int argumentIndex = definition.getOptimizationInfo().getReturnedArgument();
                 // Replace the out value of the invoke with the argument and ignore the out value.
-                if (argumentIndex != -1
-                    && checkArgumentType(invoke, target.method, argumentIndex)) {
+                if (argumentIndex >= 0 && checkArgumentType(invoke, argumentIndex)) {
                   Value argument = invoke.arguments().get(argumentIndex);
                   Value outValue = invoke.outValue();
                   assert outValue.verifyCompatible(argument.outType());
@@ -2100,9 +2115,9 @@
     TypeLatticeElement inTypeLattice = inValue.getTypeLattice();
     TypeLatticeElement outTypeLattice = outValue.getTypeLattice();
     TypeLatticeElement castTypeLattice =
-        TypeLatticeElement.fromDexType(castType, inTypeLattice.isNullable(), appInfo);
+        TypeLatticeElement.fromDexType(castType, inTypeLattice.nullability(), appInfo);
 
-    assert inTypeLattice.nullElement().lessThanOrEqual(outTypeLattice.nullElement());
+    assert inTypeLattice.nullability().lessThanOrEqual(outTypeLattice.nullability());
 
     if (inTypeLattice.lessThanOrEqual(castTypeLattice, appInfo)) {
       // 1) Trivial cast.
@@ -2152,7 +2167,7 @@
     Value inValue = instanceOf.value();
     TypeLatticeElement inType = inValue.getTypeLattice();
     TypeLatticeElement instanceOfType =
-        TypeLatticeElement.fromDexType(instanceOf.type(), inType.isNullable(), appInfo);
+        TypeLatticeElement.fromDexType(instanceOf.type(), inType.nullability(), appInfo);
 
     InstanceOfResult result = InstanceOfResult.UNKNOWN;
     if (inType.isDefinitelyNull()) {
@@ -3177,13 +3192,12 @@
         InstructionListIterator throwNullInsnIterator = throwNullBlock.listIterator();
 
         // Insert 'null' constant.
-        Value nullValue = code.createValue(TypeLatticeElement.NULL, gotoInsn.getLocalInfo());
-        ConstNumber nullConstant = new ConstNumber(nullValue, 0);
+        ConstNumber nullConstant = code.createConstNull(gotoInsn.getLocalInfo());
         nullConstant.setPosition(insn.getPosition());
         throwNullInsnIterator.add(nullConstant);
 
         // Replace Goto with Throw.
-        Throw notReachableThrow = new Throw(nullValue);
+        Throw notReachableThrow = new Throw(nullConstant.outValue());
         Instruction insnGoto = throwNullInsnIterator.next();
         assert insnGoto.isGoto();
         throwNullInsnIterator.replaceCurrentInstruction(notReachableThrow);
@@ -3486,7 +3500,8 @@
   }
 
   private Value addConstString(IRCode code, InstructionListIterator iterator, String s) {
-    TypeLatticeElement typeLattice = TypeLatticeElement.stringClassType(appInfo);
+    TypeLatticeElement typeLattice =
+        TypeLatticeElement.stringClassType(appInfo, definitelyNotNull());
     Value value = code.createValue(typeLattice);
     ThrowingInfo throwingInfo =
         options.isGeneratingClassFiles() ? ThrowingInfo.NO_THROW : ThrowingInfo.CAN_THROW;
@@ -3519,7 +3534,7 @@
     DexType javaLangSystemType = dexItemFactory.createType("Ljava/lang/System;");
     DexType javaIoPrintStreamType = dexItemFactory.createType("Ljava/io/PrintStream;");
     Value out = code.createValue(
-        TypeLatticeElement.fromDexType(javaIoPrintStreamType, false, appInfo));
+        TypeLatticeElement.fromDexType(javaIoPrintStreamType, definitelyNotNull(), appInfo));
 
     DexProto proto = dexItemFactory.createProto(dexItemFactory.voidType, dexItemFactory.objectType);
     DexMethod print = dexItemFactory.createMethod(javaIoPrintStreamType, proto, "print");
@@ -3584,7 +3599,7 @@
         iterator.add(new InvokeVirtual(print, null, ImmutableList.of(out, nul)));
         iterator = isNotNullBlock.listIterator();
         iterator.setInsertionPosition(position);
-        value = code.createValue(TypeLatticeElement.classClassType(appInfo));
+        value = code.createValue(TypeLatticeElement.classClassType(appInfo, definitelyNotNull()));
         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 6da387f..b6bc6c3 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
@@ -143,7 +143,7 @@
           TypeLatticeElement receiverTypeLattice = receiver.getTypeLattice();
           TypeLatticeElement castTypeLattice =
               TypeLatticeElement.fromDexType(
-                  holderType, receiverTypeLattice.isNullable(), appView.appInfo());
+                  holderType, receiverTypeLattice.nullability(), appView.appInfo());
           // 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.
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 41faa04..4da9f8d 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
@@ -14,6 +14,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.Nullability;
 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.ConstNumber;
@@ -80,7 +81,8 @@
     if (replacement == null && rule != null
         && rule.hasReturnValue() && rule.getReturnValue().isField()) {
       DexField field = rule.getReturnValue().getField();
-      assert TypeLatticeElement.fromDexType(field.type, true, appInfo) == typeLattice;
+      assert typeLattice
+          == TypeLatticeElement.fromDexType(field.type, Nullability.maybeNull(), appInfo);
       DexEncodedField staticField = appInfo.lookupStaticTarget(field.clazz, field);
       if (staticField != null) {
         Value value = code.createValue(typeLattice, instruction.getLocalInfo());
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 7966d3a..4ab54e9 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
@@ -4,6 +4,9 @@
 
 package com.android.tools.r8.ir.optimize;
 
+import static com.android.tools.r8.ir.analysis.type.Nullability.definitelyNotNull;
+import static com.android.tools.r8.ir.analysis.type.Nullability.maybeNull;
+
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.AppInfo;
@@ -357,7 +360,7 @@
     @Override
     public int createInstruction(IRBuilder builder, Outline outline, int argumentMapIndex) {
       TypeLatticeElement latticeElement =
-          TypeLatticeElement.fromDexType(clazz, false, builder.getAppInfo());
+          TypeLatticeElement.fromDexType(clazz, definitelyNotNull(), builder.getAppInfo());
       Value outValue =
           builder.writeRegister(outline.argumentCount(), latticeElement, ThrowingInfo.CAN_THROW);
       Instruction newInstruction = new NewInstance(clazz, outValue);
@@ -493,7 +496,8 @@
       Value outValue = null;
       if (hasOutValue) {
         TypeLatticeElement latticeElement =
-            TypeLatticeElement.fromDexType(method.proto.returnType, true, builder.getAppInfo());
+            TypeLatticeElement.fromDexType(
+                method.proto.returnType, maybeNull(), builder.getAppInfo());
         outValue =
             builder.writeRegister(outline.argumentCount(), latticeElement, ThrowingInfo.CAN_THROW);
       }
@@ -1398,7 +1402,7 @@
       // Fill in the Argument instructions in the argument block.
       for (int i = 0; i < outline.argumentTypes.size(); i++) {
         TypeLatticeElement typeLattice =
-            TypeLatticeElement.fromDexType(outline.argumentTypes.get(i), true, appInfo);
+            TypeLatticeElement.fromDexType(outline.argumentTypes.get(i), maybeNull(), appInfo);
         builder.addNonThisArgument(i, typeLattice);
       }
       builder.flushArgumentInstructions();
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/ReflectionOptimizer.java b/src/main/java/com/android/tools/r8/ir/optimize/ReflectionOptimizer.java
index 511b077..fe09444 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/ReflectionOptimizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/ReflectionOptimizer.java
@@ -3,6 +3,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.optimize;
 
+import static com.android.tools.r8.ir.analysis.type.Nullability.definitelyNotNull;
 import static com.android.tools.r8.utils.DescriptorUtils.getCanonicalNameFromDescriptor;
 import static com.android.tools.r8.utils.DescriptorUtils.getClassNameFromDescriptor;
 import static com.android.tools.r8.utils.DescriptorUtils.getSimpleClassNameFromDescriptor;
@@ -124,7 +125,8 @@
         if (constraints == ConstraintWithTarget.NEVER) {
           continue;
         }
-        TypeLatticeElement typeLattice = TypeLatticeElement.classClassType(appInfo);
+        TypeLatticeElement typeLattice =
+            TypeLatticeElement.classClassType(appInfo, definitelyNotNull());
         Value value = code.createValue(typeLattice, invoke.getLocalInfo());
         ConstClass constClass = new ConstClass(value, type);
         it.replaceCurrentInstruction(constClass);
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/UninstantiatedTypeOptimization.java b/src/main/java/com/android/tools/r8/ir/optimize/UninstantiatedTypeOptimization.java
index 6a43c03..14be4f3 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/UninstantiatedTypeOptimization.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/UninstantiatedTypeOptimization.java
@@ -23,6 +23,7 @@
 import com.android.tools.r8.graph.GraphLense.RewrittenPrototypeDescription.RemovedArgumentInfo;
 import com.android.tools.r8.graph.GraphLense.RewrittenPrototypeDescription.RemovedArgumentsInfo;
 import com.android.tools.r8.graph.TopDownClassHierarchyTraversal;
+import com.android.tools.r8.ir.analysis.type.Nullability;
 import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.code.BasicBlock;
 import com.android.tools.r8.ir.code.CatchHandlers;
@@ -455,7 +456,8 @@
                 : instruction.asStaticPut().inValue();
 
         TypeLatticeElement fieldLatticeType =
-            TypeLatticeElement.fromDexType(fieldType, true, appView.appInfo());
+            TypeLatticeElement.fromDexType(
+                fieldType, Nullability.maybeNull(), appView.appInfo());
         if (!value.getTypeLattice().lessThanOrEqual(fieldLatticeType, appView.appInfo())) {
           // Broken type hierarchy. See FieldTypeTest#test_brokenTypeHierarchy.
           assert options.testing.allowTypeErrors;
@@ -532,15 +534,14 @@
 
     // Insert constant null before the instruction.
     instructionIterator.previous();
-    Value nullValue = new Value(code.valueNumberGenerator.next(), TypeLatticeElement.NULL, null);
-    ConstNumber constNumberInstruction = new ConstNumber(nullValue, 0);
+    ConstNumber constNumberInstruction = code.createConstNull();
     // Note that we only keep position info for throwing instructions in release mode.
     constNumberInstruction.setPosition(options.debug ? instruction.getPosition() : Position.none());
     instructionIterator.add(constNumberInstruction);
     instructionIterator.next();
 
     // Replace the instruction by throw.
-    Throw throwInstruction = new Throw(nullValue);
+    Throw throwInstruction = new Throw(constNumberInstruction.outValue());
     for (Value inValue : instruction.inValues()) {
       if (inValue.hasLocalInfo()) {
         // Add this value as a debug value to avoid changing its live range.
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 75d579c..425ce11 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
@@ -4,6 +4,8 @@
 
 package com.android.tools.r8.ir.optimize.classinliner;
 
+import static com.android.tools.r8.ir.analysis.type.Nullability.maybeNull;
+
 import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.graph.DexField;
 import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
@@ -92,7 +94,7 @@
           new Phi(
               code.valueNumberGenerator.next(),
               block,
-              TypeLatticeElement.fromDexType(field.type, true, appInfo),
+              TypeLatticeElement.fromDexType(field.type, maybeNull(), appInfo),
               null,
               RegisterReadType.NORMAL);
       ins.put(block, phi);
@@ -140,7 +142,8 @@
     assert root == valueProducingInsn;
     if (defaultValue == null) {
       // If we met newInstance it means that default value is supposed to be used.
-      defaultValue = code.createValue(TypeLatticeElement.fromDexType(field.type, true, appInfo));
+      defaultValue = code.createValue(
+          TypeLatticeElement.fromDexType(field.type, maybeNull(), appInfo));
       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/kotlin/KotlinLambdaGroupCodeStrategy.java b/src/main/java/com/android/tools/r8/ir/optimize/lambda/kotlin/KotlinLambdaGroupCodeStrategy.java
index c137cfd..71fbf44 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
@@ -4,6 +4,9 @@
 
 package com.android.tools.r8.ir.optimize.lambda.kotlin;
 
+import static com.android.tools.r8.ir.analysis.type.Nullability.definitelyNotNull;
+import static com.android.tools.r8.ir.analysis.type.Nullability.maybeNull;
+
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.DexField;
 import com.android.tools.r8.graph.DexItemFactory;
@@ -115,7 +118,8 @@
     NewInstance patchedNewInstance = new NewInstance(
         group.getGroupClassType(),
         context.code.createValue(
-            TypeLatticeElement.fromDexType(newInstance.clazz, false, context.appInfo)));
+            TypeLatticeElement.fromDexType(
+                newInstance.clazz, definitelyNotNull(), context.appInfo)));
     context.instructions().replaceCurrentInstruction(patchedNewInstance);
   }
 
@@ -162,7 +166,7 @@
     // 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.
     TypeLatticeElement castTypeLattice =
-        TypeLatticeElement.fromDexType(fieldType, false, context.appInfo);
+        TypeLatticeElement.fromDexType(fieldType, definitelyNotNull(), context.appInfo);
     Value newValue = context.code.createValue(castTypeLattice, newInstanceGet.getLocalInfo());
     newInstanceGet.outValue().replaceUsers(newValue);
     CheckCast cast = new CheckCast(newValue, newInstanceGet.outValue(), fieldType);
@@ -188,7 +192,7 @@
     context.instructions().replaceCurrentInstruction(
         new StaticGet(
             context.code.createValue(
-                TypeLatticeElement.fromDexType(staticGet.getField().type, true, context.appInfo)),
+                TypeLatticeElement.fromDexType(staticGet.getField().type, maybeNull(), context.appInfo)),
             mapSingletonInstanceField(context.factory, staticGet.getField())));
   }
 
@@ -223,7 +227,7 @@
   private Value createValueForType(CodeProcessor context, DexType returnType) {
     return returnType == context.factory.voidType ? null :
         context.code.createValue(
-            TypeLatticeElement.fromDexType(returnType, true, context.appInfo));
+            TypeLatticeElement.fromDexType(returnType, maybeNull(), context.appInfo));
   }
 
   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 fa0b28a..59d8717 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
@@ -4,6 +4,8 @@
 
 package com.android.tools.r8.ir.optimize.staticizer;
 
+import static com.android.tools.r8.ir.analysis.type.Nullability.maybeNull;
+
 import com.android.tools.r8.graph.DebugLocalInfo;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexEncodedField;
@@ -411,7 +413,8 @@
           it.replaceCurrentInstruction(
               new StaticGet(
                   code.createValue(
-                      TypeLatticeElement.fromDexType(field.type, true, classStaticizer.appInfo),
+                      TypeLatticeElement.fromDexType(
+                          field.type, maybeNull(), classStaticizer.appInfo),
                       outValue.getLocalInfo()),
                   field
               )
@@ -439,7 +442,7 @@
           Value newOutValue = method.proto.returnType.isVoidType() ? null
               : code.createValue(
                   TypeLatticeElement.fromDexType(
-                      method.proto.returnType, true, classStaticizer.appInfo),
+                      method.proto.returnType, maybeNull(), classStaticizer.appInfo),
                   outValue == null ? null : outValue.getLocalInfo());
           it.replaceCurrentInstruction(
               new InvokeStatic(newMethod, newOutValue, invoke.inValues()));
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/string/StringOptimizer.java b/src/main/java/com/android/tools/r8/ir/optimize/string/StringOptimizer.java
index cdd85e4..0ff9331 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/string/StringOptimizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/string/StringOptimizer.java
@@ -3,6 +3,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.optimize.string;
 
+import static com.android.tools.r8.ir.analysis.type.Nullability.definitelyNotNull;
 import static com.android.tools.r8.ir.optimize.CodeRewriter.removeOrReplaceByDebugLocalWrite;
 import static com.android.tools.r8.ir.optimize.ReflectionOptimizer.ClassNameComputationInfo.ClassNameComputationOption.CANONICAL_NAME;
 import static com.android.tools.r8.ir.optimize.ReflectionOptimizer.ClassNameComputationInfo.ClassNameComputationOption.NAME;
@@ -242,7 +243,9 @@
       }
       if (name != null) {
         Value stringValue =
-            code.createValue(TypeLatticeElement.stringClassType(appInfo), invoke.getLocalInfo());
+            code.createValue(
+                TypeLatticeElement.stringClassType(appInfo, definitelyNotNull()),
+                invoke.getLocalInfo());
         ConstString constString =
             new ConstString(stringValue, factory.createString(name), throwingInfo);
         it.replaceCurrentInstruction(constString);
@@ -307,11 +310,13 @@
         TypeLatticeElement inType = in.getTypeLattice();
         if (inType.isNullType()) {
           Value nullStringValue =
-              code.createValue(TypeLatticeElement.stringClassType(appInfo), invoke.getLocalInfo());
+              code.createValue(
+                  TypeLatticeElement.stringClassType(appInfo, definitelyNotNull()),
+                  invoke.getLocalInfo());
           ConstString nullString = new ConstString(
               nullStringValue, factory.createString("null"), throwingInfo);
           it.replaceCurrentInstruction(nullString);
-        } else if (inType.nullElement().isDefinitelyNotNull()
+        } else if (inType.nullability().isDefinitelyNotNull()
             && inType.isClassType()
             && inType.asClassTypeLatticeElement().getClassType().equals(factory.stringType)) {
           Value out = invoke.outValue();
@@ -330,7 +335,7 @@
         assert invoke.inValues().size() == 1;
         Value in = invoke.getReceiver();
         TypeLatticeElement inType = in.getTypeLattice();
-        if (inType.nullElement().isDefinitelyNotNull()
+        if (inType.nullability().isDefinitelyNotNull()
             && inType.isClassType()
             && inType.asClassTypeLatticeElement().getClassType().equals(factory.stringType)) {
           Value out = invoke.outValue();
diff --git a/src/main/java/com/android/tools/r8/ir/regalloc/SpillMoveSet.java b/src/main/java/com/android/tools/r8/ir/regalloc/SpillMoveSet.java
index fa82d2b..8489866 100644
--- a/src/main/java/com/android/tools/r8/ir/regalloc/SpillMoveSet.java
+++ b/src/main/java/com/android/tools/r8/ir/regalloc/SpillMoveSet.java
@@ -5,6 +5,7 @@
 package com.android.tools.r8.ir.regalloc;
 
 import com.android.tools.r8.graph.AppInfo;
+import com.android.tools.r8.ir.analysis.type.Nullability;
 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;
@@ -44,8 +45,7 @@
   public SpillMoveSet(LinearScanRegisterAllocator allocator, IRCode code, AppInfo appInfo) {
     this.allocator = allocator;
     this.code = code;
-    this.objectType =
-        TypeLatticeElement.fromDexType(appInfo.dexItemFactory.objectType, true, appInfo);
+    this.objectType = TypeLatticeElement.objectClassType(appInfo, Nullability.maybeNull());
     for (BasicBlock block : code.blocks) {
       blockStartMap.put(block.entry().getNumber(), block);
     }
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 88bbc6c..8f51777 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.Nullability;
 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;
@@ -187,7 +188,8 @@
       receiverValue =
           builder.writeRegister(
               receiverRegister,
-              TypeLatticeElement.fromDexType(receiver, false, builder.getAppInfo()),
+              TypeLatticeElement.fromDexType(
+                  receiver, Nullability.definitelyNotNull(), builder.getAppInfo()),
               NO_THROW);
       builder.add(new Argument(receiverValue));
       receiverValue.markAsThis(false);
@@ -198,7 +200,8 @@
     for (int i = 0; i < parameters.length; i++) {
       // TODO(zerny): Why does this not call builder.addNonThisArgument?
       TypeLatticeElement typeLattice =
-          TypeLatticeElement.fromDexType(parameters[i], true, builder.getAppInfo());
+          TypeLatticeElement.fromDexType(
+              parameters[i], Nullability.maybeNull(), builder.getAppInfo());
       Value paramValue = builder.writeRegister(paramRegisters[i], typeLattice, NO_THROW);
       paramValues[i] = paramValue;
       builder.add(new Argument(paramValue));
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 361c8b7..eadec82 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
@@ -3,7 +3,10 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.analysis.type;
 
+import static com.android.tools.r8.ir.analysis.type.Nullability.definitelyNotNull;
+import static com.android.tools.r8.ir.analysis.type.Nullability.maybeNull;
 import static com.android.tools.r8.ir.analysis.type.TypeLatticeElement.fromDexType;
+import static com.android.tools.r8.ir.analysis.type.TypeLatticeElement.stringClassType;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertTrue;
@@ -121,9 +124,9 @@
       DexType mainClass = appInfo.dexItemFactory.createType(
           DescriptorUtils.javaTypeToDescriptor(NonNullAfterInvoke.class.getCanonicalName()));
       Map<Class<? extends Instruction>, TypeLatticeElement> expectedLattices = ImmutableMap.of(
-          InvokeVirtual.class, fromDexType(appInfo.dexItemFactory.stringType, true, appInfo),
-          NonNull.class, fromDexType(appInfo.dexItemFactory.stringType, false, appInfo),
-          NewInstance.class, fromDexType(assertionErrorType, false, appInfo));
+          InvokeVirtual.class, stringClassType(appInfo, maybeNull()),
+          NonNull.class, stringClassType(appInfo, definitelyNotNull()),
+          NewInstance.class, fromDexType(assertionErrorType, definitelyNotNull(), appInfo));
       forEachOutValue(irCode, (v, l) -> verifyClassTypeLattice(expectedLattices, mainClass, v, l));
     });
   }
@@ -137,9 +140,9 @@
       DexType mainClass = appInfo.dexItemFactory.createType(
           DescriptorUtils.javaTypeToDescriptor(NonNullAfterInvoke.class.getCanonicalName()));
       Map<Class<? extends Instruction>, TypeLatticeElement> expectedLattices = ImmutableMap.of(
-          InvokeVirtual.class, fromDexType(appInfo.dexItemFactory.stringType, true, appInfo),
-          NonNull.class, fromDexType(appInfo.dexItemFactory.stringType, false, appInfo),
-          NewInstance.class, fromDexType(assertionErrorType, false, appInfo));
+          InvokeVirtual.class, stringClassType(appInfo, maybeNull()),
+          NonNull.class, stringClassType(appInfo, definitelyNotNull()),
+          NewInstance.class, fromDexType(assertionErrorType, definitelyNotNull(), appInfo));
       forEachOutValue(irCode, (v, l) -> verifyClassTypeLattice(expectedLattices, mainClass, v, l));
     });
   }
@@ -154,8 +157,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.dexItemFactory.stringType, true, appInfo),
-          NewInstance.class, fromDexType(assertionErrorType, false, appInfo));
+          ArrayGet.class, fromDexType(appInfo.dexItemFactory.stringType, maybeNull(), appInfo),
+          NewInstance.class, fromDexType(assertionErrorType, definitelyNotNull(), appInfo));
       forEachOutValue(irCode, (v, l) -> {
         if (l.isArrayType()) {
           ArrayTypeLatticeElement lattice = l.asArrayTypeLatticeElement();
@@ -183,8 +186,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.dexItemFactory.stringType, true, appInfo),
-          NewInstance.class, fromDexType(assertionErrorType, false, appInfo));
+          ArrayGet.class, fromDexType(appInfo.dexItemFactory.stringType, maybeNull(), appInfo),
+          NewInstance.class, fromDexType(assertionErrorType, definitelyNotNull(), appInfo));
       forEachOutValue(irCode, (v, l) -> {
         if (l.isArrayType()) {
           ArrayTypeLatticeElement lattice = l.asArrayTypeLatticeElement();
@@ -213,11 +216,11 @@
       DexType testClass = appInfo.dexItemFactory.createType(
           DescriptorUtils.javaTypeToDescriptor(FieldAccessTest.class.getCanonicalName()));
       Map<Class<? extends Instruction>, TypeLatticeElement> expectedLattices = ImmutableMap.of(
-          Argument.class, fromDexType(testClass, true, appInfo),
-          NonNull.class, fromDexType(testClass, false, appInfo),
+          Argument.class, fromDexType(testClass, maybeNull(), appInfo),
+          NonNull.class, fromDexType(testClass, definitelyNotNull(), appInfo),
           // instance may not be initialized.
-          InstanceGet.class, fromDexType(appInfo.dexItemFactory.stringType, true, appInfo),
-          NewInstance.class, fromDexType(assertionErrorType, false, appInfo));
+          InstanceGet.class, fromDexType(appInfo.dexItemFactory.stringType, maybeNull(), appInfo),
+          NewInstance.class, fromDexType(assertionErrorType, definitelyNotNull(), appInfo));
       forEachOutValue(irCode, (v, l) -> verifyClassTypeLattice(expectedLattices, mainClass, v, l));
     });
   }
@@ -233,11 +236,11 @@
       DexType testClass = appInfo.dexItemFactory.createType(
           DescriptorUtils.javaTypeToDescriptor(FieldAccessTest.class.getCanonicalName()));
       Map<Class<? extends Instruction>, TypeLatticeElement> expectedLattices = ImmutableMap.of(
-          Argument.class, fromDexType(testClass, true, appInfo),
-          NonNull.class, fromDexType(testClass, false, appInfo),
+          Argument.class, fromDexType(testClass, maybeNull(), appInfo),
+          NonNull.class, fromDexType(testClass, definitelyNotNull(), appInfo),
           // instance may not be initialized.
-          InstanceGet.class, fromDexType(appInfo.dexItemFactory.stringType, true, appInfo),
-          NewInstance.class, fromDexType(assertionErrorType, false, appInfo));
+          InstanceGet.class, fromDexType(appInfo.dexItemFactory.stringType, maybeNull(), appInfo),
+          NewInstance.class, fromDexType(assertionErrorType, definitelyNotNull(), appInfo));
       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 09f6a01..d85b8dd 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
@@ -3,6 +3,8 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.analysis.type;
 
+import static com.android.tools.r8.ir.analysis.type.Nullability.definitelyNotNull;
+import static com.android.tools.r8.ir.analysis.type.Nullability.maybeNull;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertNotNull;
@@ -282,9 +284,9 @@
     DexType test = appInfo.dexItemFactory.createType("LTest;");
     Map<Class<? extends Instruction>, TypeLatticeElement> expectedLattices = ImmutableMap.of(
         ArrayLength.class, INT,
-        ConstString.class, TypeLatticeElement.stringClassType(appInfo),
-        CheckCast.class, TypeLatticeElement.fromDexType(test, true, appInfo),
-        NewInstance.class, TypeLatticeElement.fromDexType(test, false, appInfo));
+        ConstString.class, TypeLatticeElement.stringClassType(appInfo, definitelyNotNull()),
+        CheckCast.class, TypeLatticeElement.fromDexType(test, maybeNull(), appInfo),
+        NewInstance.class, TypeLatticeElement.fromDexType(test, definitelyNotNull(), appInfo));
     IRCode irCode =
         method.buildIR(appInfo, GraphLense.getIdentityLense(), TEST_OPTIONS, Origin.unknown());
     TypeAnalysis analysis = new TypeAnalysis(appInfo, method);
@@ -313,9 +315,9 @@
             .getMethod();
     DexType test = appInfo.dexItemFactory.createType("LTest;");
     Map<Class<? extends Instruction>, TypeLatticeElement> expectedLattices = ImmutableMap.of(
-      ConstString.class, TypeLatticeElement.stringClassType(appInfo),
+      ConstString.class, TypeLatticeElement.stringClassType(appInfo, definitelyNotNull()),
       InstanceOf.class, INT,
-      StaticGet.class, TypeLatticeElement.fromDexType(test, true, appInfo));
+      StaticGet.class, TypeLatticeElement.fromDexType(test, maybeNull(), appInfo));
     IRCode irCode =
         method.buildIR(appInfo, GraphLense.getIdentityLense(), TEST_OPTIONS, Origin.unknown());
     TypeAnalysis analysis = new TypeAnalysis(appInfo, method);
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 fbfc09b..3aa4394 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
@@ -76,7 +76,7 @@
   }
 
   private TypeLatticeElement element(DexType type) {
-    return TypeLatticeElement.fromDexType(type, true, appInfo);
+    return TypeLatticeElement.fromDexType(type, Nullability.maybeNull(), appInfo);
   }
 
   private ArrayTypeLatticeElement array(int nesting, DexType base) {
@@ -506,7 +506,8 @@
   @Test
   public void testSelfOrderWithoutSubtypingInfo() {
     DexType type = appInfo.dexItemFactory.createType("Lmy/Type;");
-    TypeLatticeElement nonNullType = fromDexType(type, false, appInfo);
+    TypeLatticeElement nonNullType =
+        fromDexType(type, Nullability.definitelyNotNull(), appInfo);
     TypeLatticeElement nullableType = nonNullType.asNullable();
     // TODO(zerny): Once the null lattice is used for null info check that the class-type null is
     // also more specific that the nullableType.
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 6f22e21..3582403 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
@@ -9,6 +9,7 @@
 import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.graph.DexApplication;
 import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.ir.analysis.type.Nullability;
 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;
@@ -129,7 +130,12 @@
     block0.setNumber(0);
     Value value =
         new Value(
-            0, TypeLatticeElement.fromDexType(DexItemFactory.catchAllType, false, appInfo), null);
+            0,
+            TypeLatticeElement.fromDexType(
+                DexItemFactory.catchAllType,
+                Nullability.definitelyNotNull(),
+                appInfo),
+            null);
     instruction = new Argument(value);
     instruction.setPosition(position);
     block0.add(instruction);
diff --git a/src/test/java/com/android/tools/r8/ir/regalloc/RegisterMoveSchedulerTest.java b/src/test/java/com/android/tools/r8/ir/regalloc/RegisterMoveSchedulerTest.java
index 929dfaa..80a3285 100644
--- a/src/test/java/com/android/tools/r8/ir/regalloc/RegisterMoveSchedulerTest.java
+++ b/src/test/java/com/android/tools/r8/ir/regalloc/RegisterMoveSchedulerTest.java
@@ -9,6 +9,7 @@
 import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.graph.DexApplication;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.Nullability;
 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;
@@ -328,7 +329,8 @@
     InternalOptions options = new InternalOptions();
     AppInfo appInfo = new AppInfo(DexApplication.builder(options.itemFactory, null).build());
     TypeLatticeElement objectType =
-        TypeLatticeElement.fromDexType(options.itemFactory.objectType, true, appInfo);
+        TypeLatticeElement.fromDexType(
+            options.itemFactory.objectType, Nullability.maybeNull(), appInfo);
     CollectMovesIterator moves = new CollectMovesIterator();
     int temp = 42;
     RegisterMoveScheduler scheduler = new RegisterMoveScheduler(moves, temp);
diff --git a/tools/archive.py b/tools/archive.py
index ce04494..d8fb4d0 100755
--- a/tools/archive.py
+++ b/tools/archive.py
@@ -91,12 +91,6 @@
   if not utils.is_bot() and not options.dry_run:
     raise Exception('You are not a bot, don\'t archive builds')
 
-  # Generate an r8-ed build without dependencies.
-  # The '-Pno_internal' flag is important because we generate the lib based on uses in tests.
-  gradle.RunGradleExcludeDeps([utils.R8LIB_NO_DEPS, '-Pno_internal'])
-  shutil.copyfile(utils.R8LIB_JAR, utils.R8LIB_EXCLUDE_DEPS_JAR)
-  shutil.copyfile(utils.R8LIB_JAR + '.map', utils.R8LIB_EXCLUDE_DEPS_JAR + '.map')
-
   # Create maven release which uses a build that exclude dependencies.
   create_maven_release.main(["--out", utils.LIBS])
 
@@ -114,6 +108,7 @@
     utils.COMPATDX,
     utils.COMPATPROGUARD,
     utils.R8LIB,
+    utils.R8LIB_NO_DEPS,
     utils.COMPATDXLIB,
     utils.COMPATPROGUARDLIB,
     '-Pno_internal'
diff --git a/tools/as_utils.py b/tools/as_utils.py
index 7b373f4..d5db8a3 100644
--- a/tools/as_utils.py
+++ b/tools/as_utils.py
@@ -5,6 +5,7 @@
 
 from distutils.version import LooseVersion
 import os
+import shutil
 
 import utils
 
@@ -62,3 +63,43 @@
     for line in lines:
       if (utils.R8_JAR not in line) and (utils.R8LIB_JAR not in line):
         f.write(line)
+
+def Move(src, dst):
+  print('Moving `{}` to `{}`'.format(src, dst))
+  dst_parent = os.path.dirname(dst)
+  if not os.path.isdir(dst_parent):
+    os.makedirs(dst_parent)
+  elif os.path.isdir(dst):
+    shutil.rmtree(dst)
+  elif os.path.isfile(dst):
+    os.remove(dst)
+  os.rename(src, dst)
+
+def MoveDir(src, dst):
+  assert os.path.isdir(src)
+  Move(src, dst)
+
+def MoveFile(src, dst):
+  assert os.path.isfile(src)
+  Move(src, dst)
+
+def MoveProfileReportTo(dest_dir, build_stdout):
+  html_file = None
+  profile_message = 'See the profiling report at: '
+  for line in build_stdout:
+    if profile_message in line:
+      html_file = line[len(profile_message):]
+      if html_file.startswith('file://'):
+        html_file = html_file[len('file://'):]
+      break
+
+  if not html_file:
+    return
+
+  assert os.path.isfile(html_file), 'Expected to find HTML file at {}'.format(
+      html_file)
+  MoveFile(html_file, os.path.join(dest_dir, 'index.html'))
+
+  html_dir = os.path.dirname(html_file)
+  for dir_name in ['css', 'js']:
+    MoveDir(os.path.join(html_dir, dir_name), os.path.join(dest_dir, dir_name))
diff --git a/tools/internal_test.py b/tools/internal_test.py
index 4713daf..d34f74b 100755
--- a/tools/internal_test.py
+++ b/tools/internal_test.py
@@ -293,8 +293,7 @@
   git_hash = utils.get_HEAD_sha1()
   log('Running once with hash %s' % git_hash)
   # Run test.py internal testing.
-  # TODO(mkrogh) Change this to --r8lib when we have it working with dependencies relocated.
-  cmd = ['tools/test.py', '--only_internal', '--r8lib_no_deps']
+  cmd = ['tools/test.py', '--only_internal', '--r8lib']
   env = os.environ.copy()
   # Bot does not have a lot of memory.
   env['R8_GRADLE_CORES_PER_FORK'] = '8'
diff --git a/tools/run_on_as_app.py b/tools/run_on_as_app.py
index 244c093..eab815d 100755
--- a/tools/run_on_as_app.py
+++ b/tools/run_on_as_app.py
@@ -123,13 +123,6 @@
 def GitCheckout(file):
   return subprocess.check_output(['git', 'checkout', file]).strip()
 
-def MoveApkToDest(apk, apk_dest):
-  print('Moving `{}` to `{}`'.format(apk, apk_dest))
-  assert os.path.isfile(apk)
-  if os.path.isfile(apk_dest):
-    os.remove(apk_dest)
-  os.rename(apk, apk_dest)
-
 def InstallApkOnEmulator(apk_dest):
   subprocess.check_call(
       ['adb', '-s', emulator_id, 'install', '-r', '-d', apk_dest])
@@ -196,14 +189,17 @@
       apk_dest = None
       result = {}
       try:
-        apk_dest = BuildAppWithShrinker(
+        (apk_dest, profile_dest_dir) = BuildAppWithShrinker(
           app, config, shrinker, checkout_dir, options)
         dex_size = ComputeSizeOfDexFilesInApk(apk_dest)
         result['apk_dest'] = apk_dest,
         result['build_status'] = 'success'
         result['dex_size'] = dex_size
-      except:
+        result['profile_dest_dir'] = profile_dest_dir
+      except Exception as e:
         warn('Failed to build {} with {}'.format(app, shrinker))
+        if e:
+          print('Error: ' + str(e))
         result['build_status'] = 'failed'
 
       if options.monkey:
@@ -255,9 +251,20 @@
     releaseTarget = app_module + ':' + 'assemble' + (
         flavor.capitalize() if flavor else '') + 'Release'
 
-  cmd = ['./gradlew', '--no-daemon', 'clean', releaseTarget, '--stacktrace']
+  cmd = ['./gradlew', '--no-daemon', 'clean', releaseTarget, '--profile',
+      '--stacktrace']
+
   utils.PrintCmd(cmd)
-  subprocess.check_call(cmd, env=env)
+  build_process = subprocess.Popen(cmd, env=env, stdout=subprocess.PIPE)
+  stdout = []
+  while True:
+    line = build_process.stdout.readline()
+    if line != b'':
+      stripped = line.rstrip()
+      stdout.append(stripped)
+      print(stripped)
+    else:
+      break
 
   apk_base_name = (archives_base_name
       + (('-' + flavor) if flavor else '') + '-release')
@@ -288,15 +295,18 @@
 
   if os.path.isfile(signed_apk):
     apk_dest = os.path.join(out, signed_apk_name)
-    MoveApkToDest(signed_apk, apk_dest)
+    as_utils.MoveFile(signed_apk, apk_dest)
   else:
     apk_dest = os.path.join(out, unsigned_apk_name)
-    MoveApkToDest(unsigned_apk, apk_dest)
+    as_utils.MoveFile(unsigned_apk, apk_dest)
 
   assert IsBuiltWithR8(apk_dest) == ('r8' in shrinker), (
       'Unexpected marker in generated APK for {}'.format(shrinker))
 
-  return apk_dest
+  profile_dest_dir = os.path.join(out, 'profile')
+  as_utils.MoveProfileReportTo(profile_dest_dir, stdout)
+
+  return (apk_dest, profile_dest_dir)
 
 def RunMonkey(app, config, apk_dest):
   WaitForEmulator()
diff --git a/tools/test.py b/tools/test.py
index 6b24433..043487c 100755
--- a/tools/test.py
+++ b/tools/test.py
@@ -185,7 +185,6 @@
     gradle_args.append('-Pr8lib')
   if options.r8lib_no_deps:
     gradle_args.append('-Pr8lib_no_deps')
-    gradle_args.append('-Pexclude_deps')
 
   # Add Gradle tasks
   gradle_args.append('cleanTest')