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 163c20b..60703de 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
@@ -495,6 +495,8 @@
 
   public void removePhi(Phi phi) {
     phis.remove(phi);
+    assert currentDefinitions == null || !currentDefinitions.containsValue(phi)
+        : "Attempt to remove Phi " + phi + " which is present in currentDefinitions";
   }
 
   public void add(Instruction next) {
@@ -678,7 +680,17 @@
   public void replaceCurrentDefinitions(Value oldValue, Value newValue) {
     assert oldValue.definition.getBlock() == this;
     assert !oldValue.isUsed();
-    currentDefinitions.replaceAll((index, value) -> value == oldValue ? newValue : value);
+    for (Entry<Integer, Value> entry : currentDefinitions.entrySet()) {
+      if (entry.getValue() == oldValue) {
+        if (oldValue.isPhi()) {
+          oldValue.asPhi().removeDefinitionsUser(currentDefinitions);
+        }
+        entry.setValue(newValue);
+        if (newValue.isPhi()) {
+          newValue.asPhi().addDefinitionsUser(currentDefinitions);
+        }
+      }
+    }
   }
 
   public void updateCurrentDefinition(int register, Value value, EdgeType readingEdge) {
diff --git a/src/test/java/com/android/tools/r8/ir/PhiDefinitionsTest.java b/src/test/java/com/android/tools/r8/ir/PhiDefinitionsTest.java
new file mode 100644
index 0000000..98db705
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/PhiDefinitionsTest.java
@@ -0,0 +1,61 @@
+// Copyright (c) 2018, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.ir;
+
+public class PhiDefinitionsTest {
+
+  public static Class[] CLASSES = {
+      PhiDefinitionsTest.class,
+      MethodWriter.class,
+  };
+
+  static class MethodWriter {
+    public int exceptionCount;
+  }
+
+  public static void main(String[] args) {
+    if (args.length >= 42) {
+      System.out.println(new PhiDefinitionsTest().readMethod(args.length));
+    }
+  }
+
+  private int readMethod(int u) {
+    u += 6;
+    int exception = 0;
+    for (int i = count(u); i > 0; --i) {
+      exception = count(u);
+      for (int j = count(); j > 0; --j) {
+        read(exception);
+        exception += 2;
+      }
+      u += 6 + count(u + 4);
+    }
+    u += 2;
+    MethodWriter mv = visitMethod();
+    if (cond() && cond() && cond()) {
+      MethodWriter mw = mv;
+      boolean sameExceptions = false;
+      if (count() == mw.exceptionCount) {
+        sameExceptions = true;
+        for (int j = count(); j >= 0; --j) {
+          exception -= 2;
+        }
+      }
+      if (cond()) {
+        return u;
+      }
+    }
+    return u;
+  }
+
+  private native MethodWriter visitMethod();
+
+  private native boolean cond();
+
+  private native String read(int i);
+
+  private native int count(int arg);
+
+  private native int count();
+}
diff --git a/src/test/java/com/android/tools/r8/ir/PhiDefinitionsTestDump.java b/src/test/java/com/android/tools/r8/ir/PhiDefinitionsTestDump.java
new file mode 100644
index 0000000..5a93117
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/PhiDefinitionsTestDump.java
@@ -0,0 +1,509 @@
+// Copyright (c) 2018, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.ir;
+
+import org.objectweb.asm.*;
+
+public class PhiDefinitionsTestDump implements Opcodes {
+
+  private static final String SIMPLE_NAME = "PhiDefinitionsTest";
+  static final String INTERNAL_NAME = "com/android/tools/r8/ir/" + SIMPLE_NAME;
+  private static final String INNER_SIMPLE_NAME = "MethodWriter";
+  static final String INNER_INTERNAL_NAME = INTERNAL_NAME + "$" + INNER_SIMPLE_NAME;
+
+  // static String INTERNAL_NAME = "com/android/tools/r8/ir/PhiDefinitionsTest";
+  // private static String INNER_SIMPLE_NAME = "MethodWriter";
+  // static String INNER_INTERNAL_NAME = INTERNAL_NAME + '$' + INNER_SIMPLE_NAME;
+
+  public static byte[] dump() throws Exception {
+
+    ClassWriter cw = new ClassWriter(0);
+    FieldVisitor fv;
+    AnnotationVisitor av0;
+
+    cw.visit(V1_8, ACC_PUBLIC + ACC_SUPER, INTERNAL_NAME, null, "java/lang/Object", null);
+
+    cw.visitSource(SIMPLE_NAME + ".java", null);
+
+    cw.visitInnerClass(INNER_INTERNAL_NAME, INTERNAL_NAME, INNER_SIMPLE_NAME, ACC_STATIC);
+
+    method0(cw);
+    method1(cw);
+    method2(cw);
+    nativeMethod(cw, "visitMethod", "()L" + INTERNAL_NAME + "$" + INNER_SIMPLE_NAME + ";");
+    nativeMethod(cw, "cond", "()Z");
+    nativeMethod(cw, "read", "(I)Ljava/lang/String;");
+    nativeMethod(cw, "count", "(I)I");
+    nativeMethod(cw, "count", "()I");
+    cw.visitEnd();
+
+    return cw.toByteArray();
+  }
+
+  private static void nativeMethod(ClassWriter cw, String name, String desc) {
+    MethodVisitor mv;
+    mv = cw.visitMethod(ACC_PRIVATE + ACC_NATIVE, name, desc, null, null);
+    mv.visitEnd();
+  }
+
+  private static void method0(ClassWriter cw) {
+    MethodVisitor mv = cw.visitMethod(ACC_PUBLIC, "<init>", "()V", null, null);
+    Label[] labels = new Label[2];
+    for (int i = 0; i < labels.length; i++) {
+      labels[i] = new Label();
+    }
+    mv.visitCode();
+    mv.visitLabel(labels[0]);
+    mv.visitLineNumber(6, labels[0]);
+    mv.visitVarInsn(ALOAD, 0);
+    mv.visitMethodInsn(INVOKESPECIAL, "java/lang/Object", "<init>", "()V", false);
+    mv.visitInsn(RETURN);
+    mv.visitLabel(labels[1]);
+    mv.visitLocalVariable("this", "L" + INTERNAL_NAME + ";", null, labels[0], labels[1], 0);
+    mv.visitMaxs(1, 1);
+    mv.visitEnd();
+  }
+
+  private static void method1(ClassWriter cw) {
+    MethodVisitor mv =
+        cw.visitMethod(ACC_PUBLIC + ACC_STATIC, "main", "([Ljava/lang/String;)V", null, null);
+    Label[] labels = new Label[4];
+    for (int i = 0; i < labels.length; i++) {
+      labels[i] = new Label();
+    }
+    mv.visitCode();
+    mv.visitLabel(labels[0]);
+    mv.visitLineNumber(18, labels[0]);
+    mv.visitLdcInsn(new Integer(42));
+    mv.visitVarInsn(ISTORE, 1);
+    mv.visitVarInsn(ALOAD, 0);
+    mv.visitInsn(ARRAYLENGTH);
+    mv.visitVarInsn(ILOAD, 1);
+    mv.visitJumpInsn(IF_ICMPLT, labels[1]);
+    mv.visitLabel(labels[2]);
+    mv.visitLineNumber(19, labels[2]);
+    mv.visitFieldInsn(GETSTATIC, "java/lang/System", "out", "Ljava/io/PrintStream;");
+    mv.visitVarInsn(ASTORE, 1);
+    mv.visitTypeInsn(NEW, INTERNAL_NAME);
+    mv.visitVarInsn(ASTORE, 2);
+    mv.visitVarInsn(ALOAD, 2);
+    mv.visitMethodInsn(INVOKESPECIAL, INTERNAL_NAME, "<init>", "()V", false);
+    mv.visitVarInsn(ALOAD, 0);
+    mv.visitInsn(ARRAYLENGTH);
+    mv.visitVarInsn(ISTORE, 3);
+    mv.visitVarInsn(ALOAD, 2);
+    mv.visitVarInsn(ILOAD, 3);
+    mv.visitMethodInsn(INVOKESPECIAL, INTERNAL_NAME, "readMethod", "(I)I", false);
+    mv.visitVarInsn(ISTORE, 2);
+    mv.visitVarInsn(ALOAD, 1);
+    mv.visitVarInsn(ILOAD, 2);
+    mv.visitMethodInsn(INVOKEVIRTUAL, "java/io/PrintStream", "println", "(I)V", false);
+    mv.visitLabel(labels[1]);
+    mv.visitLineNumber(21, labels[1]);
+    mv.visitFrame(Opcodes.F_SAME, 0, null, 0, null);
+    mv.visitInsn(RETURN);
+    mv.visitLabel(labels[3]);
+    mv.visitLocalVariable("args", "[Ljava/lang/String;", null, labels[0], labels[3], 0);
+    mv.visitMaxs(2, 4);
+    mv.visitEnd();
+  }
+
+  private static void method2(ClassWriter cw) {
+    MethodVisitor mv = cw.visitMethod(ACC_PRIVATE, "readMethod", "(I)I", null, null);
+    Label[] labels = new Label[31];
+    for (int i = 0; i < labels.length; i++) {
+      labels[i] = new Label();
+    }
+    mv.visitCode();
+    mv.visitLabel(labels[0]);
+    mv.visitLineNumber(24, labels[0]);
+    mv.visitLdcInsn(new Integer(6));
+    mv.visitInsn(POP);
+    mv.visitLdcInsn(new Integer(6));
+    mv.visitVarInsn(ISTORE, 2);
+    mv.visitVarInsn(ILOAD, 1);
+    mv.visitVarInsn(ILOAD, 2);
+    mv.visitInsn(IADD);
+    mv.visitVarInsn(ISTORE, 1);
+    mv.visitLabel(labels[1]);
+    mv.visitLineNumber(25, labels[1]);
+    mv.visitInsn(ICONST_0);
+    mv.visitVarInsn(ISTORE, 3);
+    mv.visitLabel(labels[2]);
+    mv.visitLineNumber(26, labels[2]);
+    mv.visitVarInsn(ALOAD, 0);
+    mv.visitVarInsn(ILOAD, 1);
+    mv.visitMethodInsn(INVOKESPECIAL, INTERNAL_NAME, "count", "(I)I", false);
+    mv.visitVarInsn(ISTORE, 4);
+    mv.visitVarInsn(ILOAD, 4);
+    mv.visitVarInsn(ILOAD, 1);
+    mv.visitVarInsn(ILOAD, 3);
+    mv.visitVarInsn(ISTORE, 4);
+    mv.visitVarInsn(ISTORE, 3);
+    mv.visitVarInsn(ISTORE, 1);
+    mv.visitLabel(labels[3]);
+    mv.visitFrame(
+        Opcodes.F_APPEND,
+        3,
+        new Object[] {Opcodes.INTEGER, Opcodes.INTEGER, Opcodes.INTEGER},
+        0,
+        null);
+    mv.visitVarInsn(ILOAD, 1);
+    mv.visitVarInsn(ISTORE, 1);
+    mv.visitVarInsn(ILOAD, 1);
+    mv.visitJumpInsn(IFLE, labels[4]);
+    mv.visitLabel(labels[5]);
+    mv.visitLineNumber(27, labels[5]);
+    mv.visitVarInsn(ALOAD, 0);
+    mv.visitVarInsn(ILOAD, 3);
+    mv.visitMethodInsn(INVOKESPECIAL, INTERNAL_NAME, "count", "(I)I", false);
+    mv.visitVarInsn(ISTORE, 4);
+    mv.visitLabel(labels[6]);
+    mv.visitLineNumber(28, labels[6]);
+    mv.visitVarInsn(ALOAD, 0);
+    mv.visitMethodInsn(INVOKESPECIAL, INTERNAL_NAME, "count", "()I", false);
+    mv.visitVarInsn(ISTORE, 5);
+    mv.visitVarInsn(ILOAD, 5);
+    mv.visitVarInsn(ILOAD, 4);
+    mv.visitVarInsn(ISTORE, 5);
+    mv.visitVarInsn(ISTORE, 4);
+    mv.visitLabel(labels[7]);
+    mv.visitFrame(Opcodes.F_APPEND, 1, new Object[] {Opcodes.INTEGER}, 0, null);
+    mv.visitVarInsn(ILOAD, 4);
+    mv.visitVarInsn(ISTORE, 4);
+    mv.visitVarInsn(ILOAD, 4);
+    mv.visitJumpInsn(IFLE, labels[8]);
+    mv.visitLabel(labels[9]);
+    mv.visitLineNumber(29, labels[9]);
+    mv.visitVarInsn(ALOAD, 0);
+    mv.visitVarInsn(ILOAD, 5);
+    mv.visitMethodInsn(INVOKESPECIAL, INTERNAL_NAME, "read", "(I)Ljava/lang/String;", false);
+    mv.visitInsn(POP);
+    mv.visitLabel(labels[10]);
+    mv.visitLineNumber(30, labels[10]);
+    mv.visitInsn(ICONST_2);
+    mv.visitInsn(POP);
+    mv.visitInsn(ICONST_2);
+    mv.visitVarInsn(ISTORE, 6);
+    mv.visitVarInsn(ILOAD, 5);
+    mv.visitVarInsn(ILOAD, 6);
+    mv.visitInsn(IADD);
+    mv.visitVarInsn(ISTORE, 5);
+    mv.visitLabel(labels[11]);
+    mv.visitLineNumber(28, labels[11]);
+    mv.visitInsn(ICONST_M1);
+    mv.visitInsn(POP);
+    mv.visitInsn(ICONST_M1);
+    mv.visitVarInsn(ISTORE, 6);
+    mv.visitVarInsn(ILOAD, 4);
+    mv.visitVarInsn(ILOAD, 6);
+    mv.visitInsn(IADD);
+    mv.visitVarInsn(ISTORE, 4);
+    mv.visitJumpInsn(GOTO, labels[7]);
+    mv.visitLabel(labels[8]);
+    mv.visitLineNumber(32, labels[8]);
+    mv.visitFrame(
+        Opcodes.F_FULL,
+        6,
+        new Object[] {
+          INTERNAL_NAME,
+          Opcodes.INTEGER,
+          Opcodes.INTEGER,
+          Opcodes.INTEGER,
+          Opcodes.TOP,
+          Opcodes.INTEGER
+        },
+        0,
+        new Object[] {});
+    mv.visitLdcInsn(new Integer(6));
+    mv.visitInsn(POP);
+    mv.visitInsn(ICONST_4);
+    mv.visitVarInsn(ISTORE, 4);
+    mv.visitVarInsn(ILOAD, 3);
+    mv.visitVarInsn(ILOAD, 4);
+    mv.visitInsn(IADD);
+    mv.visitVarInsn(ISTORE, 4);
+    mv.visitVarInsn(ALOAD, 0);
+    mv.visitVarInsn(ILOAD, 4);
+    mv.visitMethodInsn(INVOKESPECIAL, INTERNAL_NAME, "count", "(I)I", false);
+    mv.visitVarInsn(ISTORE, 4);
+    mv.visitVarInsn(ILOAD, 2);
+    mv.visitVarInsn(ILOAD, 4);
+    mv.visitInsn(IADD);
+    mv.visitVarInsn(ISTORE, 4);
+    mv.visitVarInsn(ILOAD, 3);
+    mv.visitVarInsn(ILOAD, 4);
+    mv.visitInsn(IADD);
+    mv.visitVarInsn(ISTORE, 3);
+    mv.visitLabel(labels[12]);
+    mv.visitLineNumber(26, labels[12]);
+    mv.visitInsn(ICONST_M1);
+    mv.visitInsn(POP);
+    mv.visitInsn(ICONST_M1);
+    mv.visitVarInsn(ISTORE, 4);
+    mv.visitVarInsn(ILOAD, 1);
+    mv.visitVarInsn(ILOAD, 4);
+    mv.visitInsn(IADD);
+    mv.visitVarInsn(ISTORE, 1);
+    mv.visitVarInsn(ILOAD, 5);
+    mv.visitVarInsn(ISTORE, 4);
+    mv.visitJumpInsn(GOTO, labels[3]);
+    mv.visitLabel(labels[4]);
+    mv.visitLineNumber(34, labels[4]);
+    mv.visitFrame(
+        Opcodes.F_FULL,
+        5,
+        new Object[] {INTERNAL_NAME, Opcodes.TOP, Opcodes.TOP, Opcodes.INTEGER, Opcodes.INTEGER},
+        0,
+        new Object[] {});
+    mv.visitInsn(ICONST_2);
+    mv.visitInsn(POP);
+    mv.visitInsn(ICONST_2);
+    mv.visitVarInsn(ISTORE, 1);
+    mv.visitVarInsn(ILOAD, 3);
+    mv.visitVarInsn(ILOAD, 1);
+    mv.visitInsn(IADD);
+    mv.visitVarInsn(ISTORE, 1);
+    mv.visitLabel(labels[13]);
+    mv.visitLineNumber(35, labels[13]);
+    mv.visitVarInsn(ALOAD, 0);
+    mv.visitMethodInsn(
+        INVOKESPECIAL,
+        INTERNAL_NAME,
+        "visitMethod",
+        "()L" + INTERNAL_NAME + "$" + INNER_SIMPLE_NAME + ";",
+        false);
+    mv.visitVarInsn(ASTORE, 2);
+    mv.visitLabel(labels[14]);
+    mv.visitLineNumber(36, labels[14]);
+    mv.visitVarInsn(ALOAD, 0);
+    mv.visitMethodInsn(INVOKESPECIAL, INTERNAL_NAME, "cond", "()Z", false);
+    mv.visitJumpInsn(IFEQ, labels[15]);
+    mv.visitVarInsn(ALOAD, 0);
+    mv.visitMethodInsn(INVOKESPECIAL, INTERNAL_NAME, "cond", "()Z", false);
+    mv.visitJumpInsn(IFEQ, labels[15]);
+    mv.visitVarInsn(ALOAD, 0);
+    mv.visitMethodInsn(INVOKESPECIAL, INTERNAL_NAME, "cond", "()Z", false);
+    mv.visitJumpInsn(IFEQ, labels[15]);
+    mv.visitLabel(labels[16]);
+    mv.visitLineNumber(37, labels[16]);
+    mv.visitVarInsn(ALOAD, 2);
+    mv.visitVarInsn(ASTORE, 3);
+    mv.visitLabel(labels[17]);
+    mv.visitLineNumber(38, labels[17]);
+    mv.visitInsn(ICONST_0);
+    mv.visitVarInsn(ISTORE, 5);
+    mv.visitLabel(labels[18]);
+    mv.visitLineNumber(39, labels[18]);
+    mv.visitVarInsn(ALOAD, 0);
+    mv.visitMethodInsn(INVOKESPECIAL, INTERNAL_NAME, "count", "()I", false);
+    mv.visitVarInsn(ISTORE, 6);
+    mv.visitVarInsn(ALOAD, 3);
+    mv.visitFieldInsn(GETFIELD, INNER_INTERNAL_NAME, "exceptionCount", "I");
+    mv.visitVarInsn(ISTORE, 7);
+    mv.visitVarInsn(ILOAD, 6);
+    mv.visitVarInsn(ILOAD, 7);
+    mv.visitJumpInsn(IF_ICMPNE, labels[19]);
+    mv.visitLabel(labels[20]);
+    mv.visitLineNumber(40, labels[20]);
+    mv.visitInsn(ICONST_1);
+    mv.visitVarInsn(ISTORE, 5);
+    mv.visitLabel(labels[21]);
+    mv.visitLineNumber(41, labels[21]);
+    mv.visitVarInsn(ALOAD, 0);
+    mv.visitMethodInsn(INVOKESPECIAL, INTERNAL_NAME, "count", "()I", false);
+    mv.visitVarInsn(ISTORE, 6);
+    mv.visitVarInsn(ILOAD, 6);
+    mv.visitVarInsn(ILOAD, 4);
+    mv.visitVarInsn(ISTORE, 6);
+    mv.visitVarInsn(ISTORE, 4);
+    mv.visitLabel(labels[22]);
+    mv.visitFrame(
+        Opcodes.F_FULL,
+        7,
+        new Object[] {
+          INTERNAL_NAME,
+          Opcodes.INTEGER,
+          INNER_INTERNAL_NAME,
+          INNER_INTERNAL_NAME,
+          Opcodes.INTEGER,
+          Opcodes.INTEGER,
+          Opcodes.INTEGER
+        },
+        0,
+        new Object[] {});
+    mv.visitVarInsn(ILOAD, 4);
+    mv.visitVarInsn(ISTORE, 4);
+    mv.visitVarInsn(ILOAD, 4);
+    mv.visitJumpInsn(IFLT, labels[23]);
+    mv.visitLabel(labels[24]);
+    mv.visitLineNumber(42, labels[24]);
+    mv.visitLdcInsn(new Integer(-2));
+    mv.visitVarInsn(ISTORE, 7);
+    mv.visitVarInsn(ILOAD, 6);
+    mv.visitVarInsn(ILOAD, 7);
+    mv.visitInsn(IADD);
+    mv.visitVarInsn(ISTORE, 6);
+    mv.visitLabel(labels[25]);
+    mv.visitLineNumber(41, labels[25]);
+    mv.visitInsn(ICONST_M1);
+    mv.visitInsn(POP);
+    mv.visitInsn(ICONST_M1);
+    mv.visitVarInsn(ISTORE, 7);
+    mv.visitVarInsn(ILOAD, 4);
+    mv.visitVarInsn(ILOAD, 7);
+    mv.visitInsn(IADD);
+    mv.visitVarInsn(ISTORE, 4);
+    mv.visitJumpInsn(GOTO, labels[22]);
+    mv.visitLabel(labels[23]);
+    mv.visitFrame(
+        Opcodes.F_FULL,
+        7,
+        new Object[] {
+          INTERNAL_NAME,
+          Opcodes.INTEGER,
+          INNER_INTERNAL_NAME,
+          INNER_INTERNAL_NAME,
+          Opcodes.TOP,
+          Opcodes.INTEGER,
+          Opcodes.INTEGER
+        },
+        0,
+        new Object[] {});
+    mv.visitVarInsn(ILOAD, 5);
+    mv.visitVarInsn(ILOAD, 6);
+    mv.visitVarInsn(ISTORE, 5);
+    mv.visitVarInsn(ISTORE, 4);
+    mv.visitJumpInsn(GOTO, labels[26]);
+    mv.visitLabel(labels[19]);
+    mv.visitFrame(
+        Opcodes.F_FULL,
+        6,
+        new Object[] {
+          INTERNAL_NAME,
+          Opcodes.INTEGER,
+          INNER_INTERNAL_NAME,
+          INNER_INTERNAL_NAME,
+          Opcodes.INTEGER,
+          Opcodes.INTEGER
+        },
+        0,
+        new Object[] {});
+    mv.visitVarInsn(ILOAD, 5);
+    mv.visitVarInsn(ILOAD, 4);
+    mv.visitVarInsn(ISTORE, 5);
+    mv.visitVarInsn(ISTORE, 4);
+    mv.visitLabel(labels[26]);
+    mv.visitLineNumber(45, labels[26]);
+    mv.visitFrame(Opcodes.F_SAME, 0, null, 0, null);
+    mv.visitVarInsn(ALOAD, 0);
+    mv.visitMethodInsn(INVOKESPECIAL, INTERNAL_NAME, "cond", "()Z", false);
+    mv.visitJumpInsn(IFEQ, labels[27]);
+    mv.visitLabel(labels[28]);
+    mv.visitLineNumber(46, labels[28]);
+    mv.visitVarInsn(ILOAD, 1);
+    mv.visitInsn(IRETURN);
+    mv.visitLabel(labels[27]);
+    mv.visitFrame(
+        Opcodes.F_FULL,
+        6,
+        new Object[] {
+          INTERNAL_NAME,
+          Opcodes.INTEGER,
+          INNER_INTERNAL_NAME,
+          Opcodes.TOP,
+          Opcodes.TOP,
+          Opcodes.INTEGER
+        },
+        0,
+        new Object[] {});
+    mv.visitVarInsn(ILOAD, 5);
+    mv.visitVarInsn(ISTORE, 3);
+    mv.visitJumpInsn(GOTO, labels[29]);
+    mv.visitLabel(labels[15]);
+    mv.visitFrame(
+        Opcodes.F_FULL,
+        5,
+        new Object[] {
+          INTERNAL_NAME, Opcodes.INTEGER, INNER_INTERNAL_NAME, Opcodes.TOP, Opcodes.INTEGER
+        },
+        0,
+        new Object[] {});
+    mv.visitVarInsn(ILOAD, 4);
+    mv.visitVarInsn(ISTORE, 3);
+    mv.visitLabel(labels[29]);
+    mv.visitLineNumber(49, labels[29]);
+    mv.visitFrame(
+        Opcodes.F_FULL,
+        4,
+        new Object[] {INTERNAL_NAME, Opcodes.INTEGER, INNER_INTERNAL_NAME, Opcodes.INTEGER},
+        0,
+        new Object[] {});
+    mv.visitVarInsn(ILOAD, 1);
+    mv.visitInsn(IRETURN);
+    mv.visitLabel(labels[30]);
+    mv.visitLocalVariable("u", "I", null, labels[0], labels[3], 1);
+    mv.visitLocalVariable("exception", "I", null, labels[2], labels[3], 3);
+    mv.visitLocalVariable("exception", "I", null, labels[3], labels[7], 4);
+    mv.visitLocalVariable("j", "I", null, labels[7], labels[8], 4);
+    mv.visitLocalVariable("i", "I", null, labels[3], labels[4], 1);
+    mv.visitLocalVariable("exception", "I", null, labels[7], labels[4], 5);
+    mv.visitLocalVariable("u", "I", null, labels[3], labels[13], 3);
+    mv.visitLocalVariable("exception", "I", null, labels[4], labels[22], 4);
+    mv.visitLocalVariable("j", "I", null, labels[22], labels[23], 4);
+    mv.visitLocalVariable("exception", "I", null, labels[22], labels[19], 6);
+    mv.visitLocalVariable("exception", "I", null, labels[19], labels[26], 4);
+    mv.visitLocalVariable("sameExceptions", "Z", null, labels[18], labels[26], 5);
+    mv.visitLocalVariable(
+        "mw", "L" + INTERNAL_NAME + "$" + INNER_SIMPLE_NAME + ";", null, labels[17], labels[27], 3);
+    mv.visitLocalVariable("sameExceptions", "Z", null, labels[26], labels[27], 4);
+    mv.visitLocalVariable("exception", "I", null, labels[26], labels[15], 5);
+    mv.visitLocalVariable("exception", "I", null, labels[15], labels[29], 4);
+    mv.visitLocalVariable("this", "L" + INTERNAL_NAME + ";", null, labels[0], labels[30], 0);
+    mv.visitLocalVariable("u", "I", null, labels[13], labels[30], 1);
+    mv.visitLocalVariable("exception", "I", null, labels[29], labels[30], 3);
+    mv.visitLocalVariable(
+        "mv", "L" + INTERNAL_NAME + "$" + INNER_SIMPLE_NAME + ";", null, labels[14], labels[30], 2);
+    mv.visitMaxs(3, 8);
+    mv.visitEnd();
+  }
+
+  public static byte[] dumpInner() throws Exception {
+
+    ClassWriter cw = new ClassWriter(0);
+    FieldVisitor fv;
+    MethodVisitor mv;
+    AnnotationVisitor av0;
+
+    cw.visit(V1_8, ACC_SUPER, INNER_INTERNAL_NAME, null, "java/lang/Object", null);
+
+    cw.visitSource(SIMPLE_NAME + ".java", null);
+
+    cw.visitInnerClass(INNER_INTERNAL_NAME, INTERNAL_NAME, INNER_SIMPLE_NAME, ACC_STATIC);
+
+    {
+      fv = cw.visitField(ACC_PUBLIC, "exceptionCount", "I", null, null);
+      fv.visitEnd();
+    }
+    {
+      mv = cw.visitMethod(0, "<init>", "()V", null, null);
+      mv.visitCode();
+      Label l0 = new Label();
+      mv.visitLabel(l0);
+      mv.visitLineNumber(13, l0);
+      mv.visitVarInsn(ALOAD, 0);
+      mv.visitMethodInsn(INVOKESPECIAL, "java/lang/Object", "<init>", "()V", false);
+      mv.visitInsn(RETURN);
+      Label l1 = new Label();
+      mv.visitLabel(l1);
+      mv.visitLocalVariable(
+          "this", "L" + INTERNAL_NAME + "$" + INNER_SIMPLE_NAME + ";", null, l0, l1, 0);
+      mv.visitMaxs(1, 1);
+      mv.visitEnd();
+    }
+    cw.visitEnd();
+
+    return cw.toByteArray();
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/ir/PhiDefinitionsTestRunner.java b/src/test/java/com/android/tools/r8/ir/PhiDefinitionsTestRunner.java
new file mode 100644
index 0000000..f9541e5
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/PhiDefinitionsTestRunner.java
@@ -0,0 +1,126 @@
+// Copyright (c) 2018, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.ir;
+
+import static org.junit.Assert.assertEquals;
+
+import com.android.tools.r8.ClassFileConsumer;
+import com.android.tools.r8.CompilationMode;
+import com.android.tools.r8.DexIndexedConsumer;
+import com.android.tools.r8.ProgramConsumer;
+import com.android.tools.r8.R8Command;
+import com.android.tools.r8.R8Command.Builder;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.ToolHelper.ProcessResult;
+import com.android.tools.r8.utils.DescriptorUtils;
+import java.io.IOException;
+import java.nio.file.Path;
+import java.nio.file.Paths;
+import org.junit.Test;
+
+public class PhiDefinitionsTestRunner extends TestBase {
+
+  private ProcessResult runInput;
+  private String className = PhiDefinitionsTest.class.getName();
+
+  private Path writeAndRunOriginal() throws IOException {
+    Path originalJar = temp.getRoot().toPath().resolve("originput.jar");
+    ClassFileConsumer consumer = new ClassFileConsumer.ArchiveConsumer(originalJar);
+    for (Class clazz : PhiDefinitionsTest.CLASSES) {
+      String descriptor = DescriptorUtils.javaTypeToDescriptor(clazz.getName());
+      consumer.accept(ToolHelper.getClassAsBytes(clazz), descriptor, null);
+    }
+    consumer.finished(null);
+    runOriginalJar(originalJar);
+    return originalJar;
+  }
+
+  private void runOriginalJar(Path originalJar) throws IOException {
+    runInput = ToolHelper.runJava(originalJar, className);
+    if (runInput.exitCode != 0) {
+      System.out.println(runInput);
+    }
+    assertEquals(0, runInput.exitCode);
+  }
+
+  private Path writeAndRunInputJar() throws Exception {
+    Path originalJar = writeAndRunOriginal();
+    Path inputJar = temp.getRoot().toPath().resolve("input.jar");
+    build(originalJar, new ClassFileConsumer.ArchiveConsumer(inputJar));
+    runCf(inputJar, className);
+    return inputJar;
+  }
+
+  private Path writeAndRunDumpJar() throws Exception {
+    Path dumpJar = temp.getRoot().toPath().resolve("dump.jar");
+    ClassFileConsumer consumer = new ClassFileConsumer.ArchiveConsumer(dumpJar);
+    String desc = 'L' + PhiDefinitionsTestDump.INTERNAL_NAME + ';';
+    consumer.accept(PhiDefinitionsTestDump.dump(), desc, null);
+    String innerDesc = 'L' + PhiDefinitionsTestDump.INNER_INTERNAL_NAME + ';';
+    consumer.accept(PhiDefinitionsTestDump.dumpInner(), innerDesc, null);
+    consumer.finished(null);
+    runOriginalJar(dumpJar);
+    return dumpJar;
+  }
+
+  @Test
+  public void testCf() throws Exception {
+    Path outCf = temp.getRoot().toPath().resolve("cf.zip");
+    build(writeAndRunInputJar(), new ClassFileConsumer.ArchiveConsumer(outCf));
+    runCf(outCf, className);
+  }
+
+  @Test
+  public void testDex() throws Exception {
+    Path outDex = temp.getRoot().toPath().resolve("dex.zip");
+    build(writeAndRunInputJar(), new DexIndexedConsumer.ArchiveConsumer(outDex));
+    runDex(outDex, className);
+  }
+
+  @Test
+  public void testCfDump() throws Exception {
+    Path outCf = temp.getRoot().toPath().resolve("dump-cf.zip");
+    build(writeAndRunDumpJar(), new ClassFileConsumer.ArchiveConsumer(outCf));
+    runCf(outCf, className);
+  }
+
+  @Test
+  public void testDexDump() throws Exception {
+    Path outDex = temp.getRoot().toPath().resolve("dump-dex.zip");
+    build(writeAndRunDumpJar(), new DexIndexedConsumer.ArchiveConsumer(outDex));
+    runDex(outDex, className);
+  }
+
+  private void runCf(Path outCf, String className) throws Exception {
+    ProcessResult runCf = ToolHelper.runJava(outCf, className);
+    assertEquals(runInput.toString(), runCf.toString());
+  }
+
+  private void runDex(Path outDex, String className) throws Exception {
+    ProcessResult runDex = ToolHelper.runArtNoVerificationErrorsRaw(outDex.toString(), className);
+    assertEquals(runInput.stdout, runDex.stdout);
+    assertEquals(runInput.exitCode, runDex.exitCode);
+  }
+
+  private void build(Path inputJar, ProgramConsumer consumer) throws Exception {
+    Builder builder =
+        R8Command.builder()
+            .setMode(CompilationMode.DEBUG)
+            .setProgramConsumer(consumer)
+            .addProgramFiles(inputJar);
+    if (consumer instanceof ClassFileConsumer) {
+      builder.addLibraryFiles(Paths.get(ToolHelper.JAVA_8_RUNTIME));
+    } else {
+      builder.addLibraryFiles(ToolHelper.getAndroidJar(ToolHelper.getMinApiLevelForDexVm()));
+    }
+    // TODO(b/75997473): Enable inlining when supported by CF backend
+    ToolHelper.runR8(
+        builder.build(),
+        options -> {
+          options.enableInlining = false;
+          options.invalidDebugInfoFatal = true;
+        });
+  }
+}