diff --git a/build.gradle b/build.gradle
index 234fe25..418474a 100644
--- a/build.gradle
+++ b/build.gradle
@@ -268,6 +268,7 @@
         ],
         "third_party": [
                 "android_jar/lib-v14",
+                "android_jar/lib-v15",
                 "android_jar/lib-v19",
                 "android_jar/lib-v21",
                 "android_jar/lib-v24",
diff --git a/src/main/java/com/android/tools/r8/D8.java b/src/main/java/com/android/tools/r8/D8.java
index 94d8350..fca359f 100644
--- a/src/main/java/com/android/tools/r8/D8.java
+++ b/src/main/java/com/android/tools/r8/D8.java
@@ -141,7 +141,7 @@
   }
 
   // Compute the marker to be placed in the main dex file.
-  private static Marker getMarker(InternalOptions options) {
+  static Marker getMarker(InternalOptions options) {
     if (options.hasMarker()) {
       return options.getMarker();
     }
@@ -184,9 +184,12 @@
     }
   }
 
-  private static DexApplication optimize(
-      DexApplication application, AppInfo appInfo, InternalOptions options,
-      Timing timing, ExecutorService executor)
+  static DexApplication optimize(
+      DexApplication application,
+      AppInfo appInfo,
+      InternalOptions options,
+      Timing timing,
+      ExecutorService executor)
       throws IOException, ExecutionException, ApiLevelException {
     final CfgPrinter printer = options.printCfg ? new CfgPrinter() : null;
 
diff --git a/src/main/java/com/android/tools/r8/DexFileMergerHelper.java b/src/main/java/com/android/tools/r8/DexFileMergerHelper.java
index de58c61..57b3804 100644
--- a/src/main/java/com/android/tools/r8/DexFileMergerHelper.java
+++ b/src/main/java/com/android/tools/r8/DexFileMergerHelper.java
@@ -4,24 +4,88 @@
 
 package com.android.tools.r8;
 
-import com.android.tools.r8.utils.AndroidApp;
+import com.android.tools.r8.dex.ApplicationReader;
+import com.android.tools.r8.dex.ApplicationWriter;
+import com.android.tools.r8.graph.AppInfo;
+import com.android.tools.r8.graph.DexApplication;
+import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.utils.InternalOptions;
+import com.android.tools.r8.utils.ThreadUtils;
+import com.android.tools.r8.utils.Timing;
 import java.io.IOException;
+import java.util.Map;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.ExecutorService;
 
 public class DexFileMergerHelper {
-  public static void run(D8Command command, Boolean minimalMainDex)
-      throws IOException, CompilationException {
-    AndroidApp app = command.getInputApp();
+
+  private final Map<String, Integer> inputOrdering;
+
+  private DexFileMergerHelper(Map<String, Integer> inputOrdering) {
+    this.inputOrdering = inputOrdering;
+  }
+
+  private DexProgramClass keepFirstProgramClassConflictResolver(
+      DexProgramClass a, DexProgramClass b) {
+    String aPath = a.getOrigin().parent().part();
+    String bPath = b.getOrigin().parent().part();
+    Integer aIndex = inputOrdering.get(aPath);
+    Integer bIndex = inputOrdering.get(bPath);
+    if (aIndex == null || bIndex == null) {
+      StringBuilder builder = new StringBuilder();
+      builder.append("Class parent paths not found among input paths: ");
+      if (aIndex == null) {
+        builder.append(aPath);
+      }
+      if (bIndex == null) {
+        if (aIndex == null) {
+          builder.append(", ");
+        }
+        builder.append(bPath);
+      }
+      throw new RuntimeException(builder.toString());
+    }
+    return aIndex <= bIndex ? a.get() : b.get();
+  }
+
+  public static void run(
+      D8Command command, Boolean minimalMainDex, Map<String, Integer> inputOrdering)
+      throws IOException, CompilationException, ExecutionException {
     InternalOptions options = command.getInternalOptions();
-    // DX does not desugar.
     options.enableDesugaring = false;
-    // DX allows --multi-dex without specifying a main dex list for legacy devices.
-    // That is broken, but for CompatDX we do the same to not break existing builds
-    // that are trying to transition.
     options.enableMainDexListCheck = false;
-    // DX has a minimal main dex flag. In compat mode only do minimal main dex
-    // if the flag is actually set.
     options.minimalMainDex = minimalMainDex;
-    D8.runForTesting(app, options);
+    options.skipMinification = true;
+    options.inlineAccessors = false;
+    options.outline.enabled = false;
+
+    ExecutorService executor = ThreadUtils.getExecutorService(ThreadUtils.NOT_SPECIFIED);
+    try {
+      try {
+        Timing timing = new Timing("DexFileMerger");
+        DexApplication app =
+            new ApplicationReader(command.getInputApp(), options, timing)
+                .read(
+                    null,
+                    executor,
+                    new DexFileMergerHelper(inputOrdering)::keepFirstProgramClassConflictResolver);
+        AppInfo appInfo = new AppInfo(app);
+        app = D8.optimize(app, appInfo, options, timing, executor);
+
+        assert !options.hasMethodsFilter();
+        new ApplicationWriter(
+                app, options, D8.getMarker(options), null, NamingLens.getIdentityLens(), null, null)
+            .write(executor);
+        options.printWarnings();
+      } catch (ExecutionException e) {
+        R8.unwrapExecutionException(e);
+        throw new AssertionError(e); // unwrapping method should have thrown
+      } finally {
+        options.signalFinishedToProgramConsumer();
+      }
+    } finally {
+      executor.shutdown();
+    }
   }
 }
diff --git a/src/main/java/com/android/tools/r8/dex/ApplicationReader.java b/src/main/java/com/android/tools/r8/dex/ApplicationReader.java
index 64dc47d..450cdab 100644
--- a/src/main/java/com/android/tools/r8/dex/ApplicationReader.java
+++ b/src/main/java/com/android/tools/r8/dex/ApplicationReader.java
@@ -32,6 +32,7 @@
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.LibraryClassCollection;
 import com.android.tools.r8.utils.MainDexList;
+import com.android.tools.r8.utils.ProgramClassCollection;
 import com.android.tools.r8.utils.StringDiagnostic;
 import com.android.tools.r8.utils.ThreadUtils;
 import com.android.tools.r8.utils.Timing;
@@ -54,6 +55,10 @@
   final Timing timing;
   private final AndroidApp inputApp;
 
+  public interface ProgramClassConflictResolver {
+    DexProgramClass resolveClassConflict(DexProgramClass a, DexProgramClass b);
+  }
+
   public ApplicationReader(AndroidApp inputApp, InternalOptions options, Timing timing) {
     this.options = options;
     itemFactory = options.itemFactory;
@@ -76,13 +81,22 @@
 
   public final DexApplication read(ExecutorService executorService)
       throws IOException, ExecutionException {
-    return read(null, executorService);
+    return read(null, executorService, ProgramClassCollection::resolveClassConflictImpl);
   }
 
   public final DexApplication read(StringResource proguardMap, ExecutorService executorService)
       throws IOException, ExecutionException {
+    return read(proguardMap, executorService, ProgramClassCollection::resolveClassConflictImpl);
+  }
+
+  public final DexApplication read(
+      StringResource proguardMap,
+      ExecutorService executorService,
+      ProgramClassConflictResolver resolver)
+      throws IOException, ExecutionException {
     timing.begin("DexApplication.read");
-    final LazyLoadedDexApplication.Builder builder = DexApplication.builder(itemFactory, timing);
+    final LazyLoadedDexApplication.Builder builder =
+        DexApplication.builder(itemFactory, timing, resolver);
     try {
       List<Future<?>> futures = new ArrayList<>();
       // Still preload some of the classes, primarily for two reasons:
diff --git a/src/main/java/com/android/tools/r8/dexfilemerger/DexFileMerger.java b/src/main/java/com/android/tools/r8/dexfilemerger/DexFileMerger.java
index 5e0b4e9..249e7a1 100644
--- a/src/main/java/com/android/tools/r8/dexfilemerger/DexFileMerger.java
+++ b/src/main/java/com/android/tools/r8/dexfilemerger/DexFileMerger.java
@@ -20,19 +20,16 @@
 import java.nio.file.Paths;
 import java.util.ArrayList;
 import java.util.Collections;
+import java.util.HashMap;
 import java.util.List;
+import java.util.Map;
 import java.util.Set;
+import java.util.concurrent.ExecutionException;
 import java.util.regex.Matcher;
 import java.util.regex.Pattern;
 import java.util.zip.ZipOutputStream;
 
 public class DexFileMerger {
-  /**
-   * Maximum addressable field or method index. The largest addressable member is 0xffff, in the
-   * "instruction formats" spec as field@CCCC or meth@CCCC.
-   */
-  private static final int MAX_MEMBER_IDX = 0xFFFF;
-
   /** File name prefix of a {@code .dex} file automatically loaded in an archive. */
   private static final String DEX_PREFIX = "classes";
 
@@ -281,7 +278,7 @@
   }
 
   public static void run(String[] args)
-      throws CompilationFailedException, IOException, CompilationException {
+      throws CompilationFailedException, IOException, CompilationException, ExecutionException {
     Options options = parseArguments(args);
 
     if (options.inputArchives.isEmpty()) {
@@ -308,8 +305,11 @@
 
     D8Command.Builder builder = D8Command.builder();
 
+    Map<String, Integer> inputOrdering = new HashMap<>(options.inputArchives.size());
+    int sequenceNumber = 0;
     for (String s : options.inputArchives) {
       builder.addProgramFiles(Paths.get(s));
+      inputOrdering.put(s, sequenceNumber++);
     }
 
     // Determine enabling multidexing and file indexing.
@@ -341,7 +341,7 @@
             Paths.get(options.outputArchive), options.dexPrefix, singleFixedFileIndex);
     builder.setProgramConsumer(consumer);
 
-    DexFileMergerHelper.run(builder.build(), options.minimalMainDex);
+    DexFileMergerHelper.run(builder.build(), options.minimalMainDex, inputOrdering);
 
     // If input was empty we still need to write out an empty zip.
     if (!consumer.dataHasBeenWritten) {
@@ -357,7 +357,10 @@
         printArgs(args);
       }
       run(args);
-    } catch (CompilationFailedException | IOException | CompilationException e) {
+    } catch (CompilationFailedException
+        | IOException
+        | CompilationException
+        | ExecutionException e) {
       System.err.println("Merge failed: " + e.getMessage());
       System.exit(1);
     }
diff --git a/src/main/java/com/android/tools/r8/graph/DexApplication.java b/src/main/java/com/android/tools/r8/graph/DexApplication.java
index c05b025..8b2fee9 100644
--- a/src/main/java/com/android/tools/r8/graph/DexApplication.java
+++ b/src/main/java/com/android/tools/r8/graph/DexApplication.java
@@ -6,6 +6,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.graph;
 
+import com.android.tools.r8.dex.ApplicationReader.ProgramClassConflictResolver;
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.naming.ClassNameMapper;
 import com.android.tools.r8.utils.ProgramClassCollection;
@@ -21,7 +22,7 @@
 public abstract class DexApplication {
 
   // Maps type into class, may be used concurrently.
-  ProgramClassCollection programClasses;
+  final ProgramClassCollection programClasses;
 
   public final ImmutableSet<DexType> mainDexList;
   public final String deadCode;
@@ -198,7 +199,12 @@
   }
 
   public static LazyLoadedDexApplication.Builder builder(DexItemFactory factory, Timing timing) {
-    return new LazyLoadedDexApplication.Builder(factory, timing);
+    return builder(factory, timing, ProgramClassCollection::resolveClassConflictImpl);
+  }
+
+  public static LazyLoadedDexApplication.Builder builder(
+      DexItemFactory factory, Timing timing, ProgramClassConflictResolver resolver) {
+    return new LazyLoadedDexApplication.Builder(resolver, factory, timing);
   }
 
   public DirectMappedDexApplication asDirect() {
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/graph/DirectMappedDexApplication.java b/src/main/java/com/android/tools/r8/graph/DirectMappedDexApplication.java
index 1e0b1e2..e958a5d 100644
--- a/src/main/java/com/android/tools/r8/graph/DirectMappedDexApplication.java
+++ b/src/main/java/com/android/tools/r8/graph/DirectMappedDexApplication.java
@@ -112,11 +112,16 @@
     @Override
     public DexApplication build() {
       // Rebuild the map. This will fail if keys are not unique.
-      return new DirectMappedDexApplication(proguardMap,
-          ProgramClassCollection.create(programClasses),
+      return new DirectMappedDexApplication(
+          proguardMap,
+          ProgramClassCollection.create(
+              programClasses, ProgramClassCollection::resolveClassConflictImpl),
           libraryClasses.stream().collect(ImmutableMap.toImmutableMap(c -> c.type, c -> c)),
-          ImmutableSet.copyOf(mainDexList), deadCode,
-          dexItemFactory, highestSortingString, timing);
+          ImmutableSet.copyOf(mainDexList),
+          deadCode,
+          dexItemFactory,
+          highestSortingString,
+          timing);
     }
   }
 }
diff --git a/src/main/java/com/android/tools/r8/graph/LazyLoadedDexApplication.java b/src/main/java/com/android/tools/r8/graph/LazyLoadedDexApplication.java
index 97911a1..db521f9 100644
--- a/src/main/java/com/android/tools/r8/graph/LazyLoadedDexApplication.java
+++ b/src/main/java/com/android/tools/r8/graph/LazyLoadedDexApplication.java
@@ -6,6 +6,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.graph;
 
+import com.android.tools.r8.dex.ApplicationReader.ProgramClassConflictResolver;
 import com.android.tools.r8.naming.ClassNameMapper;
 import com.android.tools.r8.utils.ClasspathClassCollection;
 import com.android.tools.r8.utils.LibraryClassCollection;
@@ -82,15 +83,18 @@
 
     private ClasspathClassCollection classpathClasses;
     private LibraryClassCollection libraryClasses;
+    private final ProgramClassConflictResolver resolver;
 
-    Builder(DexItemFactory dexItemFactory, Timing timing) {
+    Builder(ProgramClassConflictResolver resolver, DexItemFactory dexItemFactory, Timing timing) {
       super(dexItemFactory, timing);
+      this.resolver = resolver;
       this.classpathClasses = null;
       this.libraryClasses = null;
     }
 
     private Builder(LazyLoadedDexApplication application) {
       super(application);
+      this.resolver = ProgramClassCollection::resolveClassConflictImpl;
       this.classpathClasses = application.classpathClasses;
       this.libraryClasses = application.libraryClasses;
     }
@@ -112,10 +116,16 @@
 
     @Override
     public LazyLoadedDexApplication build() {
-      return new LazyLoadedDexApplication(proguardMap,
-          ProgramClassCollection.create(programClasses),
-          classpathClasses, libraryClasses, ImmutableSet.copyOf(mainDexList), deadCode,
-          dexItemFactory, highestSortingString, timing);
+      return new LazyLoadedDexApplication(
+          proguardMap,
+          ProgramClassCollection.create(programClasses, resolver),
+          classpathClasses,
+          libraryClasses,
+          ImmutableSet.copyOf(mainDexList),
+          deadCode,
+          dexItemFactory,
+          highestSortingString,
+          timing);
     }
   }
 
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/constant/SparseConditionalConstantPropagation.java b/src/main/java/com/android/tools/r8/ir/analysis/constant/SparseConditionalConstantPropagation.java
index be3fc05..d5bf54b 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/constant/SparseConditionalConstantPropagation.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/constant/SparseConditionalConstantPropagation.java
@@ -13,12 +13,12 @@
 import com.android.tools.r8.ir.code.Phi;
 import com.android.tools.r8.ir.code.Switch;
 import com.android.tools.r8.ir.code.Value;
-import com.google.common.base.Equivalence;
-import com.google.common.base.Equivalence.Wrapper;
+import java.util.ArrayList;
 import java.util.BitSet;
 import java.util.Deque;
 import java.util.HashMap;
 import java.util.LinkedList;
+import java.util.List;
 import java.util.Map;
 
 /**
@@ -75,30 +75,9 @@
     assert code.isConsistentSSA();
   }
 
-  private static class PhiEquivalence extends Equivalence<Phi> {
-
-    @Override
-    protected boolean doEquivalent(Phi a, Phi b) {
-      assert a.getBlock() == b.getBlock();
-      for (int i = 0; i < a.getOperands().size(); i++) {
-        if (a.getOperand(i) != b.getOperand(i)) {
-          return false;
-        }
-      }
-      return true;
-    }
-
-    @Override
-    protected int doHash(Phi phi) {
-      int hash = 0;
-      for (Value value : phi.getOperands()) {
-        hash = hash * 13 + value.hashCode();
-      }
-      return hash;
-    }
-  }
-
   private void rewriteCode() {
+    List<BasicBlock> blockToAnalyze = new ArrayList<>();
+
     mapping.entrySet().stream()
         .filter((entry) -> entry.getValue().isConst())
         .forEach((entry) -> {
@@ -109,6 +88,7 @@
               // D8 relies on dead code removal to get rid of the dead phi itself.
               if (value.numberOfAllUsers() != 0) {
                 BasicBlock block = value.asPhi().getBlock();
+                blockToAnalyze.add(block);
                 // Create a new constant, because it can be an existing constant that flow directly
                 // into the phi.
                 ConstNumber newConst = ConstNumber.copyOf(code, evaluatedConst);
@@ -130,18 +110,8 @@
           }
         });
 
-    for (BasicBlock block : code.blocks) {
-      PhiEquivalence equivalence = new PhiEquivalence();
-      HashMap<Wrapper<Phi>, Phi> phis = new HashMap<>();
-      for (Phi phi : block.getPhis()) {
-        Wrapper<Phi> key = equivalence.wrap(phi);
-        Phi replacement = phis.get(key);
-        if (replacement != null) {
-          phi.replaceUsers(replacement);
-        } else {
-          phis.put(key, phi);
-        }
-      }
+    for (BasicBlock block : blockToAnalyze) {
+      block.deduplicatePhis();
     }
 
     code.removeAllTrivialPhis();
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/BasicBlock.java b/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
index 34a3e79..21bf14f 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
@@ -14,6 +14,8 @@
 import com.android.tools.r8.utils.ListUtils;
 import com.android.tools.r8.utils.StringUtils;
 import com.android.tools.r8.utils.StringUtils.BraceType;
+import com.google.common.base.Equivalence;
+import com.google.common.base.Equivalence.Wrapper;
 import com.google.common.collect.ImmutableList;
 import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
 import java.util.ArrayDeque;
@@ -21,6 +23,7 @@
 import java.util.Collection;
 import java.util.Collections;
 import java.util.HashMap;
+import java.util.Iterator;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.ListIterator;
@@ -1398,4 +1401,46 @@
 
     return false;
   }
+
+  private static class PhiEquivalence extends Equivalence<Phi> {
+    @Override
+    protected boolean doEquivalent(Phi a, Phi b) {
+      assert a.getBlock() == b.getBlock();
+      for (int i = 0; i < a.getOperands().size(); i++) {
+        if (a.getOperand(i) != b.getOperand(i)) {
+          return false;
+        }
+      }
+      return true;
+    }
+
+    @Override
+    protected int doHash(Phi phi) {
+      int hash = 0;
+      for (Value value : phi.getOperands()) {
+        hash = hash * 13 + value.hashCode();
+      }
+      return hash;
+    }
+  }
+
+  public void deduplicatePhis() {
+    PhiEquivalence equivalence = new PhiEquivalence();
+    HashMap<Wrapper<Phi>, Phi> wrapper2phi = new HashMap<>();
+    Iterator<Phi> phiIt = phis.iterator();
+    while (phiIt.hasNext()) {
+      Phi phi = phiIt.next();
+      Wrapper<Phi> key = equivalence.wrap(phi);
+      Phi replacement = wrapper2phi.get(key);
+      if (replacement != null) {
+        phi.replaceUsers(replacement);
+        for (Value operand : phi.getOperands()) {
+          operand.removePhiUser(phi);
+        }
+        phiIt.remove();
+      } else {
+        wrapper2phi.put(key, phi);
+      }
+    }
+  }
 }
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/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java b/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java
index e4168ea..b392308 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
@@ -414,6 +414,12 @@
     clearCanonicalizationMaps();
     source = null;
 
+    for (BasicBlock block : blocks) {
+      block.deduplicatePhis();
+    }
+
+    ir.removeAllTrivialPhis();
+
     assert ir.isConsistentSSA();
     return ir;
   }
diff --git a/src/main/java/com/android/tools/r8/utils/ProgramClassCollection.java b/src/main/java/com/android/tools/r8/utils/ProgramClassCollection.java
index 17ca1a9..3c802f5 100644
--- a/src/main/java/com/android/tools/r8/utils/ProgramClassCollection.java
+++ b/src/main/java/com/android/tools/r8/utils/ProgramClassCollection.java
@@ -3,6 +3,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.utils;
 
+import com.android.tools.r8.dex.ApplicationReader.ProgramClassConflictResolver;
 import com.android.tools.r8.errors.CompilationError;
 import com.android.tools.r8.graph.ClassKind;
 import com.android.tools.r8.graph.DexProgramClass;
@@ -14,11 +15,14 @@
 
 /** Represents a collection of library classes. */
 public class ProgramClassCollection extends ClassMap<DexProgramClass> {
-  public static ProgramClassCollection create(List<DexProgramClass> classes) {
+
+  public static ProgramClassCollection create(
+      List<DexProgramClass> classes, ProgramClassConflictResolver conflictResolver) {
     // We have all classes preloaded, but not necessarily without conflicts.
     IdentityHashMap<DexType, Supplier<DexProgramClass>> map = new IdentityHashMap<>();
     for (DexProgramClass clazz : classes) {
-      map.merge(clazz.type, clazz, (a, b) -> resolveClassConflictImpl(a.get(), b.get()));
+      map.merge(
+          clazz.type, clazz, (a, b) -> conflictResolver.resolveClassConflict(a.get(), b.get()));
     }
     return new ProgramClassCollection(map);
   }
@@ -47,7 +51,7 @@
     return ClassKind.PROGRAM;
   }
 
-  private static DexProgramClass resolveClassConflictImpl(DexProgramClass a, DexProgramClass b) {
+  public static DexProgramClass resolveClassConflictImpl(DexProgramClass a, DexProgramClass b) {
     // Currently only allow collapsing synthetic lambda classes.
     if (a.originatesFromDexResource()
         && b.originatesFromDexResource()
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/ir/optimize/TrivialGotoEliminationTest.java b/src/test/java/com/android/tools/r8/ir/optimize/TrivialGotoEliminationTest.java
index 07e38e5..8697917 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
@@ -48,7 +48,7 @@
     throwing.setPosition(Position.none());
     block1.add(throwing);
     block1.setFilledForTesting();
-    LinkedList<BasicBlock> blocks = new LinkedList();
+    LinkedList<BasicBlock> blocks = new LinkedList<>();
     blocks.add(block0);
     blocks.add(block1);
     blocks.add(block2);
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
diff --git a/third_party/android_jar/lib-v15.tar.gz.sha1 b/third_party/android_jar/lib-v15.tar.gz.sha1
new file mode 100644
index 0000000..e9ce20a
--- /dev/null
+++ b/third_party/android_jar/lib-v15.tar.gz.sha1
@@ -0,0 +1 @@
+fcbd85d969e36bdbda0a5a46aabc01331fec98b1
\ No newline at end of file