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 e920751..d4a2ef9 100644
--- a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
+++ b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
@@ -174,6 +174,7 @@
   public final DexType enumType = createType(enumDescriptor);
   public final DexType annotationType = createType(annotationDescriptor);
   public final DexType throwableType = createType(throwableDescriptor);
+  public final DexType classType = createType(classDescriptor);
 
   public final DexType stringBuilderType = createType(stringBuilderDescriptor);
   public final DexType stringBufferType = createType(stringBufferDescriptor);
diff --git a/src/main/java/com/android/tools/r8/graph/DexType.java b/src/main/java/com/android/tools/r8/graph/DexType.java
index a9689e5..9983f29 100644
--- a/src/main/java/com/android/tools/r8/graph/DexType.java
+++ b/src/main/java/com/android/tools/r8/graph/DexType.java
@@ -348,7 +348,7 @@
     }
   }
 
-  private int getNumberOfLeadingSquareBrackets() {
+  public int getNumberOfLeadingSquareBrackets() {
     int leadingSquareBrackets = 0;
     while (descriptor.content[leadingSquareBrackets] == '[') {
       leadingSquareBrackets++;
@@ -468,4 +468,51 @@
     assert hierarchyLevel != UNKNOWN_LEVEL;
     return type.directSubtypes.contains(this);
   }
+
+  public DexType computeLeastUpperBound(AppInfoWithSubtyping appInfo, DexType other) {
+    DexType objectType = appInfo.dexItemFactory.objectType;
+    // If either one is interface,
+    //   1) one of them is a super type of the other
+    //   2) otherwise, the object type is the least upper bound.
+    if (isInterface() || other.isInterface()) {
+      if (isSubtypeOf(other, appInfo)) {
+        return other;
+      }
+      if (other.isSubtypeOf(this, appInfo)) {
+        return this;
+      }
+      return objectType;
+    }
+    // To make the logic simple, change the role if the other is lower than this.
+    if (other.hierarchyLevel < this.hierarchyLevel) {
+      return other.computeLeastUpperBound(appInfo, this);
+    }
+    DexClass dexClass;
+    // Make both of other and this in the same level.
+    while (other.hierarchyLevel > this.hierarchyLevel) {
+      dexClass = appInfo.definitionFor(other);
+      if (dexClass == null) {
+        return objectType;
+      }
+      other = dexClass.superType;
+    }
+    // At this point, they are at the same level.
+    // lub starts from this, and will move up; other starts from itself, and will move up, too.
+    // They move up in their own hierarchy tree, and will repeat the process until they meet.
+    // (It will stop at anytime when either one's definition is not found.)
+    DexType lub = this;
+    while (other != lub) {
+      dexClass = appInfo.definitionFor(other);
+      if (dexClass == null) {
+        return objectType;
+      }
+      other = dexClass.superType;
+      dexClass = appInfo.definitionFor(lub);
+      if (dexClass == null) {
+        return objectType;
+      }
+      lub = dexClass.superType;
+    }
+    return lub;
+  }
 }
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
new file mode 100644
index 0000000..c388ec5
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/ArrayTypeLatticeElement.java
@@ -0,0 +1,65 @@
+// Copyright (c) 2017, 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.graph.AppInfoWithSubtyping;
+import com.android.tools.r8.graph.DexType;
+import com.google.common.base.Strings;
+
+public class ArrayTypeLatticeElement extends TypeLatticeElement {
+  final DexType elementType;
+  final int nesting;
+
+  ArrayTypeLatticeElement(DexType elementType, int nesting, boolean isNullable) {
+    super(isNullable);
+    this.elementType = elementType;
+    this.nesting = nesting;
+  }
+
+  @Override
+  TypeLatticeElement asNullable() {
+    return isNullable() ? this : new ArrayTypeLatticeElement(elementType, nesting, true);
+  }
+
+  @Override
+  public TypeLatticeElement arrayGet(AppInfoWithSubtyping appInfo) {
+    if (nesting == 1) {
+      return fromDexType(appInfo, elementType, true);
+    }
+    return new ArrayTypeLatticeElement(elementType, nesting - 1, true);
+  }
+
+  @Override
+  public TypeLatticeElement checkCast(AppInfoWithSubtyping appInfo, DexType castType) {
+    if (castType.getNumberOfLeadingSquareBrackets() == nesting) {
+      DexType base = castType.toBaseType(appInfo.dexItemFactory);
+      if (elementType.isSubtypeOf(base, appInfo)) {
+        return this;
+      }
+    }
+    return super.checkCast(appInfo, castType);
+  }
+
+  @Override
+  public String toString() {
+    return isNullableString() + elementType.toString() + Strings.repeat("[]", nesting);
+  }
+
+  @Override
+  public boolean equals(Object o) {
+    if (!super.equals(o)) {
+      return false;
+    }
+    ArrayTypeLatticeElement other = (ArrayTypeLatticeElement) o;
+    return nesting == other.nesting && elementType == other.elementType;
+  }
+
+  @Override
+  public int hashCode() {
+    int result = super.hashCode();
+    result = 31 * result + elementType.hashCode();
+    result = 31 * result + nesting;
+    return result;
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/Bottom.java b/src/main/java/com/android/tools/r8/ir/analysis/type/Bottom.java
new file mode 100644
index 0000000..3de4233
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/Bottom.java
@@ -0,0 +1,31 @@
+// Copyright (c) 2017, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.ir.analysis.type;
+
+public class Bottom extends TypeLatticeElement {
+  private static final Bottom INSTANCE = new Bottom();
+
+  private Bottom() {
+    super(true);
+  }
+
+  @Override
+  TypeLatticeElement asNullable() {
+    return this;
+  }
+
+  static Bottom getInstance() {
+    return INSTANCE;
+  }
+
+  @Override
+  boolean isBottom() {
+    return true;
+  }
+
+  @Override
+  public String toString() {
+    return "BOTTOM (empty)";
+  }
+}
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
new file mode 100644
index 0000000..2120669
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/ClassTypeLatticeElement.java
@@ -0,0 +1,56 @@
+// Copyright (c) 2017, 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.graph.AppInfoWithSubtyping;
+import com.android.tools.r8.graph.DexType;
+
+public class ClassTypeLatticeElement extends TypeLatticeElement {
+  final DexType classType;
+
+  ClassTypeLatticeElement(DexType classType, boolean isNullable) {
+    super(isNullable);
+    assert classType.isClassType();
+    this.classType = classType;
+  }
+
+  @Override
+  TypeLatticeElement asNullable() {
+    return isNullable() ? this : new ClassTypeLatticeElement(classType, true);
+  }
+
+  @Override
+  public TypeLatticeElement arrayGet(AppInfoWithSubtyping appInfo) {
+    return objectType(appInfo, true);
+  }
+
+  @Override
+  public TypeLatticeElement checkCast(AppInfoWithSubtyping appInfo, DexType castType) {
+    if (classType.isSubtypeOf(castType, appInfo)) {
+      return this;
+    }
+    return fromDexType(appInfo, castType, isNullable());
+  }
+
+  @Override
+  public String toString() {
+    return isNullableString() + classType.toString();
+  }
+
+  @Override
+  public boolean equals(Object o) {
+    if (!super.equals(o)) {
+      return false;
+    }
+    ClassTypeLatticeElement other = (ClassTypeLatticeElement) o;
+    return classType == other.classType;
+  }
+
+  @Override
+  public int hashCode() {
+    int result = super.hashCode();
+    result = 31 * result + classType.hashCode();
+    return result;
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/NullLatticeElement.java b/src/main/java/com/android/tools/r8/ir/analysis/type/NullLatticeElement.java
new file mode 100644
index 0000000..18ffad3
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/NullLatticeElement.java
@@ -0,0 +1,26 @@
+// Copyright (c) 2017, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.ir.analysis.type;
+
+public class NullLatticeElement extends TypeLatticeElement {
+  private static final NullLatticeElement INSTANCE = new NullLatticeElement();
+
+  private NullLatticeElement() {
+    super(true);
+  }
+
+  @Override
+  TypeLatticeElement asNullable() {
+    return this;
+  }
+
+  static NullLatticeElement getInstance() {
+    return INSTANCE;
+  }
+
+  @Override
+  public String toString() {
+    return "NULL";
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/PrimitiveArrayTypeLatticeElement.java b/src/main/java/com/android/tools/r8/ir/analysis/type/PrimitiveArrayTypeLatticeElement.java
new file mode 100644
index 0000000..d92e891
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/PrimitiveArrayTypeLatticeElement.java
@@ -0,0 +1,50 @@
+// Copyright (c) 2017, 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.graph.AppInfoWithSubtyping;
+import com.google.common.base.Strings;
+
+public class PrimitiveArrayTypeLatticeElement extends TypeLatticeElement {
+  final int nesting;
+
+  PrimitiveArrayTypeLatticeElement(int nesting, boolean isNullable) {
+    super(isNullable);
+    this.nesting = nesting;
+  }
+
+  @Override
+  TypeLatticeElement asNullable() {
+    return isNullable() ? this : new PrimitiveArrayTypeLatticeElement(nesting, true);
+  }
+
+  @Override
+  public TypeLatticeElement arrayGet(AppInfoWithSubtyping appInfo) {
+    if (nesting == 1) {
+      return PrimitiveTypeLatticeElement.getInstance();
+    }
+    return new PrimitiveArrayTypeLatticeElement(nesting - 1, true);
+  }
+
+  @Override
+  public String toString() {
+    return isNullableString() + "PRIMITIVE" + Strings.repeat("[]", nesting);
+  }
+
+  @Override
+  public boolean equals(Object o) {
+    if (!super.equals(o)) {
+      return false;
+    }
+    PrimitiveArrayTypeLatticeElement other = (PrimitiveArrayTypeLatticeElement) o;
+    return nesting == other.nesting;
+  }
+
+  @Override
+  public int hashCode() {
+    int result = super.hashCode();
+    result = 31 * result + nesting;
+    return result;
+  }
+}
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
new file mode 100644
index 0000000..ea06862
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/PrimitiveTypeLatticeElement.java
@@ -0,0 +1,31 @@
+// Copyright (c) 2017, 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;
+
+/**
+ * A {@link TypeLatticeElement} that represents all primitive types, such as int, long, etc.
+ * All primitives are aggregated, since the main use of this type analysis is to help
+ * better understanding of the type of object references.
+ */
+public class PrimitiveTypeLatticeElement extends TypeLatticeElement {
+  private static final PrimitiveTypeLatticeElement INSTANCE = new PrimitiveTypeLatticeElement();
+
+  private PrimitiveTypeLatticeElement() {
+    super(false);
+  }
+
+  @Override
+  TypeLatticeElement asNullable() {
+    return Top.getInstance();
+  }
+
+  public static PrimitiveTypeLatticeElement getInstance() {
+    return INSTANCE;
+  }
+
+  @Override
+  public String toString() {
+    return "PRIMITIVE";
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/Top.java b/src/main/java/com/android/tools/r8/ir/analysis/type/Top.java
new file mode 100644
index 0000000..6b4745d
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/Top.java
@@ -0,0 +1,31 @@
+// Copyright (c) 2017, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.ir.analysis.type;
+
+public class Top extends TypeLatticeElement {
+  private static final Top INSTANCE = new Top();
+
+  private Top() {
+    super(true);
+  }
+
+  @Override
+  TypeLatticeElement asNullable() {
+    return this;
+  }
+
+  static Top getInstance() {
+    return INSTANCE;
+  }
+
+  @Override
+  boolean isTop() {
+    return true;
+  }
+
+  @Override
+  public String toString() {
+    return "TOP (everything)";
+  }
+}
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
new file mode 100644
index 0000000..91d53a2
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/TypeAnalysis.java
@@ -0,0 +1,138 @@
+// Copyright (c) 2017, 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.graph.AppInfoWithSubtyping;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.code.Argument;
+import com.android.tools.r8.ir.code.BasicBlock;
+import com.android.tools.r8.ir.code.IRCode;
+import com.android.tools.r8.ir.code.Instruction;
+import com.android.tools.r8.ir.code.Phi;
+import com.android.tools.r8.ir.code.Value;
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.collect.Maps;
+import com.google.common.collect.Sets;
+
+import java.util.ArrayDeque;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.Deque;
+import java.util.Map;
+import java.util.Set;
+import java.util.function.BiConsumer;
+import java.util.function.BiFunction;
+
+public class TypeAnalysis {
+  private final AppInfoWithSubtyping appInfo;
+  private final DexEncodedMethod encodedMethod;
+  private final IRCode code;
+
+  private final Deque<BasicBlock> worklist = new ArrayDeque<>();
+  private final Map<Value, TypeLatticeElement> typeMap = Maps.newHashMap();
+  private final Map<Value, Set<BasicBlock>> users = Maps.newHashMap();
+
+  public TypeAnalysis(AppInfoWithSubtyping appInfo, DexEncodedMethod encodedMethod, IRCode code) {
+    this.appInfo = appInfo;
+    this.encodedMethod = encodedMethod;
+    this.code = code;
+  }
+
+  public void run() {
+    BasicBlock[] basicBlocks = code.topologicallySortedBlocks();
+    if (basicBlocks.length <= 0) {
+      return;
+    }
+    worklist.addAll(Arrays.asList(basicBlocks));
+    while (!worklist.isEmpty()) {
+      processBasicBlock(worklist.poll());
+    }
+  }
+
+  private void addToWorklist(BasicBlock block) {
+    if (!worklist.contains(block)) {
+      worklist.add(block);
+    }
+  }
+
+  private void processBasicBlock(BasicBlock block) {
+    int argumentsSeen = encodedMethod.accessFlags.isStatic() ? 0 : -1;
+    for (Instruction instruction : block.getInstructions()) {
+      TypeLatticeElement derived = Bottom.getInstance();
+      Value outValue = instruction.outValue();
+      // Argument, a quasi instruction, needs to be handled specially:
+      //   1) We can derive its type from the method signature; and
+      //   2) It does not have an out value, so we can skip the env updating.
+      if (instruction instanceof Argument) {
+        if (argumentsSeen < 0) {
+          derived = TypeLatticeElement.fromDexType(appInfo, encodedMethod.method.holder, false);
+        } else {
+          DexType argType = encodedMethod.method.proto.parameters.values[argumentsSeen];
+          derived = TypeLatticeElement.fromDexType(appInfo, argType, true);
+        }
+        argumentsSeen++;
+      } else {
+        // Register this block as a user for in values to revisit this if in values are updated.
+        instruction.inValues()
+            .forEach(v -> registerAsUserOfValue(v, block, Sets.newIdentityHashSet()));
+        if (outValue != null) {
+          derived = instruction.evaluate(appInfo, this::getLatticeElement);
+        }
+      }
+      if (outValue != null) {
+        TypeLatticeElement current = getLatticeElement(outValue);
+        if (!current.equals(derived)) {
+          updateTypeOfValue(outValue, derived);
+        }
+      }
+    }
+  }
+
+  private void registerAsUserOfValue(Value value, BasicBlock block, Set<Value> seenPhis) {
+    if (value.isPhi() && seenPhis.add(value)) {
+      for (Value operand : value.asPhi().getOperands()) {
+        registerAsUserOfValue(operand, block, seenPhis);
+      }
+    } else {
+      users.computeIfAbsent(value, k -> Sets.newIdentityHashSet()).add(block);
+    }
+  }
+
+  private void updateTypeOfValue(Value value, TypeLatticeElement type) {
+    setLatticeElement(value, type);
+    // Revisit the blocks that use the value whose type binding has just been updated.
+    users.getOrDefault(value, Collections.emptySet()).forEach(this::addToWorklist);
+    // Propagate the type change to phi users if any.
+    for (Phi phi : value.uniquePhiUsers()) {
+      TypeLatticeElement phiType = computePhiType(phi);
+      if (!getLatticeElement(phi).equals(phiType)) {
+        updateTypeOfValue(phi, phiType);
+      }
+    }
+  }
+
+  private TypeLatticeElement computePhiType(Phi phi) {
+    // Type of phi(v1, v2, ..., vn) is the least upper bound of all those n operands.
+    BiFunction<TypeLatticeElement, TypeLatticeElement, TypeLatticeElement> joiner =
+        TypeLatticeElement.joiner(appInfo);
+    return phi.getOperands().stream().reduce(
+        Bottom.getInstance(),
+        (acc, value) -> joiner.apply(acc, getLatticeElement(value)),
+        joiner::apply);
+  }
+
+  private void setLatticeElement(Value value, TypeLatticeElement type) {
+    typeMap.put(value, type);
+  }
+
+  TypeLatticeElement getLatticeElement(Value value) {
+    return typeMap.getOrDefault(value, Bottom.getInstance());
+  }
+
+  @VisibleForTesting
+  void forEach(BiConsumer<Value, TypeLatticeElement> consumer) {
+    typeMap.forEach(consumer);
+  }
+}
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
new file mode 100644
index 0000000..3d5738f
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/TypeLatticeElement.java
@@ -0,0 +1,214 @@
+// Copyright (c) 2017, 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;
+import com.android.tools.r8.graph.AppInfo;
+import com.android.tools.r8.graph.AppInfoWithSubtyping;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.code.Value;
+import java.util.function.BiFunction;
+
+/**
+ * The base abstraction of lattice elements for local type analysis.
+ */
+abstract public class TypeLatticeElement {
+  private final boolean isNullable;
+
+  TypeLatticeElement(boolean isNullable) {
+    this.isNullable = isNullable;
+  }
+
+  boolean isNullable() {
+    return isNullable;
+  }
+
+  /**
+   * Defines how to join with null.
+   *
+   * @return {@link TypeLatticeElement} a result of joining with null.
+   */
+  abstract TypeLatticeElement asNullable();
+
+  String isNullableString() {
+    return isNullable() ? "" : "@NonNull ";
+  }
+
+  /**
+   * Computes the least upper bound of the current and the other elements.
+   *
+   * @param appInfo {@link AppInfoWithSubtyping} that contains subtype info.
+   * @param l1 {@link TypeLatticeElement} to join.
+   * @param l2 {@link TypeLatticeElement} to join.
+   * @return {@link TypeLatticeElement}, a least upper bound of {@param l1} and {@param l2}.
+   */
+  static TypeLatticeElement join(
+      AppInfoWithSubtyping appInfo, TypeLatticeElement l1, TypeLatticeElement l2) {
+    if (l1.isBottom()) {
+      return l2;
+    }
+    if (l2.isBottom()) {
+      return l1;
+    }
+    if (l1.isTop() || l2.isTop()) {
+      return Top.getInstance();
+    }
+    if (l1 instanceof NullLatticeElement) {
+      return l2.asNullable();
+    }
+    if (l2 instanceof NullLatticeElement) {
+      return l1.asNullable();
+    }
+    if (l1 instanceof PrimitiveTypeLatticeElement) {
+      return l2 instanceof PrimitiveTypeLatticeElement ? l1 : Top.getInstance();
+    }
+    if (l2 instanceof PrimitiveTypeLatticeElement) {
+      // !(l1 instanceof PrimitiveTypeLatticeElement)
+      return Top.getInstance();
+    }
+    // From now on, l1 and l2 are either PrimitiveArrayType, ArrayType, or ClassType.
+    boolean isNullable = l1.isNullable() || l2.isNullable();
+    if (l1.getClass() != l2.getClass()) {
+      return objectType(appInfo, isNullable);
+    }
+    // From now on, l1.getClass() == l2.getClass()
+    if (l1 instanceof PrimitiveArrayTypeLatticeElement) {
+      PrimitiveArrayTypeLatticeElement a1 = (PrimitiveArrayTypeLatticeElement) l1;
+      PrimitiveArrayTypeLatticeElement a2 = (PrimitiveArrayTypeLatticeElement) l2;
+      if (a1.nesting != a2.nesting) {
+        int min = Math.min(a1.nesting, a2.nesting);
+        if (min > 1) {
+          return objectArrayType(appInfo, min - 1, isNullable);
+        } else {
+          return objectType(appInfo, isNullable);
+        }
+      } else {
+        return l1;
+      }
+    }
+    if (l1 instanceof ArrayTypeLatticeElement) {
+      ArrayTypeLatticeElement a1 = (ArrayTypeLatticeElement) l1;
+      ArrayTypeLatticeElement a2 = (ArrayTypeLatticeElement) l2;
+      if (a1.nesting != a2.nesting) {
+        int min = Math.min(a1.nesting, a2.nesting);
+        return objectArrayType(appInfo, min, isNullable);
+      } else {
+        // Same nesting, same base type.
+        if (a1.elementType == a2.elementType) {
+          return a1.isNullable() ? a1 : a2;
+        } else if (a1.elementType.isClassType() && a2.elementType.isClassType()) {
+          // For different class element types, compute the least upper bound of element types.
+          DexType lub = a1.elementType.computeLeastUpperBound(appInfo, a2.elementType);
+          return new ArrayTypeLatticeElement(lub, a1.nesting, isNullable);
+        }
+        // Otherwise, fall through to the end, where TOP will be returned.
+      }
+    }
+    if (l1 instanceof ClassTypeLatticeElement) {
+      ClassTypeLatticeElement c1 = (ClassTypeLatticeElement) l1;
+      ClassTypeLatticeElement c2 = (ClassTypeLatticeElement) l2;
+      if (c1.classType == c2.classType) {
+        return c1.isNullable() ? c1 : c2;
+      } else {
+        DexType lub = c1.classType.computeLeastUpperBound(appInfo, c2.classType);
+        return new ClassTypeLatticeElement(lub, isNullable);
+      }
+    }
+    throw new Unreachable("unless a new type lattice is introduced.");
+  }
+
+  static BiFunction<TypeLatticeElement, TypeLatticeElement, TypeLatticeElement> joiner(
+      AppInfoWithSubtyping appInfo) {
+    return (l1, l2) -> join(appInfo, l1, l2);
+  }
+
+  /**
+   * Represents a type that can be everything.
+   *
+   * @return true if the corresponding {@link Value} could be any kinds.
+   */
+  boolean isTop() {
+    return false;
+  }
+
+  /**
+   * Represents an empty type.
+   *
+   * @return true if the type of corresponding {@link Value} is not determined yet.
+   */
+  boolean isBottom() {
+    return false;
+  }
+
+  static ClassTypeLatticeElement objectType(AppInfo appInfo, boolean isNullable) {
+    return new ClassTypeLatticeElement(appInfo.dexItemFactory.objectType, isNullable);
+  }
+
+  static ArrayTypeLatticeElement objectArrayType(AppInfo appInfo, int nesting, boolean isNullable) {
+    return new ArrayTypeLatticeElement(appInfo.dexItemFactory.objectType, nesting, isNullable);
+  }
+
+  public static TypeLatticeElement fromDexType(
+      AppInfoWithSubtyping appInfo, DexType type, boolean isNullable) {
+    if (type.isPrimitiveType()) {
+      return PrimitiveTypeLatticeElement.getInstance();
+    }
+    if (type.isPrimitiveArrayType()) {
+      return new PrimitiveArrayTypeLatticeElement(
+          type.getNumberOfLeadingSquareBrackets(), isNullable);
+    }
+    if (type.isClassType()) {
+      return new ClassTypeLatticeElement(type, isNullable);
+    }
+    assert type.isArrayType();
+    return new ArrayTypeLatticeElement(
+        type.toBaseType(appInfo.dexItemFactory),
+        type.getNumberOfLeadingSquareBrackets(),
+        isNullable);
+  }
+
+  public static TypeLatticeElement newArray(
+      AppInfoWithSubtyping appInfo, DexType arrayType, boolean isNullable) {
+    DexType baseType = arrayType.toBaseType(appInfo.dexItemFactory);
+    assert baseType != arrayType;
+    int nesting = arrayType.getNumberOfLeadingSquareBrackets();
+    if (baseType.isClassType()) {
+      return new ArrayTypeLatticeElement(baseType, nesting, isNullable);
+    } else {
+      return newPrimitiveArray(nesting, isNullable);
+    }
+  }
+
+  public static TypeLatticeElement newPrimitiveArray(int nesting, boolean isNullable) {
+    return new PrimitiveArrayTypeLatticeElement(nesting, isNullable);
+  }
+
+  public TypeLatticeElement arrayGet(AppInfoWithSubtyping appInfo) {
+    return Top.getInstance();
+  }
+
+  public TypeLatticeElement checkCast(AppInfoWithSubtyping appInfo, DexType castType) {
+    return fromDexType(appInfo, castType, isNullable());
+  }
+
+  @Override
+  abstract public String toString();
+
+  @Override
+  public boolean equals(Object o) {
+    if (this == o) {
+      return true;
+    }
+    if (o == null || o.getClass() != this.getClass()) {
+      return false;
+    }
+    TypeLatticeElement otherElement = (TypeLatticeElement) o;
+    return otherElement.isNullable() == isNullable;
+  }
+
+  @Override
+  public int hashCode() {
+    return isNullable ? 1 : 0;
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/code/ArrayGet.java b/src/main/java/com/android/tools/r8/ir/code/ArrayGet.java
index b226b70..2380ea2 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ArrayGet.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ArrayGet.java
@@ -16,11 +16,13 @@
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.Constraint;
 import com.android.tools.r8.ir.regalloc.RegisterAllocator;
 import java.util.Arrays;
+import java.util.function.Function;
 
 public class ArrayGet extends Instruction {
 
@@ -142,4 +144,10 @@
   public void buildCf(CfBuilder builder) {
     builder.add(new CfArrayLoad(type));
   }
+
+  @Override
+  public TypeLatticeElement evaluate(
+      AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+    return getLatticeElement.apply(array()).arrayGet(appInfo);
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/ArrayLength.java b/src/main/java/com/android/tools/r8/ir/code/ArrayLength.java
index 742ccb5..f7689ab 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ArrayLength.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ArrayLength.java
@@ -9,10 +9,13 @@
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.PrimitiveTypeLatticeElement;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.Constraint;
 import com.android.tools.r8.ir.regalloc.RegisterAllocator;
+import java.util.function.Function;
 
 public class ArrayLength extends Instruction {
 
@@ -101,4 +104,10 @@
   public void buildCf(CfBuilder builder) {
     builder.add(new CfArrayLength());
   }
+
+  @Override
+  public TypeLatticeElement evaluate(
+      AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+    return PrimitiveTypeLatticeElement.getInstance();
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Binop.java b/src/main/java/com/android/tools/r8/ir/code/Binop.java
index 8473f71..55b3ba5 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Binop.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Binop.java
@@ -11,9 +11,12 @@
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.PrimitiveTypeLatticeElement;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.Constraint;
 import com.android.tools.r8.ir.regalloc.RegisterAllocator;
+import java.util.function.Function;
 
 public abstract class Binop extends Instruction {
 
@@ -132,4 +135,10 @@
   public void buildCf(CfBuilder builder) {
     builder.add(new CfBinop(getCfOpcode()));
   }
+
+  @Override
+  public TypeLatticeElement evaluate(
+      AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+    return PrimitiveTypeLatticeElement.getInstance();
+  }
 }
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 90723b2..f0e4d44 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
@@ -9,8 +9,10 @@
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.Constraint;
+import java.util.function.Function;
 
 public class CheckCast extends Instruction {
 
@@ -101,4 +103,10 @@
   public Constraint inliningConstraint(AppInfoWithSubtyping info, DexType invocationContext) {
     return Constraint.classIsVisible(invocationContext, type, info);
   }
+
+  @Override
+  public TypeLatticeElement evaluate(
+      AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+    return getLatticeElement.apply(object()).checkCast(appInfo, type);
+  }
 }
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 bab1c2f..16239e2 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
@@ -7,9 +7,11 @@
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.Constraint;
 import com.android.tools.r8.utils.InternalOptions;
+import java.util.function.Function;
 
 public class ConstClass extends ConstInstruction {
 
@@ -94,4 +96,10 @@
   public Constraint inliningConstraint(AppInfoWithSubtyping info, DexType invocationContext) {
     return Constraint.classIsVisible(invocationContext, clazz, info);
   }
+
+  @Override
+  public TypeLatticeElement evaluate(
+      AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+    return TypeLatticeElement.fromDexType(appInfo, appInfo.dexItemFactory.classType, false);
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/ConstNumber.java b/src/main/java/com/android/tools/r8/ir/code/ConstNumber.java
index f990d90..1c6161b 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ConstNumber.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ConstNumber.java
@@ -16,10 +16,13 @@
 import com.android.tools.r8.code.ConstWide32;
 import com.android.tools.r8.code.ConstWideHigh16;
 import com.android.tools.r8.dex.Constants;
+import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.ir.analysis.constant.Bottom;
 import com.android.tools.r8.ir.analysis.constant.ConstLatticeElement;
 import com.android.tools.r8.ir.analysis.constant.LatticeElement;
+import com.android.tools.r8.ir.analysis.type.PrimitiveTypeLatticeElement;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.utils.NumberUtils;
@@ -263,4 +266,10 @@
     }
     return new ConstLatticeElement(this);
   }
+
+  @Override
+  public TypeLatticeElement evaluate(
+      AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+    return PrimitiveTypeLatticeElement.getInstance();
+  }
 }
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 a3a730d..9ff7fe4 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
@@ -7,12 +7,15 @@
 import com.android.tools.r8.cf.TypeVerificationHelper;
 import com.android.tools.r8.cf.code.CfConstString;
 import com.android.tools.r8.dex.Constants;
+import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.DexString;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.utils.InternalOptions;
 import java.io.UTFDataFormatException;
+import java.util.function.Function;
 
 public class ConstString extends ConstInstruction {
 
@@ -120,4 +123,10 @@
   public DexType computeVerificationType(TypeVerificationHelper helper) {
     return helper.getFactory().stringType;
   }
+
+  @Override
+  public TypeLatticeElement evaluate(
+      AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+    return TypeLatticeElement.fromDexType(appInfo, appInfo.dexItemFactory.stringType, false);
+  }
 }
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 e1bc063..ddf2969 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
@@ -14,10 +14,13 @@
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.AppInfo;
+import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.DexEncodedField;
 import com.android.tools.r8.graph.DexField;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.conversion.DexBuilder;
+import java.util.function.Function;
 
 public class InstanceGet extends FieldInstruction {
 
@@ -121,4 +124,10 @@
   public String toString() {
     return super.toString() + "; field: " + field.toSourceString();
   }
+
+  @Override
+  public TypeLatticeElement evaluate(
+      AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+    return TypeLatticeElement.fromDexType(appInfo, field.type, true);
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/InstanceOf.java b/src/main/java/com/android/tools/r8/ir/code/InstanceOf.java
index 995a35e..0985ad1 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InstanceOf.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InstanceOf.java
@@ -7,8 +7,11 @@
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.PrimitiveTypeLatticeElement;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.Constraint;
+import java.util.function.Function;
 
 public class InstanceOf extends Instruction {
 
@@ -77,4 +80,10 @@
   public Constraint inliningConstraint(AppInfoWithSubtyping info, DexType invocationContext) {
     return Constraint.classIsVisible(invocationContext, type, info);
   }
+
+  @Override
+  public TypeLatticeElement evaluate(
+      AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+    return PrimitiveTypeLatticeElement.getInstance();
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Instruction.java b/src/main/java/com/android/tools/r8/ir/code/Instruction.java
index 70ffe8a..cf5190a 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Instruction.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Instruction.java
@@ -13,6 +13,7 @@
 import com.android.tools.r8.ir.analysis.constant.Bottom;
 import com.android.tools.r8.ir.analysis.constant.ConstRangeLatticeElement;
 import com.android.tools.r8.ir.analysis.constant.LatticeElement;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.Constraint;
@@ -1018,4 +1019,10 @@
     }
     return Bottom.getInstance();
   }
+
+  public TypeLatticeElement evaluate(
+      AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+    assert outValue == null;
+    throw new Unreachable("Instructions without outValue have no type.");
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java b/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java
index 9e1494e..17b7b64 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java
@@ -5,16 +5,19 @@
 
 import com.android.tools.r8.cf.LoadStoreHelper;
 import com.android.tools.r8.cf.TypeVerificationHelper;
+import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.optimize.Inliner.Constraint;
 import com.android.tools.r8.ir.optimize.Inliner.InlineAction;
 import com.android.tools.r8.ir.optimize.InliningOracle;
 import java.util.Collection;
 import java.util.List;
+import java.util.function.Function;
 
 public abstract class InvokeMethod extends Invoke {
 
@@ -144,4 +147,14 @@
   public DexType computeVerificationType(TypeVerificationHelper helper) {
     return getInvokedMethod().proto.returnType;
   }
+
+  @Override
+  public TypeLatticeElement evaluate(
+      AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+    DexType returnType = method.proto.returnType;
+    if (returnType.isVoidType()) {
+      throw new Unreachable("void methods have no type.");
+    }
+    return TypeLatticeElement.fromDexType(appInfo, returnType, true);
+  }
 }
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 440574a..f075633 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
@@ -8,9 +8,11 @@
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.Constraint;
 import java.util.List;
+import java.util.function.Function;
 
 public class InvokeNewArray extends Invoke {
 
@@ -104,4 +106,10 @@
   public Constraint inliningConstraint(AppInfoWithSubtyping info, DexType invocationContext) {
     return Constraint.classIsVisible(invocationContext, type, info);
   }
+
+  @Override
+  public TypeLatticeElement evaluate(
+      AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+    return TypeLatticeElement.newArray(appInfo, type, false);
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Move.java b/src/main/java/com/android/tools/r8/ir/code/Move.java
index 9d27eab..4187cab 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Move.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Move.java
@@ -7,8 +7,10 @@
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.Constraint;
+import java.util.function.Function;
 
 public class Move extends Instruction {
 
@@ -84,4 +86,10 @@
   public Constraint inliningConstraint(AppInfoWithSubtyping info, DexType invocationContext) {
     return Constraint.ALWAYS;
   }
+
+  @Override
+  public TypeLatticeElement evaluate(
+      AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+    return getLatticeElement.apply(src());
+  }
 }
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 8bfdcd2..dda7a30 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.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.Constraint;
@@ -15,6 +16,7 @@
 import java.util.HashSet;
 import java.util.List;
 import java.util.Set;
+import java.util.function.Function;
 
 public class MoveException extends Instruction {
 
@@ -105,4 +107,10 @@
     }
     return helper.join(exceptionTypes);
   }
+
+  @Override
+  public TypeLatticeElement evaluate(
+      AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+    return TypeLatticeElement.fromDexType(appInfo, appInfo.dexItemFactory.throwableType, false);
+  }
 }
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 8d32ca9..2c15de7 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,9 +10,11 @@
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.Constraint;
+import java.util.function.Function;
 
 public class NewArrayEmpty extends Instruction {
 
@@ -101,4 +103,10 @@
     assert type.isArrayType();
     builder.add(new CfNewArray(type));
   }
+
+  @Override
+  public TypeLatticeElement evaluate(
+      AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+    return TypeLatticeElement.newArray(appInfo, type, false);
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/NewArrayFilledData.java b/src/main/java/com/android/tools/r8/ir/code/NewArrayFilledData.java
index 765251f..4b53afb 100644
--- a/src/main/java/com/android/tools/r8/ir/code/NewArrayFilledData.java
+++ b/src/main/java/com/android/tools/r8/ir/code/NewArrayFilledData.java
@@ -8,10 +8,12 @@
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.Constraint;
 import com.android.tools.r8.utils.InternalOptions;
 import java.util.Arrays;
+import java.util.function.Function;
 
 public class NewArrayFilledData extends Instruction {
 
@@ -102,4 +104,10 @@
   public Constraint inliningConstraint(AppInfoWithSubtyping info, DexType invocationContext) {
     return Constraint.ALWAYS;
   }
+
+  @Override
+  public TypeLatticeElement evaluate(
+      AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+    return TypeLatticeElement.newPrimitiveArray(1, false);
+  }
 }
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 b00eef0..6b45990 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,9 +9,11 @@
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.Constraint;
+import java.util.function.Function;
 
 public class NewInstance extends Instruction {
 
@@ -95,4 +97,10 @@
   public DexType computeVerificationType(TypeVerificationHelper helper) {
     return clazz;
   }
+
+  @Override
+  public TypeLatticeElement evaluate(
+      AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+    return TypeLatticeElement.fromDexType(appInfo, clazz, false);
+  }
 }
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 32871b3..acb8977 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
@@ -16,11 +16,14 @@
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.AppInfo;
+import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.DexEncodedField;
 import com.android.tools.r8.graph.DexField;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.DexBuilder;
+import java.util.function.Function;
 
 public class StaticGet extends FieldInstruction {
 
@@ -135,4 +138,10 @@
   public DexType computeVerificationType(TypeVerificationHelper helper) {
     return field.type;
   }
+
+  @Override
+  public TypeLatticeElement evaluate(
+      AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+    return TypeLatticeElement.fromDexType(appInfo, field.type, true);
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Unop.java b/src/main/java/com/android/tools/r8/ir/code/Unop.java
index f161635..f1189b9 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Unop.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Unop.java
@@ -8,8 +8,11 @@
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.PrimitiveTypeLatticeElement;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.Constraint;
+import java.util.function.Function;
 
 abstract public class Unop extends Instruction {
 
@@ -62,4 +65,10 @@
   public void buildCf(CfBuilder builder) {
     builder.add(new CfUnop(getCfOpcode()));
   }
+
+  @Override
+  public TypeLatticeElement evaluate(
+      AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+    return PrimitiveTypeLatticeElement.getInstance();
+  }
 }
diff --git a/src/test/java/com/android/tools/r8/ToolHelper.java b/src/test/java/com/android/tools/r8/ToolHelper.java
index a6ab7e9..cf5e451 100644
--- a/src/test/java/com/android/tools/r8/ToolHelper.java
+++ b/src/test/java/com/android/tools/r8/ToolHelper.java
@@ -72,6 +72,7 @@
   public static final String EXAMPLES_ANDROID_O_BUILD_DIR = TESTS_BUILD_DIR + "examplesAndroidO/";
   public static final String EXAMPLES_ANDROID_P_BUILD_DIR = TESTS_BUILD_DIR + "examplesAndroidP/";
   public static final String EXAMPLES_JAVA9_BUILD_DIR = TESTS_BUILD_DIR + "examplesJava9/";
+  public static final String SMALI_DIR = TESTS_DIR + "smali/";
   public static final String SMALI_BUILD_DIR = TESTS_BUILD_DIR + "smali/";
 
   public static final String LINE_SEPARATOR = StringUtils.LINE_SEPARATOR;
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
new file mode 100644
index 0000000..da8772f
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/analysis/type/NullabilityTest.java
@@ -0,0 +1,257 @@
+// Copyright (c) 2017, 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 static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+import com.android.tools.r8.dex.ApplicationReader;
+import com.android.tools.r8.graph.AppInfoWithSubtyping;
+import com.android.tools.r8.graph.DexApplication;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.code.IRCode;
+import com.android.tools.r8.smali.SmaliBuilder;
+import com.android.tools.r8.smali.SmaliBuilder.MethodSignature;
+import com.android.tools.r8.smali.SmaliTestBase;
+import com.android.tools.r8.utils.AndroidApp;
+import com.android.tools.r8.utils.DexInspector;
+import com.android.tools.r8.utils.InternalOptions;
+import com.android.tools.r8.utils.Timing;
+import com.google.common.collect.ImmutableList;
+import java.util.function.BiConsumer;
+import org.junit.Test;
+
+public class NullabilityTest extends SmaliTestBase {
+  private final String CLASS_NAME = "Example";
+  private static final InternalOptions TEST_OPTIONS = new InternalOptions();
+
+  private void buildAndTest(
+      SmaliBuilder builder,
+      MethodSignature signature,
+      BiConsumer<AppInfoWithSubtyping, TypeAnalysis> inspector)
+      throws Exception {
+    AndroidApp app = builder.build();
+    DexApplication dexApplication =
+        new ApplicationReader(app, TEST_OPTIONS, new Timing("NullabilityTest.appReader"))
+            .read().toDirect();
+    AppInfoWithSubtyping appInfo = new AppInfoWithSubtyping(dexApplication);
+    DexInspector dexInspector = new DexInspector(appInfo.app);
+    DexEncodedMethod foo = dexInspector.clazz(CLASS_NAME).method(signature).getMethod();
+    IRCode irCode = foo.buildIR(TEST_OPTIONS);
+    TypeAnalysis analysis = new TypeAnalysis(appInfo, foo, irCode);
+    analysis.run();
+    inspector.accept(appInfo, analysis);
+  }
+
+  @Test
+  public void nonNullAfterSafeInvokes() throws Exception {
+    SmaliBuilder builder = new SmaliBuilder(CLASS_NAME);
+    MethodSignature signature =
+        builder.addInstanceMethod("void", "foo", ImmutableList.of("java.lang.String"), 1,
+            "invoke-virtual {p1}, Ljava/lang/String;->toString()Ljava/lang/String;",
+            // Successful invocation above means p1 is not null.
+            "if-nez p1, :not_null",
+            "new-instance v0, Ljava/lang/AssertionError;",
+            "throw v0",
+            ":not_null",
+            "return-void"
+    );
+    buildAndTest(builder, signature, (appInfo, typeAnalysis) -> {
+      typeAnalysis.forEach((v, l) -> {
+        assertTrue(l instanceof ClassTypeLatticeElement);
+        ClassTypeLatticeElement lattice = (ClassTypeLatticeElement) l;
+        if (lattice.classType.equals(appInfo.dexItemFactory.stringType)) {
+          // TODO(b/70795205): Can be refined by using control-flow info.
+          // parameter
+          assertTrue(lattice.isNullable());
+        } else {
+          // holder and newly created assertion error.
+          assertFalse(lattice.isNullable());
+        }
+      });
+    });
+  }
+
+  @Test
+  public void stillNullAfterExceptionCatch_invoke() throws Exception {
+    SmaliBuilder builder = new SmaliBuilder(CLASS_NAME);
+    MethodSignature signature =
+        builder.addInstanceMethod("void", "foo", ImmutableList.of("java.lang.String"), 1,
+            ":try_start",
+            "invoke-virtual {p1}, Ljava/lang/String;->toString()Ljava/lang/String;",
+            "if-nez p1, :return",
+            "new-instance v0, Ljava/lang/AssertionError;",
+            "throw v0",
+            ":try_end",
+            ".catch Ljava/lang/Throwable; {:try_start .. :try_end} :return",
+            ":return",
+            // p1 could be still null at the outside of try-catch.
+            "invoke-virtual {p1}, Ljava/lang/String;->hashCode()I",
+            "return-void"
+    );
+    buildAndTest(builder, signature, (appInfo, typeAnalysis) -> {
+      typeAnalysis.forEach((v, l) -> {
+        assertTrue(l instanceof ClassTypeLatticeElement);
+        ClassTypeLatticeElement lattice = (ClassTypeLatticeElement) l;
+        if (lattice.classType.equals(appInfo.dexItemFactory.stringType)) {
+          // parameter
+          assertTrue(lattice.isNullable());
+        } else {
+          // holder and newly created assertion error.
+          assertFalse(lattice.isNullable());
+        }
+      });
+    });
+  }
+
+  @Test
+  public void nonNullAfterSafeArrayAccess() throws Exception {
+    SmaliBuilder builder = new SmaliBuilder(CLASS_NAME);
+    MethodSignature signature =
+        builder.addInstanceMethod("void", "foo", ImmutableList.of("java.lang.String[]"), 1,
+            "const/4 v0, 0",
+            "aget-object v0, p1, v0",
+            // Successful array access above means p1 is not null.
+            "if-nez p1, :not_null",
+            "new-instance v0, Ljava/lang/AssertionError;",
+            "throw v0",
+            ":not_null",
+            "return-void"
+    );
+    buildAndTest(builder, signature, (appInfo, typeAnalysis) -> {
+      typeAnalysis.forEach((v, l) -> {
+        if (l instanceof ArrayTypeLatticeElement) {
+          ArrayTypeLatticeElement lattice = (ArrayTypeLatticeElement) l;
+          assertEquals(appInfo.dexItemFactory.stringType, lattice.elementType);
+          // TODO(b/70795205): Can be refined by using control-flow info.
+          assertTrue(l.isNullable());
+        }
+        if (l instanceof ClassTypeLatticeElement) {
+          ClassTypeLatticeElement lattice = (ClassTypeLatticeElement) l;
+          if (lattice.classType.equals(appInfo.dexItemFactory.stringType)) {
+            // An element inside a non-null array could be null.
+            assertTrue(lattice.isNullable());
+          } else {
+            // holder and newly created assertion error.
+            assertFalse(lattice.isNullable());
+          }
+        }
+      });
+    });
+  }
+
+  @Test
+  public void stillNullAfterExceptionCatch_aget() throws Exception {
+    SmaliBuilder builder = new SmaliBuilder(CLASS_NAME);
+    MethodSignature signature =
+        builder.addInstanceMethod("void", "foo", ImmutableList.of("java.lang.String[]"), 1,
+            ":try_start",
+            "const/4 v0, 0",
+            "aget-object v0, p1, v0",
+            "if-nez p1, :return",
+            "new-instance v0, Ljava/lang/AssertionError;",
+            "throw v0",
+            ":try_end",
+            ".catch Ljava/lang/Throwable; {:try_start .. :try_end} :return",
+            ":return",
+            // p1 could be still null at the outside of try-catch.
+            "invoke-virtual {p1}, [Ljava/lang/String;->hashCode()I",
+            "return-void"
+    );
+    buildAndTest(builder, signature, (appInfo, typeAnalysis) -> {
+      typeAnalysis.forEach((v, l) -> {
+        if (l instanceof ArrayTypeLatticeElement) {
+          ArrayTypeLatticeElement lattice = (ArrayTypeLatticeElement) l;
+          assertEquals(appInfo.dexItemFactory.stringType, lattice.elementType);
+          assertTrue(l.isNullable());
+        }
+        if (l instanceof ClassTypeLatticeElement) {
+          ClassTypeLatticeElement lattice = (ClassTypeLatticeElement) l;
+          if (lattice.classType.equals(appInfo.dexItemFactory.stringType)) {
+            // An element inside a non-null array could be null.
+            assertTrue(lattice.isNullable());
+          } else {
+            // holder and newly created assertion error.
+            assertFalse(lattice.isNullable());
+          }
+        }
+      });
+    });
+  }
+
+  @Test
+  public void nonNullAfterSafeFieldAccess() throws Exception {
+    SmaliBuilder builder = new SmaliBuilder(CLASS_NAME);
+    MethodSignature signature =
+        builder.addInstanceMethod("void", "foo", ImmutableList.of("Test"), 1,
+            "iget-object v0, p1, LTest;->bar:Ljava/lang/String;",
+            // Successful field access above means p1 is not null.
+            "if-nez p1, :not_null",
+            "new-instance v0, Ljava/lang/AssertionError;",
+            "throw v0",
+            ":not_null",
+            "return-void"
+    );
+    builder.addClass("Test");
+    builder.addInstanceField("bar", "Ljava/lang/String;");
+    buildAndTest(builder, signature, (appInfo, typeAnalysis) -> {
+      DexType testType = appInfo.dexItemFactory.createType("LTest;");
+      typeAnalysis.forEach((v, l) -> {
+        assertTrue(l instanceof ClassTypeLatticeElement);
+        ClassTypeLatticeElement lattice = (ClassTypeLatticeElement) l;
+        if (lattice.classType.equals(appInfo.dexItemFactory.stringType)) {
+          // instance may not be initialized.
+          assertTrue(lattice.isNullable());
+        } else if (lattice.classType.equals(testType)) {
+          // TODO(b/70795205): Can be refined by using control-flow info.
+          // parameter
+          assertTrue(lattice.isNullable());
+        } else {
+          // holder and newly created assertion error.
+          assertFalse(lattice.isNullable());
+        }
+      });
+    });
+  }
+
+  @Test
+  public void stillNullAfterExceptionCatch_iget() throws Exception {
+    SmaliBuilder builder = new SmaliBuilder(CLASS_NAME);
+    MethodSignature signature =
+        builder.addInstanceMethod("void", "foo", ImmutableList.of("Test"), 1,
+            ":try_start",
+            "iget-object v0, p1, LTest;->bar:Ljava/lang/String;",
+            "if-nez p1, :return",
+            "new-instance v0, Ljava/lang/AssertionError;",
+            "throw v0",
+            ":try_end",
+            ".catch Ljava/lang/Throwable; {:try_start .. :try_end} :return",
+            ":return",
+            // p1 could be still null at the outside of try-catch.
+            "invoke-virtual {p1}, LTest;->hashCode()I",
+            "return-void"
+    );
+    builder.addClass("Test");
+    builder.addInstanceField("bar", "Ljava/lang/String;");
+    buildAndTest(builder, signature, (appInfo, typeAnalysis) -> {
+      DexType testType = appInfo.dexItemFactory.createType("LTest;");
+      typeAnalysis.forEach((v, l) -> {
+        assertTrue(l instanceof ClassTypeLatticeElement);
+        ClassTypeLatticeElement lattice = (ClassTypeLatticeElement) l;
+        if (lattice.classType.equals(appInfo.dexItemFactory.stringType)) {
+          // instance may not be initialized.
+          assertTrue(lattice.isNullable());
+        } else if (lattice.classType.equals(testType)) {
+          // parameter
+          assertTrue(lattice.isNullable());
+        } else {
+          // holder and newly created assertion error.
+          assertFalse(lattice.isNullable());
+        }
+      });
+    });
+  }
+}
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
new file mode 100644
index 0000000..9bd8af6
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/analysis/type/TypeAnalysisTest.java
@@ -0,0 +1,345 @@
+// Copyright (c) 2017, 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 static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import com.android.tools.r8.ApiLevelException;
+import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.dex.ApplicationReader;
+import com.android.tools.r8.graph.AppInfoWithSubtyping;
+import com.android.tools.r8.graph.DexApplication;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.code.ArrayLength;
+import com.android.tools.r8.ir.code.CheckCast;
+import com.android.tools.r8.ir.code.ConstNumber;
+import com.android.tools.r8.ir.code.ConstString;
+import com.android.tools.r8.ir.code.IRCode;
+import com.android.tools.r8.ir.code.InstanceOf;
+import com.android.tools.r8.ir.code.Instruction;
+import com.android.tools.r8.ir.code.InstructionIterator;
+import com.android.tools.r8.ir.code.InvokeNewArray;
+import com.android.tools.r8.ir.code.NewArrayEmpty;
+import com.android.tools.r8.ir.code.NewInstance;
+import com.android.tools.r8.ir.code.StaticGet;
+import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.naming.MemberNaming.MethodSignature;
+import com.android.tools.r8.origin.Origin;
+import com.android.tools.r8.smali.SmaliTestBase;
+import com.android.tools.r8.utils.AndroidApp;
+import com.android.tools.r8.utils.DexInspector;
+import com.android.tools.r8.utils.InternalOptions;
+import com.android.tools.r8.utils.Smali;
+import com.android.tools.r8.utils.Timing;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Maps;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+import java.nio.charset.StandardCharsets;
+import java.nio.file.Files;
+import java.nio.file.Path;
+import java.nio.file.Paths;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.function.Consumer;
+
+@RunWith(Parameterized.class)
+public class TypeAnalysisTest extends SmaliTestBase {
+  private static final InternalOptions TEST_OPTIONS = new InternalOptions();
+  private static final TypeLatticeElement PRIMITIVE = PrimitiveTypeLatticeElement.getInstance();
+
+  private final String dirName;
+  private final String smaliFileName;
+  private final Consumer<AppInfoWithSubtyping> inspection;
+
+  public TypeAnalysisTest(String test, Consumer<AppInfoWithSubtyping> inspection) {
+    dirName = test.substring(0, test.lastIndexOf('/'));
+    smaliFileName = test.substring(test.lastIndexOf('/') + 1) + ".smali";
+    this.inspection = inspection;
+  }
+
+  @Parameters(name = "{0}")
+  public static Collection<Object[]> data() throws Exception {
+    List<String> tests = Arrays.asList(
+        "arithmetic/Arithmetic",
+        "fibonacci/Fibonacci",
+        "fill-array-data/FillArrayData",
+        "filled-new-array/FilledNewArray",
+        "infinite-loop/InfiniteLoop1",
+        "try-catch/TryCatch",
+        "type-confusion-regression/TestObject",
+        "type-confusion-regression5/TestObject"
+    );
+
+    Map<String, Consumer<AppInfoWithSubtyping>> inspections = new HashMap<>();
+    inspections.put("arithmetic/Arithmetic", TypeAnalysisTest::arithmetic);
+    inspections.put("fibonacci/Fibonacci", TypeAnalysisTest::fibonacci);
+    inspections.put("fill-array-data/FillArrayData", TypeAnalysisTest::fillArrayData);
+    inspections.put("filled-new-array/FilledNewArray", TypeAnalysisTest::filledNewArray);
+    inspections.put("infinite-loop/InfiniteLoop1", TypeAnalysisTest::infiniteLoop);
+    inspections.put("try-catch/TryCatch", TypeAnalysisTest::tryCatch);
+    inspections.put("type-confusion-regression/TestObject", TypeAnalysisTest::typeConfusion);
+    inspections.put("type-confusion-regression5/TestObject", TypeAnalysisTest::typeConfusion5);
+
+    List<Object[]> testCases = new ArrayList<>();
+    for (String test : tests) {
+      Consumer<AppInfoWithSubtyping> inspection = inspections.get(test);
+      testCases.add(new Object[]{test, inspection});
+    }
+    return testCases;
+  }
+
+  @Test
+  public void typeAnalysisTest() throws Exception {
+    Path smaliPath = Paths.get(ToolHelper.SMALI_DIR, dirName, smaliFileName);
+    StringBuilder smaliStringBuilder = new StringBuilder();
+    Files.lines(smaliPath, StandardCharsets.UTF_8)
+        .forEach(s -> smaliStringBuilder.append(s).append(System.lineSeparator()));
+    byte[] content = Smali.compile(smaliStringBuilder.toString());
+    AndroidApp app = AndroidApp.builder().addDexProgramData(content, Origin.unknown()).build();
+    DexApplication dexApplication =
+        new ApplicationReader(app, TEST_OPTIONS, new Timing("TypeAnalysisTest.appReader"))
+            .read().toDirect();
+    inspection.accept(new AppInfoWithSubtyping(dexApplication));
+  }
+
+  // Simple one path with a lot of arithmetic operations.
+  private static void arithmetic(AppInfoWithSubtyping appInfo) {
+    DexInspector inspector = new DexInspector(appInfo.app);
+    DexEncodedMethod subtract =
+        inspector.clazz("Test")
+            .method(
+                new MethodSignature("subtractConstants8bitRegisters", "int", ImmutableList.of()))
+            .getMethod();
+    try {
+      IRCode irCode = subtract.buildIR(TEST_OPTIONS);
+      TypeAnalysis analysis = new TypeAnalysis(appInfo, subtract, irCode);
+      analysis.run();
+      analysis.forEach((v, l) -> {
+        assertEquals(l, PRIMITIVE);
+      });
+    } catch (ApiLevelException e) {
+      fail(e.getMessage());
+    }
+  }
+
+  // A couple branches, along with some recursive calls.
+  private static void fibonacci(AppInfoWithSubtyping appInfo) {
+    DexInspector inspector = new DexInspector(appInfo.app);
+    DexEncodedMethod fib =
+        inspector.clazz("Test")
+            .method(new MethodSignature("fibonacci", "int", ImmutableList.of("int")))
+            .getMethod();
+    try {
+      IRCode irCode = fib.buildIR(TEST_OPTIONS);
+      TypeAnalysis analysis = new TypeAnalysis(appInfo, fib, irCode);
+      analysis.run();
+      analysis.forEach((v, l) -> {
+        assertEquals(l, PRIMITIVE);
+      });
+    } catch (ApiLevelException e) {
+      fail(e.getMessage());
+    }
+  }
+
+  // fill-array-data
+  private static void fillArrayData(AppInfoWithSubtyping appInfo) {
+    DexInspector inspector = new DexInspector(appInfo.app);
+    DexEncodedMethod test1 =
+        inspector.clazz("Test")
+            .method(new MethodSignature("test1", "int[]", ImmutableList.of()))
+            .getMethod();
+    try {
+      IRCode irCode = test1.buildIR(TEST_OPTIONS);
+      TypeAnalysis analysis = new TypeAnalysis(appInfo, test1, irCode);
+      analysis.run();
+      Value array = null;
+      InstructionIterator iterator = irCode.instructionIterator();
+      while (iterator.hasNext()) {
+        Instruction instruction = iterator.next();
+        if (instruction instanceof NewArrayEmpty) {
+          array = instruction.outValue();
+          break;
+        }
+      }
+      assertNotNull(array);
+      final Value finalArray = array;
+      analysis.forEach((v, l) -> {
+        if (v == finalArray) {
+          assertTrue(l instanceof PrimitiveArrayTypeLatticeElement);
+          PrimitiveArrayTypeLatticeElement lattice = (PrimitiveArrayTypeLatticeElement) l;
+          assertEquals(1, lattice.nesting);
+          assertFalse(l.isNullable());
+        }
+      });
+    } catch (ApiLevelException e) {
+      fail(e.getMessage());
+    }
+  }
+
+  // filled-new-array
+  private static void filledNewArray(AppInfoWithSubtyping appInfo) {
+    DexInspector inspector = new DexInspector(appInfo.app);
+    DexEncodedMethod test4 =
+        inspector.clazz("Test")
+            .method(new MethodSignature("test4", "int[]", ImmutableList.of()))
+            .getMethod();
+    try {
+      IRCode irCode = test4.buildIR(TEST_OPTIONS);
+      TypeAnalysis analysis = new TypeAnalysis(appInfo, test4, irCode);
+      analysis.run();
+      Value array = null;
+      InstructionIterator iterator = irCode.instructionIterator();
+      while (iterator.hasNext()) {
+        Instruction instruction = iterator.next();
+        if (instruction instanceof InvokeNewArray) {
+          array = instruction.outValue();
+          break;
+        }
+      }
+      assertNotNull(array);
+      final Value finalArray = array;
+      analysis.forEach((v, l) -> {
+        if (v == finalArray) {
+          assertTrue(l instanceof PrimitiveArrayTypeLatticeElement);
+          PrimitiveArrayTypeLatticeElement lattice = (PrimitiveArrayTypeLatticeElement) l;
+          assertEquals(1, lattice.nesting);
+          assertFalse(l.isNullable());
+        }
+      });
+    } catch (ApiLevelException e) {
+      fail(e.getMessage());
+    }
+  }
+
+  // Make sure the analysis does not hang.
+  private static void infiniteLoop(AppInfoWithSubtyping appInfo) {
+    DexInspector inspector = new DexInspector(appInfo.app);
+    DexEncodedMethod loop2 =
+        inspector.clazz("Test")
+            .method(new MethodSignature("loop2", "void", ImmutableList.of()))
+            .getMethod();
+    try {
+      IRCode irCode = loop2.buildIR(TEST_OPTIONS);
+      TypeAnalysis analysis = new TypeAnalysis(appInfo, loop2, irCode);
+      analysis.run();
+      analysis.forEach((v, l) -> {
+        if (l instanceof ClassTypeLatticeElement) {
+          ClassTypeLatticeElement lattice = (ClassTypeLatticeElement) l;
+          assertEquals("Ljava/io/PrintStream;", lattice.classType.toDescriptorString());
+          // TODO(b/70795205): Can be refined by using control-flow info.
+          assertTrue(l.isNullable());
+        }
+      });
+    } catch (ApiLevelException e) {
+      fail(e.getMessage());
+    }
+  }
+
+  // move-exception
+  private static void tryCatch(AppInfoWithSubtyping appInfo) {
+    DexInspector inspector = new DexInspector(appInfo.app);
+    DexEncodedMethod test2 =
+        inspector.clazz("Test")
+            .method(new MethodSignature("test2_throw", "int", ImmutableList.of()))
+            .getMethod();
+    try {
+      IRCode irCode = test2.buildIR(TEST_OPTIONS);
+      TypeAnalysis analysis = new TypeAnalysis(appInfo, test2, irCode);
+      analysis.run();
+      analysis.forEach((v, l) -> {
+        if (l instanceof ClassTypeLatticeElement) {
+          ClassTypeLatticeElement lattice = (ClassTypeLatticeElement) l;
+          assertEquals("Ljava/lang/Throwable;", lattice.classType.toDescriptorString());
+          assertFalse(l.isNullable());
+        }
+      });
+    } catch (ApiLevelException e) {
+      fail(e.getMessage());
+    }
+  }
+
+  // One very complicated example.
+  private static void typeConfusion(AppInfoWithSubtyping appInfo) {
+    DexInspector inspector = new DexInspector(appInfo.app);
+    DexEncodedMethod method =
+        inspector.clazz("TestObject")
+            .method(
+                new MethodSignature("a", "void",
+                    ImmutableList.of("Test", "Test", "Test", "Test")))
+            .getMethod();
+
+    DexType test = appInfo.dexItemFactory.createType("LTest;");
+    Map<Class<? extends Instruction>, TypeLatticeElement> expectedLattices = Maps.newHashMap();
+    expectedLattices.put(ArrayLength.class, PRIMITIVE);
+    expectedLattices.put(ConstNumber.class, PRIMITIVE);
+    expectedLattices.put(
+        ConstString.class, new ClassTypeLatticeElement(appInfo.dexItemFactory.stringType, false));
+    expectedLattices.put(CheckCast.class, new ClassTypeLatticeElement(test, true));
+    expectedLattices.put(NewInstance.class, new ClassTypeLatticeElement(test, false));
+
+    try {
+      IRCode irCode = method.buildIR(TEST_OPTIONS);
+      TypeAnalysis analysis = new TypeAnalysis(appInfo, method, irCode);
+      analysis.run();
+      analysis.forEach((v, l) -> {
+        if (v.definition == null) {
+          return;
+        }
+        TypeLatticeElement expected = expectedLattices.get(v.definition.getClass());
+        if (expected != null) {
+          assertEquals(expected, l);
+        }
+      });
+    } catch (ApiLevelException e) {
+      fail(e.getMessage());
+    }
+  }
+
+  // One more complicated example.
+  private static void typeConfusion5(AppInfoWithSubtyping appInfo) {
+    DexInspector inspector = new DexInspector(appInfo.app);
+    DexEncodedMethod method =
+        inspector.clazz("TestObject")
+            .method(
+                new MethodSignature("onClick", "void", ImmutableList.of("Test")))
+            .getMethod();
+
+    DexType test = appInfo.dexItemFactory.createType("LTest;");
+    Map<Class<? extends Instruction>, TypeLatticeElement> expectedLattices = Maps.newHashMap();
+    expectedLattices.put(ConstNumber.class, PRIMITIVE);
+    expectedLattices.put(
+        ConstString.class, new ClassTypeLatticeElement(appInfo.dexItemFactory.stringType, false));
+    expectedLattices.put(InstanceOf.class, PRIMITIVE);
+    expectedLattices.put(StaticGet.class, new ClassTypeLatticeElement(test, true));
+
+    try {
+      IRCode irCode = method.buildIR(TEST_OPTIONS);
+      TypeAnalysis analysis = new TypeAnalysis(appInfo, method, irCode);
+      analysis.run();
+      analysis.forEach((v, l) -> {
+        if (v.definition == null) {
+          return;
+        }
+        TypeLatticeElement expected = expectedLattices.get(v.definition.getClass());
+        if (expected != null) {
+          assertEquals(expected, l);
+        }
+      });
+    } catch (ApiLevelException e) {
+      fail(e.getMessage());
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/utils/DexInspector.java b/src/test/java/com/android/tools/r8/utils/DexInspector.java
index 56ba5a5..bbd6fb5 100644
--- a/src/test/java/com/android/tools/r8/utils/DexInspector.java
+++ b/src/test/java/com/android/tools/r8/utils/DexInspector.java
@@ -63,6 +63,7 @@
 import com.android.tools.r8.naming.MemberNaming.FieldSignature;
 import com.android.tools.r8.naming.MemberNaming.MethodSignature;
 import com.android.tools.r8.naming.MemberNaming.Signature;
+import com.android.tools.r8.smali.SmaliBuilder;
 import com.google.common.collect.BiMap;
 import com.google.common.collect.ImmutableList;
 import java.io.IOException;
@@ -286,6 +287,11 @@
       return method(signature.type, signature.name, ImmutableList.copyOf(signature.parameters));
     }
 
+    public MethodSubject method(SmaliBuilder.MethodSignature signature) {
+      return method(
+          signature.returnType, signature.name, ImmutableList.copyOf(signature.parameterTypes));
+    }
+
     public abstract void forAllFields(Consumer<FoundFieldSubject> inspection);
 
     public abstract FieldSubject field(String type, String name);
diff --git a/src/test/smali/try-catch/TryCatch.smali b/src/test/smali/try-catch/TryCatch.smali
index 2becd5f..8e06c5a 100644
--- a/src/test/smali/try-catch/TryCatch.smali
+++ b/src/test/smali/try-catch/TryCatch.smali
@@ -32,6 +32,23 @@
     return v0
 .end method
 
+.method public static test2_throw()I
+    .locals 1
+    const v0, 1
+    :try_start
+    invoke-static {}, Ltest/X;->f()V
+    const v0, 0
+    goto :return
+    :try_end
+    .catch Ljava/lang/Exception; {:try_start .. :try_end} :return
+    .catch Ljava/lang/Throwable; {:try_start .. :try_end} :error
+    :error
+    move-exception v0
+    throw v0
+    :return
+    return v0
+.end method
+
 # Dead catch block.
 .method public test3()I
     .locals 1