diff --git a/build.gradle b/build.gradle
index 93d7e1b..7ff46eb 100644
--- a/build.gradle
+++ b/build.gradle
@@ -702,6 +702,11 @@
     workingDir = projectDir
 }
 
+task R8LibApiOnly {
+    dependsOn r8LibCreateTask("Api", "src/main/keep.txt", R8NoManifest, r8LibPath)
+    outputs.file r8LibPath
+}
+
 task R8LibNoDeps {
     dependsOn r8LibCreateTask(
             "NoDeps",
diff --git a/src/main/java/com/android/tools/r8/Version.java b/src/main/java/com/android/tools/r8/Version.java
index b500296..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.21-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/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..ba01321 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,7 @@
 
 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.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;
@@ -2100,9 +2101,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 +2153,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 +3178,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 +3486,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 +3520,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 +3585,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/src/test/java/com/android/tools/r8/shaking/assumevalues/SynthesizedRulesFromApiLevelTest.java b/src/test/java/com/android/tools/r8/shaking/assumevalues/SynthesizedRulesFromApiLevelTest.java
index 32ae37a..dd11dc1 100644
--- a/src/test/java/com/android/tools/r8/shaking/assumevalues/SynthesizedRulesFromApiLevelTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/assumevalues/SynthesizedRulesFromApiLevelTest.java
@@ -15,6 +15,8 @@
 import com.android.tools.r8.D8Command;
 import com.android.tools.r8.OutputMode;
 import com.android.tools.r8.TestBase;
+import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.ToolHelper.DexVm;
 import com.android.tools.r8.jasmin.JasminBuilder;
 import com.android.tools.r8.jasmin.JasminBuilder.ClassBuilder;
 import com.android.tools.r8.shaking.ProguardAssumeValuesRule;
@@ -27,6 +29,7 @@
 import java.nio.file.Path;
 import java.util.List;
 import java.util.function.Consumer;
+import org.junit.Assume;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.Parameterized;
@@ -230,6 +233,7 @@
 
   @Test
   public void testNoExplicitAssumeValuesRuleNative() throws Exception {
+    Assume.assumeTrue(ToolHelper.getDexVm().isNewerThan(DexVm.ART_7_0_0_HOST));
     runTest(
         AndroidApiLevel.O_MR1,
         AndroidApiLevel.O_MR1,
@@ -240,6 +244,7 @@
 
   @Test
   public void testNoExplicitAssumeValuesRuleCompatPresent() throws Exception {
+    Assume.assumeTrue(ToolHelper.getDexVm().isNewerThan(DexVm.ART_7_0_0_HOST));
     runTest(
         AndroidApiLevel.O,
         AndroidApiLevel.O_MR1,
@@ -250,6 +255,7 @@
 
   @Test
   public void testNoExplicitAssumeValuesRuleCompatUsed() throws Exception {
+    Assume.assumeTrue(ToolHelper.getDexVm().isNewerThan(DexVm.ART_7_0_0_HOST));
     runTest(
         AndroidApiLevel.O,
         AndroidApiLevel.O,
@@ -260,6 +266,7 @@
 
   @Test
   public void testExplicitAssumeValuesRuleWhichMatchAndDontKeepCompat() throws Exception {
+    Assume.assumeTrue(ToolHelper.getDexVm().isNewerThan(DexVm.ART_7_0_0_HOST));
     runTest(
         AndroidApiLevel.O_MR1,
         AndroidApiLevel.O_MR1,
@@ -274,6 +281,7 @@
 
   @Test
   public void testExplicitAssumeValuesRulesWhichMatchAndKeepCompat() throws Exception {
+    Assume.assumeTrue(ToolHelper.getDexVm().isNewerThan(DexVm.ART_7_0_0_HOST));
     String[] rules = new String[] {
         "-assumevalues class * { int SDK_INT return 1..1000; }",
         "-assumevalues class * { % SDK_INT return 1..1000; }",
@@ -297,6 +305,7 @@
 
   @Test
   public void testExplicitAssumeValuesRulesWhichDoesNotMatch() throws Exception {
+    Assume.assumeTrue(ToolHelper.getDexVm().isNewerThan(DexVm.ART_7_0_0_HOST));
     String[] rules = new String[] {
         "-assumevalues class * { !public int SDK_INT return 1..1000; }",
         "-assumevalues class * { !static int SDK_INT return 1..1000; }",
diff --git a/tools/golem_build.py b/tools/golem_build.py
index d55def1..30d46bc 100755
--- a/tools/golem_build.py
+++ b/tools/golem_build.py
@@ -8,8 +8,8 @@
 import gradle
 import sys
 
-GRADLE_ARGS = ['--no-daemon', '-Pno_internal']
-BUILD_TARGETS = ['R8', 'D8', 'R8Lib', 'buildExampleJars', 'CompatDx',
+GRADLE_ARGS = ['--no-daemon']
+BUILD_TARGETS = ['R8', 'D8', 'R8LibApiOnly', 'buildExampleJars', 'CompatDx',
                  'downloadAndroidCts', 'downloadDx']
 
 def Main():
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'