Replace nullable bit in TypeLatticeElement with NullLatticeElement.

Primitive types are always not null, so detaching it from type lattice.
Rather, we can move it down to ReferenceLatticeElement, which requires
another refactoring of canonicalization of reference types.
Instead of dual relations, we need three variants per type:
MAYBE_NULL, DEFINITELY_NOT_NULL, and DEFINITELY_NULL. In factory,
the MAYBE_NULL variant is registered, and then the other two variants
are linked on demand.

Bug: 72693244
Change-Id: I9d6d035f145506c8eea98f60c82b6805f695680d
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);