diff --git a/src/main/java/com/android/tools/r8/cf/code/CfGoto.java b/src/main/java/com/android/tools/r8/cf/code/CfGoto.java
new file mode 100644
index 0000000..2207e6f
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/cf/code/CfGoto.java
@@ -0,0 +1,21 @@
+// 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.cf.code;
+
+import org.objectweb.asm.MethodVisitor;
+import org.objectweb.asm.Opcodes;
+
+public class CfGoto extends CfInstruction {
+
+  private final CfLabel target;
+
+  public CfGoto(CfLabel target) {
+    this.target = target;
+  }
+
+  @Override
+  public void write(MethodVisitor visitor) {
+    visitor.visitJumpInsn(Opcodes.GOTO, target.getLabel());
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/cf/code/CfIf.java b/src/main/java/com/android/tools/r8/cf/code/CfIf.java
new file mode 100644
index 0000000..b8397e5
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/cf/code/CfIf.java
@@ -0,0 +1,47 @@
+// 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.cf.code;
+
+import com.android.tools.r8.errors.Unreachable;
+import com.android.tools.r8.ir.code.If;
+import com.android.tools.r8.ir.code.ValueType;
+import org.objectweb.asm.MethodVisitor;
+import org.objectweb.asm.Opcodes;
+
+public class CfIf extends CfInstruction {
+
+  private final If.Type kind;
+  private final ValueType type;
+  private final CfLabel target;
+
+  public CfIf(If.Type kind, ValueType type, CfLabel target) {
+    this.kind = kind;
+    this.type = type;
+    this.target = target;
+  }
+
+  private int getOpcode() {
+    switch (kind) {
+      case EQ:
+        return type.isObject() ? Opcodes.IFNULL : Opcodes.IFEQ;
+      case GE:
+        return Opcodes.IFGE;
+      case GT:
+        return Opcodes.IFGT;
+      case LE:
+        return Opcodes.IFLE;
+      case LT:
+        return Opcodes.IFLT;
+      case NE:
+        return type.isObject() ? Opcodes.IFNONNULL : Opcodes.IFNE;
+      default:
+        throw new Unreachable("Unexpected type " + type);
+    }
+  }
+
+  @Override
+  public void write(MethodVisitor visitor) {
+    visitor.visitJumpInsn(getOpcode(), target.getLabel());
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/cf/code/CfLabel.java b/src/main/java/com/android/tools/r8/cf/code/CfLabel.java
new file mode 100644
index 0000000..9c6560d
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/cf/code/CfLabel.java
@@ -0,0 +1,24 @@
+// 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.cf.code;
+
+import org.objectweb.asm.Label;
+import org.objectweb.asm.MethodVisitor;
+
+public class CfLabel extends CfInstruction {
+
+  private Label label = null;
+
+  public Label getLabel() {
+    if (label == null) {
+      label = new Label();
+    }
+    return label;
+  }
+
+  @Override
+  public void write(MethodVisitor visitor) {
+    visitor.visitLabel(getLabel());
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/cf/code/CfTryCatch.java b/src/main/java/com/android/tools/r8/cf/code/CfTryCatch.java
new file mode 100644
index 0000000..a0d1f6a
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/cf/code/CfTryCatch.java
@@ -0,0 +1,32 @@
+// 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.cf.code;
+
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.code.BasicBlock;
+import com.android.tools.r8.ir.code.CatchHandlers;
+import com.android.tools.r8.ir.conversion.CfBuilder;
+import java.util.ArrayList;
+import java.util.List;
+
+public class CfTryCatch {
+  public final CfLabel start;
+  public final CfLabel end;
+  public final List<DexType> guards;
+  public final List<CfLabel> targets;
+
+  public CfTryCatch(
+      CfLabel start,
+      CfLabel end,
+      CatchHandlers<BasicBlock> handlers,
+      CfBuilder builder) {
+    this.start = start;
+    this.end = end;
+    guards = handlers.getGuards();
+    targets = new ArrayList<>(handlers.getAllTargets().size());
+    for (BasicBlock block : handlers.getAllTargets()) {
+      targets.add(builder.getLabel(block));
+    }
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/code/ConstClass.java b/src/main/java/com/android/tools/r8/code/ConstClass.java
index ef8b257..f140022 100644
--- a/src/main/java/com/android/tools/r8/code/ConstClass.java
+++ b/src/main/java/com/android/tools/r8/code/ConstClass.java
@@ -39,7 +39,7 @@
 
   @Override
   public void registerUse(UseRegistry registry) {
-    registry.registerConstClass(getType());
+    registry.registerTypeReference(getType());
   }
 
   public DexType getType() {
diff --git a/src/main/java/com/android/tools/r8/graph/AppInfoWithSubtyping.java b/src/main/java/com/android/tools/r8/graph/AppInfoWithSubtyping.java
index a2caf1d..ad0f549 100644
--- a/src/main/java/com/android/tools/r8/graph/AppInfoWithSubtyping.java
+++ b/src/main/java/com/android/tools/r8/graph/AppInfoWithSubtyping.java
@@ -84,6 +84,9 @@
         populateSuperType(map, inter, baseClass, definitions);
         inter.addInterfaceSubtype(holder);
       }
+      if (holderClass.isInterface()) {
+        holder.tagAsInteface();
+      }
     } else {
       if (!baseClass.isLibraryClass()) {
         missingClasses.add(holder);
@@ -193,18 +196,28 @@
     return holder.accessFlags.isAbstract();
   }
 
+  private boolean holderIsInterface(Descriptor<?, ?> desc) {
+    DexClass holder = definitionFor(desc.getHolder());
+    return holder.accessFlags.isInterface();
+  }
+
   // For mapping invoke interface instruction to target methods.
   public Set<DexEncodedMethod> lookupInterfaceTargets(DexMethod method) {
-    Set<DexEncodedMethod> result = new HashSet<>();
     Set<DexType> set = subtypes(method.holder);
-    if (set != null) {
-      for (DexType type : set) {
-        DexClass clazz = definitionFor(type);
-        if (!clazz.isInterface()) {
-          DexEncodedMethod targetMethod = lookupVirtualTarget(type, method);
-          if (targetMethod != null) {
-            result.add(targetMethod);
-          }
+    if (set == null) {
+      return Collections.emptySet();
+    }
+    assert holderIsInterface(method);
+    Set<DexEncodedMethod> result = new HashSet<>();
+    for (DexType type : set) {
+      DexClass clazz = definitionFor(type);
+      // Default methods are looked up when looking at a specific subtype that does not
+      // override them, so we ignore interfaces here. Otherwise, we would look up default methods
+      // that are factually never used.
+      if (!clazz.isInterface()) {
+        DexEncodedMethod targetMethod = lookupVirtualTarget(type, method);
+        if (targetMethod != null) {
+          result.add(targetMethod);
         }
       }
     }
@@ -212,9 +225,8 @@
   }
 
   public DexEncodedMethod lookupSingleInterfaceTarget(DexMethod method) {
-    assert method != null;
     DexClass holder = definitionFor(method.holder);
-    if ((holder == null) || holder.isLibraryClass()) {
+    if ((holder == null) || holder.isLibraryClass() || !holder.accessFlags.isInterface()) {
       return null;
     }
     DexEncodedMethod result = null;
@@ -222,6 +234,9 @@
     if (set != null) {
       for (DexType type : set) {
         DexClass clazz = definitionFor(type);
+        // Default methods are looked up when looking at a specific subtype that does not
+        // override them, so we ignore interfaces here. Otherwise, we would look up default methods
+        // that are factually never used.
         if (!clazz.isInterface()) {
           DexEncodedMethod t = lookupVirtualTarget(type, method);
           if (t != null) {
diff --git a/src/main/java/com/android/tools/r8/graph/CfCode.java b/src/main/java/com/android/tools/r8/graph/CfCode.java
index e1f9c63..7c76969 100644
--- a/src/main/java/com/android/tools/r8/graph/CfCode.java
+++ b/src/main/java/com/android/tools/r8/graph/CfCode.java
@@ -5,23 +5,32 @@
 
 import com.android.tools.r8.ApiLevelException;
 import com.android.tools.r8.cf.code.CfInstruction;
+import com.android.tools.r8.cf.code.CfTryCatch;
 import com.android.tools.r8.errors.Unimplemented;
 import com.android.tools.r8.ir.code.IRCode;
 import com.android.tools.r8.naming.ClassNameMapper;
 import com.android.tools.r8.utils.InternalOptions;
 import java.util.List;
+import org.objectweb.asm.Label;
 import org.objectweb.asm.MethodVisitor;
+import org.objectweb.asm.Type;
 
 public class CfCode extends Code {
 
   private final int maxStack;
   private final int maxLocals;
   private final List<CfInstruction> instructions;
+  private final List<CfTryCatch> tryCatchRanges;
 
-  public CfCode(int maxStack, int maxLocals, List<CfInstruction> instructions) {
+  public CfCode(
+      int maxStack,
+      int maxLocals,
+      List<CfInstruction> instructions,
+      List<CfTryCatch> tryCatchRanges) {
     this.maxStack = maxStack;
     this.maxLocals = maxLocals;
     this.instructions = instructions;
+    this.tryCatchRanges = tryCatchRanges;
   }
 
   @Override
@@ -40,6 +49,21 @@
     }
     visitor.visitEnd();
     visitor.visitMaxs(maxStack, maxLocals);
+    for (CfTryCatch tryCatch : tryCatchRanges) {
+      Label start = tryCatch.start.getLabel();
+      Label end = tryCatch.end.getLabel();
+      for (int i = 0; i < tryCatch.guards.size(); i++) {
+        DexType guard = tryCatch.guards.get(i);
+        Label target = tryCatch.targets.get(i).getLabel();
+        visitor.visitTryCatchBlock(
+            start,
+            end,
+            target,
+            guard == DexItemFactory.catchAllType
+                ? null
+                : Type.getType(guard.toDescriptorString()).getInternalName());
+      }
+    }
   }
 
   @Override
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 5aaf308..d4deb54 100644
--- a/src/main/java/com/android/tools/r8/graph/DexType.java
+++ b/src/main/java/com/android/tools/r8/graph/DexType.java
@@ -71,23 +71,27 @@
     }
   }
 
-  public void addDirectSubtype(DexType type) {
+  void addDirectSubtype(DexType type) {
     assert hierarchyLevel != UNKNOWN_LEVEL;
     ensureDirectSubTypeSet();
     directSubtypes.add(type);
     type.setLevel(hierarchyLevel + 1);
   }
 
-  public void tagAsSubtypeRoot() {
+  void tagAsSubtypeRoot() {
     setLevel(ROOT_LEVEL);
   }
 
+  void tagAsInteface() {
+    setLevel(INTERFACE_LEVEL);
+  }
+
   public boolean isInterface() {
     assert isClassType() && hierarchyLevel != UNKNOWN_LEVEL;
     return hierarchyLevel == INTERFACE_LEVEL;
   }
 
-  public void addInterfaceSubtype(DexType type) {
+  void addInterfaceSubtype(DexType type) {
     // Interfaces all inherit from java.lang.Object. However, we assign a special level to
     // identify them later on.
     setLevel(INTERFACE_LEVEL);
@@ -156,7 +160,7 @@
 
   /**
    * Apply the given function to all classes that directly extend this class.
-   *
+   * <p>
    * If this class is an interface, then this method will visit all sub-interfaces. This deviates
    * from the dex-file encoding, where subinterfaces "implement" their super interfaces. However,
    * it is consistent with the source language.
@@ -185,7 +189,7 @@
 
   /**
    * Apply the given function to all classes that directly implement this interface.
-   *
+   * <p>
    * The implementation does not consider how the hierarchy is encoded in the dex file, where
    * interfaces "implement" their super interfaces. Instead it takes the view of the source
    * language, where interfaces "extend" their superinterface.
diff --git a/src/main/java/com/android/tools/r8/graph/UseRegistry.java b/src/main/java/com/android/tools/r8/graph/UseRegistry.java
index f6736fa..78b2f56 100644
--- a/src/main/java/com/android/tools/r8/graph/UseRegistry.java
+++ b/src/main/java/com/android/tools/r8/graph/UseRegistry.java
@@ -65,8 +65,4 @@
         throw new AssertionError();
     }
   }
-
-  public boolean registerConstClass(DexType type) {
-    return registerTypeReference(type);
-  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Goto.java b/src/main/java/com/android/tools/r8/ir/code/Goto.java
index eef666b..4b88706 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Goto.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Goto.java
@@ -3,6 +3,9 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.code;
 
+import com.android.tools.r8.cf.code.CfGoto;
+import com.android.tools.r8.ir.conversion.CfBuilder;
+import com.android.tools.r8.ir.conversion.CfBuilder.StackHelper;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.utils.CfgPrinter;
 import java.util.List;
@@ -94,4 +97,14 @@
   public Goto asGoto() {
     return this;
   }
+
+  @Override
+  public void insertLoadAndStores(InstructionListIterator it, StackHelper stack) {
+    // Nothing to do.
+  }
+
+  @Override
+  public void buildCf(CfBuilder builder) {
+    builder.add(new CfGoto(builder.getLabel(getTarget())));
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/IRCode.java b/src/main/java/com/android/tools/r8/ir/code/IRCode.java
index 95dd4ba..934d3db 100644
--- a/src/main/java/com/android/tools/r8/ir/code/IRCode.java
+++ b/src/main/java/com/android/tools/r8/ir/code/IRCode.java
@@ -402,7 +402,8 @@
             assert instruction.isDebugInstruction()
                 || instruction.isJumpInstruction()
                 || instruction.isConstInstruction()
-                || instruction.isNewArrayFilledData();
+                || instruction.isNewArrayFilledData()
+                || instruction.isStore();
           }
         }
       }
diff --git a/src/main/java/com/android/tools/r8/ir/code/If.java b/src/main/java/com/android/tools/r8/ir/code/If.java
index d2e16f6..8cdf209 100644
--- a/src/main/java/com/android/tools/r8/ir/code/If.java
+++ b/src/main/java/com/android/tools/r8/ir/code/If.java
@@ -6,7 +6,10 @@
 import static com.android.tools.r8.dex.Constants.U4BIT_MAX;
 import static com.android.tools.r8.dex.Constants.U8BIT_MAX;
 
+import com.android.tools.r8.cf.code.CfIf;
 import com.android.tools.r8.errors.Unreachable;
+import com.android.tools.r8.ir.conversion.CfBuilder;
+import com.android.tools.r8.ir.conversion.CfBuilder.StackHelper;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.utils.CfgPrinter;
 import java.util.List;
@@ -186,4 +189,15 @@
   public If asIf() {
     return this;
   }
+
+  @Override
+  public void insertLoadAndStores(InstructionListIterator it, StackHelper stack) {
+    stack.loadInValues(this, it);
+  }
+
+  @Override
+  public void buildCf(CfBuilder builder) {
+    assert inValues.size() == 1;
+    builder.add(new CfIf(type, inValues.get(0).type, builder.getLabel(getTrueTarget())));
+  }
 }
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 cdcf070..eeee6f8 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
@@ -938,6 +938,22 @@
     return null;
   }
 
+  public boolean isStore() {
+    return false;
+  }
+
+  public Store asStore() {
+    return null;
+  }
+
+  public boolean isLoad() {
+    return false;
+  }
+
+  public Load asLoad() {
+    return null;
+  }
+
   public boolean canBeFolded() {
     return false;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Load.java b/src/main/java/com/android/tools/r8/ir/code/Load.java
index 734b2dd..401a880 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Load.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Load.java
@@ -8,6 +8,7 @@
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.ir.conversion.CfBuilder;
+import com.android.tools.r8.ir.conversion.CfBuilder.StackHelper;
 import com.android.tools.r8.ir.optimize.Inliner.Constraint;
 
 public class Load extends Instruction {
@@ -17,6 +18,16 @@
   }
 
   @Override
+  public boolean isLoad() {
+    return true;
+  }
+
+  @Override
+  public Load asLoad() {
+    return this;
+  }
+
+  @Override
   public boolean identicalNonValueNonPositionParts(Instruction other) {
     return true;
   }
@@ -46,4 +57,9 @@
     Value value = inValues.get(0);
     builder.add(new CfLoad(value.outType(), builder.getLocalRegister(value)));
   }
+
+  @Override
+  public void insertLoadAndStores(InstructionListIterator it, StackHelper stack) {
+    // Nothing to do. This is only hit because loads and stores are insert for phis.
+  }
 }
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 0f72182..2b419fd 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
@@ -6,6 +6,8 @@
 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.conversion.CfBuilder;
+import com.android.tools.r8.ir.conversion.CfBuilder.StackHelper;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.Constraint;
 import com.android.tools.r8.utils.InternalOptions;
@@ -61,7 +63,7 @@
 
   @Override
   public boolean canBeDeadCode(IRCode code, InternalOptions options) {
-    return !options.debug;
+    return !options.debug && !options.outputClassFiles;
   }
 
   @Override
@@ -69,4 +71,18 @@
     // TODO(64432527): Revisit this constraint.
     return Constraint.NEVER;
   }
+
+  @Override
+  public void insertLoadAndStores(InstructionListIterator it, StackHelper stack) {
+    if (outValue.isUsed()) {
+      stack.storeOutValue(this, it);
+    } else {
+      stack.popOutValue(outValue.type, this, it);
+    }
+  }
+
+  @Override
+  public void buildCf(CfBuilder builder) {
+    // Nothing to do. The exception is implicitly pushed on the stack.
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Pop.java b/src/main/java/com/android/tools/r8/ir/code/Pop.java
index 33d5557..7dd62ae 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Pop.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Pop.java
@@ -9,6 +9,7 @@
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.Constraint;
+import com.android.tools.r8.utils.InternalOptions;
 
 public class Pop extends Instruction {
 
@@ -45,4 +46,10 @@
   public void buildCf(CfBuilder builder) {
     builder.add(new CfPop(inValues.get(0).type));
   }
+
+  @Override
+  public boolean canBeDeadCode(IRCode code, InternalOptions options) {
+    // Pop cannot be dead code as it modifies the stack height.
+    return false;
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/StackValue.java b/src/main/java/com/android/tools/r8/ir/code/StackValue.java
index f670621..3bf1417 100644
--- a/src/main/java/com/android/tools/r8/ir/code/StackValue.java
+++ b/src/main/java/com/android/tools/r8/ir/code/StackValue.java
@@ -5,12 +5,16 @@
 
 public class StackValue extends Value {
 
-  public StackValue(ValueType type) {
+  private final int height;
+
+  public StackValue(ValueType type, int height) {
     super(Value.UNDEFINED_NUMBER, type, null);
+    this.height = height;
+    assert height >= 0;
   }
 
   @Override
   public String toString() {
-    return "s";
+    return "s" + height;
   }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Store.java b/src/main/java/com/android/tools/r8/ir/code/Store.java
index ddc4f50..bc1e419 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Store.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Store.java
@@ -8,7 +8,10 @@
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.ir.conversion.CfBuilder;
+import com.android.tools.r8.ir.conversion.CfBuilder.FixedLocal;
+import com.android.tools.r8.ir.conversion.CfBuilder.StackHelper;
 import com.android.tools.r8.ir.optimize.Inliner.Constraint;
+import com.android.tools.r8.utils.InternalOptions;
 
 public class Store extends Instruction {
 
@@ -17,6 +20,16 @@
   }
 
   @Override
+  public boolean isStore() {
+    return true;
+  }
+
+  @Override
+  public Store asStore() {
+    return this;
+  }
+
+  @Override
   public boolean identicalNonValueNonPositionParts(Instruction other) {
     return true;
   }
@@ -45,4 +58,14 @@
   public void buildCf(CfBuilder builder) {
     builder.add(new CfStore(outType(), builder.getLocalRegister(outValue)));
   }
+
+  @Override
+  public void insertLoadAndStores(InstructionListIterator it, StackHelper stack) {
+    // Nothing to do. This is only hit because loads and stores are insert for phis.
+  }
+
+  @Override
+  public boolean canBeDeadCode(IRCode code, InternalOptions options) {
+    return !(outValue instanceof FixedLocal);
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/CfBuilder.java b/src/main/java/com/android/tools/r8/ir/conversion/CfBuilder.java
index aed20acb..f07b61e 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/CfBuilder.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/CfBuilder.java
@@ -4,6 +4,8 @@
 package com.android.tools.r8.ir.conversion;
 
 import com.android.tools.r8.cf.code.CfInstruction;
+import com.android.tools.r8.cf.code.CfLabel;
+import com.android.tools.r8.cf.code.CfTryCatch;
 import com.android.tools.r8.errors.Unimplemented;
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.CfCode;
@@ -11,6 +13,7 @@
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.ir.code.Argument;
 import com.android.tools.r8.ir.code.BasicBlock;
+import com.android.tools.r8.ir.code.CatchHandlers;
 import com.android.tools.r8.ir.code.ConstClass;
 import com.android.tools.r8.ir.code.ConstInstruction;
 import com.android.tools.r8.ir.code.ConstNumber;
@@ -20,7 +23,9 @@
 import com.android.tools.r8.ir.code.InstructionIterator;
 import com.android.tools.r8.ir.code.InstructionListIterator;
 import com.android.tools.r8.ir.code.Load;
+import com.android.tools.r8.ir.code.Phi;
 import com.android.tools.r8.ir.code.Pop;
+import com.android.tools.r8.ir.code.Position;
 import com.android.tools.r8.ir.code.StackValue;
 import com.android.tools.r8.ir.code.Store;
 import com.android.tools.r8.ir.code.Value;
@@ -28,43 +33,64 @@
 import com.android.tools.r8.ir.optimize.CodeRewriter;
 import com.android.tools.r8.ir.optimize.DeadCodeRemover;
 import com.android.tools.r8.utils.InternalOptions;
-import it.unimi.dsi.fastutil.objects.Reference2IntArrayMap;
 import it.unimi.dsi.fastutil.objects.Reference2IntMap;
+import it.unimi.dsi.fastutil.objects.Reference2IntOpenHashMap;
 import java.util.ArrayList;
+import java.util.HashMap;
 import java.util.Iterator;
 import java.util.List;
+import java.util.ListIterator;
+import java.util.Map;
 
 public class CfBuilder {
 
   private final DexEncodedMethod method;
   private final IRCode code;
+
+  private int maxLocals = -1;
+  private int maxStack = 0;
+  private int currentStack = 0;
   private List<CfInstruction> instructions;
-  private Reference2IntMap<Value> argumentRegisters;
-  private int maxLocals;
+  private Reference2IntMap<Value> registers;
+  private Map<BasicBlock, CfLabel> labels;
+
+  /**
+   * Value that represents a shared physical location defined by the phi value.
+   *
+   * This value is introduced to represent the store instructions used to unify the location of
+   * in-flowing values to phi's. After introducing this fixed location the graph is no longer in
+   * SSA since the fixed location signifies a place that can be written to from multiple places.
+   */
+  public static class FixedLocal extends Value {
+
+    private final Phi phi;
+
+    public FixedLocal(Phi phi) {
+      super(phi.getNumber(), phi.outType(), phi.getLocalInfo());
+      this.phi = phi;
+    }
+
+    @Override
+    public boolean isConstant() {
+      return false;
+    }
+
+    @Override
+    public String toString() {
+      return "fixed:v" + phi.getNumber();
+    }
+  }
 
   public static class StackHelper {
 
+    private int currentStackHeight = 0;
+
     public void loadInValues(Instruction instruction, InstructionListIterator it) {
+      int topOfStack = currentStackHeight;
       it.previous();
-      for (int i = 0; i < instruction.inValues().size(); i++) {
-        Value value = instruction.inValues().get(i);
-        StackValue stackValue = new StackValue(value.outType());
-        Instruction load;
-        if (value.isConstant()) {
-          ConstInstruction constant = value.getConstInstruction();
-          if (constant.isConstNumber()) {
-            load = new ConstNumber(stackValue, constant.asConstNumber().getRawValue());
-          } else if (constant.isConstString()) {
-            load = new ConstString(stackValue, constant.asConstString().getValue());
-          } else if (constant.isConstClass()) {
-            load = new ConstClass(stackValue, constant.asConstClass().getValue());
-          } else {
-            throw new Unreachable("Unexpected constant value: " + value);
-          }
-        } else {
-          load = new Load(stackValue, value);
-        }
-        add(load, instruction, it);
+      for (Value value : instruction.inValues()) {
+        StackValue stackValue = new StackValue(value.outType(), topOfStack++);
+        add(load(stackValue, value), instruction, it);
         value.removeUser(instruction);
         instruction.replaceValue(value, stackValue);
       }
@@ -72,26 +98,61 @@
     }
 
     public void storeOutValue(Instruction instruction, InstructionListIterator it) {
-      if (instruction.isOutConstant()) {
+      if (instruction.outValue() instanceof StackValue) {
+        assert instruction.isConstInstruction();
         return;
       }
-      StackValue newOutValue = new StackValue(instruction.outType());
+      StackValue newOutValue = new StackValue(instruction.outType(), currentStackHeight);
       Value oldOutValue = instruction.swapOutValue(newOutValue);
       add(new Store(oldOutValue, newOutValue), instruction, it);
     }
 
     public void popOutValue(ValueType type, Instruction instruction, InstructionListIterator it) {
-      StackValue newOutValue = new StackValue(type);
+      StackValue newOutValue = new StackValue(type, currentStackHeight);
       instruction.swapOutValue(newOutValue);
       add(new Pop(newOutValue), instruction, it);
     }
 
+    public void movePhi(Phi phi, Value value, InstructionListIterator it) {
+      StackValue tmp = new StackValue(phi.outType(), currentStackHeight);
+      FixedLocal out = new FixedLocal(phi);
+      add(load(tmp, value), phi.getBlock(), Position.none(), it);
+      add(new Store(out, tmp), phi.getBlock(), Position.none(), it);
+      value.removePhiUser(phi);
+      phi.replaceUsers(out);
+    }
+
+    private Instruction load(StackValue stackValue, Value value) {
+      if (value.isConstant()) {
+        ConstInstruction constant = value.getConstInstruction();
+        if (constant.isConstNumber()) {
+          return new ConstNumber(stackValue, constant.asConstNumber().getRawValue());
+        } else if (constant.isConstString()) {
+          return new ConstString(stackValue, constant.asConstString().getValue());
+        } else if (constant.isConstClass()) {
+          return new ConstClass(stackValue, constant.asConstClass().getValue());
+        } else {
+          throw new Unreachable("Unexpected constant value: " + value);
+        }
+      }
+      return new Load(stackValue, value);
+    }
+
     private static void add(
         Instruction newInstruction, Instruction existingInstruction, InstructionListIterator it) {
-      newInstruction.setBlock(existingInstruction.getBlock());
-      newInstruction.setPosition(existingInstruction.getPosition());
+      add(newInstruction, existingInstruction.getBlock(), existingInstruction.getPosition(), it);
+    }
+
+    private static void add(
+        Instruction newInstruction,
+        BasicBlock block,
+        Position position,
+        InstructionListIterator it) {
+      newInstruction.setBlock(block);
+      newInstruction.setPosition(position);
       it.add(newInstruction);
     }
+
   }
 
   public CfBuilder(DexEncodedMethod method, IRCode code) {
@@ -101,6 +162,7 @@
 
   public Code build(CodeRewriter rewriter, InternalOptions options) {
     try {
+      splitExceptionalBlocks();
       loadStoreInsertion();
       DeadCodeRemover.removeDeadCode(code, rewriter, options);
       removeUnneededLoadsAndStores();
@@ -113,8 +175,55 @@
     }
   }
 
+  // Split all blocks with throwing instructions and exceptional edges such that any non-throwing
+  // instructions that might define values prior to the throwing exception are excluded from the
+  // try-catch range. Failure to do so will result in code that does not verify on the JVM.
+  private void splitExceptionalBlocks() {
+    ListIterator<BasicBlock> it = code.listIterator();
+    while (it.hasNext()) {
+      BasicBlock block = it.next();
+      if (!block.hasCatchHandlers()) {
+        continue;
+      }
+      int size = block.getInstructions().size();
+      boolean isThrow = block.exit().isThrow();
+      if ((isThrow && size == 1) || (!isThrow && size == 2)) {
+        // Fast-path to avoid processing blocks with just a single throwing instruction.
+        continue;
+      }
+      InstructionListIterator instructions = block.listIterator();
+      boolean hasOutValues = false;
+      while (instructions.hasNext()) {
+        Instruction instruction = instructions.next();
+        if (instruction.instructionTypeCanThrow()) {
+          break;
+        }
+        hasOutValues |= instruction.outValue() != null;
+      }
+      if (hasOutValues) {
+        instructions.previous();
+        instructions.split(code, it);
+      }
+    }
+  }
+
   private void loadStoreInsertion() {
     StackHelper stack = new StackHelper();
+    // Insert phi stores in all predecessors.
+    for (BasicBlock block : code.blocks) {
+      if (!block.getPhis().isEmpty()) {
+        for (int predIndex = 0; predIndex < block.getPredecessors().size(); predIndex++) {
+          BasicBlock pred = block.getPredecessors().get(predIndex);
+          for (Phi phi : block.getPhis()) {
+            Value value = phi.getOperand(predIndex);
+            InstructionListIterator it = pred.listIterator(pred.getInstructions().size());
+            it.previous();
+            stack.movePhi(phi, value, it);
+          }
+        }
+      }
+    }
+    // Insert per-instruction loads and stores.
     for (BasicBlock block : code.blocks) {
       InstructionListIterator it = block.listIterator();
       while (it.hasNext()) {
@@ -131,6 +240,10 @@
       InstructionListIterator it = block.listIterator();
       while (it.hasNext()) {
         Instruction store = it.next();
+        // Eliminate unneeded loads of stores:
+        //  v <- store si
+        //  si <- load v
+        // where |users(v)| == 1 (ie, the load is the only user)
         if (store instanceof Store && store.outValue().numberOfAllUsers() == 1) {
           Instruction load = it.peekNext();
           if (load instanceof Load && load.inValues().get(0) == store.outValue()) {
@@ -154,60 +267,115 @@
   private void allocateLocalRegisters() {
     // TODO(zerny): Allocate locals based on live ranges.
     InstructionIterator it = code.instructionIterator();
-    argumentRegisters = new Reference2IntArrayMap<>(
-        method.method.proto.parameters.values.length + (method.accessFlags.isStrict() ? 0 : 1));
-    int argumentRegister = 0;
-    int maxRegister = -1;
+    registers = new Reference2IntOpenHashMap<>();
+    int nextFreeRegister = 0;
     while (it.hasNext()) {
       Instruction instruction = it.next();
-      if (instruction.isArgument()) {
-        argumentRegisters.put(instruction.outValue(), argumentRegister);
-        argumentRegister += instruction.outValue().requiredRegisters();
-        maxRegister = argumentRegister - 1;
-      } else if (instruction.outValue() != null
-          && !(instruction.outValue() instanceof StackValue)) {
-        maxRegister = Math.max(maxRegister, 2 * instruction.outValue().getNumber());
+      Value outValue = instruction.outValue();
+      if (outValue instanceof FixedLocal) {
+        // Phi stores are marked by a "fixed-local" value which share the same local index.
+        FixedLocal fixed = (FixedLocal) outValue;
+        if (!registers.containsKey(fixed.phi)) {
+          registers.put(fixed.phi, nextFreeRegister);
+          nextFreeRegister += fixed.requiredRegisters();
+        }
+      } else if (outValue != null && !(outValue instanceof StackValue)) {
+        registers.put(instruction.outValue(), nextFreeRegister);
+        nextFreeRegister += instruction.outValue().requiredRegisters();
       }
     }
-    maxLocals = maxRegister + 1;
+    maxLocals = nextFreeRegister;
+  }
+
+  private void push(Value value) {
+    assert value instanceof StackValue;
+    currentStack += value.requiredRegisters();
+    maxStack = Math.max(maxStack, currentStack);
+  }
+
+  private void pop(Value value) {
+    assert value instanceof StackValue;
+    currentStack -= value.requiredRegisters();
   }
 
   private CfCode buildCfCode() {
-    int maxStack = 0;
-    int currentStack = 0;
+    List<CfTryCatch> tryCatchRanges = new ArrayList<>();
+    labels = new HashMap<>(code.blocks.size());
     instructions = new ArrayList<>();
     Iterator<BasicBlock> blockIterator = code.listIterator();
-    while (blockIterator.hasNext()) {
-      BasicBlock block = blockIterator.next();
-      InstructionIterator it = block.iterator();
-      while (it.hasNext()) {
-        Instruction instruction = it.next();
-        if (instruction.outValue() != null) {
-          Value outValue = instruction.outValue();
-          if (outValue instanceof StackValue) {
-            currentStack += outValue.requiredRegisters();
-            maxStack = Math.max(maxStack, currentStack);
+    BasicBlock block = blockIterator.next();
+    CfLabel tryCatchStart = null;
+    CatchHandlers<BasicBlock> tryCatchHandlers = CatchHandlers.EMPTY_BASIC_BLOCK;
+    do {
+      CatchHandlers<BasicBlock> handlers = block.getCatchHandlers();
+      if (!tryCatchHandlers.equals(handlers)) {
+        if (!tryCatchHandlers.isEmpty()) {
+          // Close try-catch and save the range.
+          CfLabel tryCatchEnd = getLabel(block);
+          tryCatchRanges.add(new CfTryCatch(tryCatchStart, tryCatchEnd, tryCatchHandlers, this));
+          if (instructions.get(instructions.size() - 1) != tryCatchEnd) {
+            instructions.add(tryCatchEnd);
           }
         }
-        for (Value inValue : instruction.inValues()) {
-          if (inValue instanceof StackValue) {
-            currentStack -= inValue.requiredRegisters();
+        if (!handlers.isEmpty()) {
+          // Open a try-catch.
+          tryCatchStart = getLabel(block);
+          if (instructions.isEmpty()
+              || instructions.get(instructions.size() - 1) != tryCatchStart) {
+            instructions.add(tryCatchStart);
           }
         }
-        instruction.buildCf(this);
+        tryCatchHandlers = handlers;
       }
-    }
+      BasicBlock nextBlock = blockIterator.hasNext() ? blockIterator.next() : null;
+      buildCfInstructions(block, nextBlock);
+      block = nextBlock;
+    } while (block != null);
     assert currentStack == 0;
-    return new CfCode(maxStack, maxLocals, instructions);
+    return new CfCode(maxStack, maxLocals, instructions, tryCatchRanges);
+  }
+
+  private void buildCfInstructions(BasicBlock block, BasicBlock nextBlock) {
+    boolean fallthrough = false;
+    InstructionIterator it = block.iterator();
+    while (it.hasNext()) {
+      Instruction instruction = it.next();
+      if (instruction.isGoto() && instruction.asGoto().getTarget() == nextBlock) {
+        fallthrough = true;
+        continue;
+      }
+      for (Value inValue : instruction.inValues()) {
+        if (inValue instanceof StackValue) {
+          pop(inValue);
+        }
+      }
+      if (instruction.outValue() != null) {
+        Value outValue = instruction.outValue();
+        if (outValue instanceof StackValue) {
+          push(outValue);
+        }
+      }
+      instruction.buildCf(this);
+    }
+    if (nextBlock == null || (fallthrough && nextBlock.getPredecessors().size() == 1)) {
+      return;
+    }
+    instructions.add(getLabel(nextBlock));
   }
 
   // Callbacks
 
+  public CfLabel getLabel(BasicBlock target){
+    return labels.computeIfAbsent(target, (block) -> new CfLabel());
+  }
+
   public int getLocalRegister(Value value) {
-    if (value.isArgument()) {
-      return argumentRegisters.getInt(value);
+    if (value instanceof FixedLocal) {
+      // Phi stores are marked by a "fixed-local" value which share the same local index.
+      FixedLocal fixed = (FixedLocal) value;
+      return registers.getInt(fixed.phi);
     }
-    return 2 * value.getNumber();
+    return registers.getInt(value);
   }
 
   public void add(CfInstruction instruction) {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java b/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
index e8c6bac..3c7fe40 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
@@ -710,6 +710,9 @@
 
   // Replace result uses for methods where something is known about what is returned.
   public void rewriteMoveResult(IRCode code) {
+    if (options.outputClassFiles) {
+      return;
+    }
     AppInfoWithSubtyping appInfoWithSubtyping = appInfo.withSubtyping();
     InstructionIterator iterator = code.instructionIterator();
     while (iterator.hasNext()) {
diff --git a/src/main/java/com/android/tools/r8/jar/CfApplicationWriter.java b/src/main/java/com/android/tools/r8/jar/CfApplicationWriter.java
index 3509357..b2760e4 100644
--- a/src/main/java/com/android/tools/r8/jar/CfApplicationWriter.java
+++ b/src/main/java/com/android/tools/r8/jar/CfApplicationWriter.java
@@ -57,27 +57,15 @@
     }
   }
 
+  // TODO(zerny): Implement stack-map computation to support Java 1.6 and above.
+  private int downgrade(int version) {
+    return version > 49 ? 49 : version;
+  }
+
   private void writeClass(DexProgramClass clazz, OutputSink outputSink) throws IOException {
-    // If there are CF representations for all methods manually compute stack height and frames.
-    // TODO(zerny): This is a temporary hack since we will need to manually compute stack maps for
-    // any methods that are IR processed.
-    int flags = 0;
-    for (DexEncodedMethod method : clazz.directMethods()) {
-      if (!method.getCode().isCfCode()) {
-        flags = ClassWriter.COMPUTE_FRAMES;
-        break;
-      }
-    }
-    if (flags == 0) {
-      for (DexEncodedMethod method : clazz.virtualMethods()) {
-        if (!method.getCode().isCfCode()) {
-          flags = ClassWriter.COMPUTE_FRAMES;
-        }
-      }
-    }
-    ClassWriter writer = new ClassWriter(flags);
+    ClassWriter writer = new ClassWriter(0);
     writer.visitSource(clazz.sourceFile.toString(), null);
-    int version = clazz.getClassFileVersion();
+    int version = downgrade(clazz.getClassFileVersion());
     int access = clazz.accessFlags.getAsCfAccessFlags();
     String desc = clazz.type.toDescriptorString();
     String name = internalName(clazz.type);
diff --git a/src/main/java/com/android/tools/r8/jar/JarRegisterEffectsVisitor.java b/src/main/java/com/android/tools/r8/jar/JarRegisterEffectsVisitor.java
index 46bcbd5..3321cb7 100644
--- a/src/main/java/com/android/tools/r8/jar/JarRegisterEffectsVisitor.java
+++ b/src/main/java/com/android/tools/r8/jar/JarRegisterEffectsVisitor.java
@@ -51,7 +51,7 @@
       // Nothing to register for method type, it represents only a prototype not associated with a
       // method name.
       if (((Type) cst).getSort() != Type.METHOD) {
-        registry.registerConstClass(application.getType((Type) cst));
+        registry.registerTypeReference(application.getType((Type) cst));
       }
     } else if (cst instanceof Handle) {
       registerMethodHandleType((Handle) cst);
diff --git a/src/main/java/com/android/tools/r8/shaking/AbstractMethodRemover.java b/src/main/java/com/android/tools/r8/shaking/AbstractMethodRemover.java
index fed236a..e4e2ed7 100644
--- a/src/main/java/com/android/tools/r8/shaking/AbstractMethodRemover.java
+++ b/src/main/java/com/android/tools/r8/shaking/AbstractMethodRemover.java
@@ -6,16 +6,10 @@
 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.logging.Log;
-import com.android.tools.r8.utils.MethodSignatureEquivalence;
-import com.google.common.base.Equivalence;
-import com.google.common.base.Equivalence.Wrapper;
 import java.util.ArrayList;
-import java.util.HashSet;
 import java.util.List;
-import java.util.Set;
 
 /**
  * Removes abstract methods if they only shadow methods of the same signature in a superclass.
@@ -29,20 +23,20 @@
 public class AbstractMethodRemover {
 
   private final AppInfoWithSubtyping appInfo;
-  private ScopedDexItemSet scope;
+  private ScopedDexMethodSet scope = new ScopedDexMethodSet();
 
   public AbstractMethodRemover(AppInfoWithSubtyping appInfo) {
     this.appInfo = appInfo;
   }
 
   public void run() {
-    assert scope == null;
+    assert scope.getParent() == null;
     processClass(appInfo.dexItemFactory.objectType);
   }
 
   private void processClass(DexType type) {
     DexClass holder = appInfo.definitionFor(type);
-    scope = new ScopedDexItemSet(scope);
+    scope = scope.newNestedScope();
     if (holder != null && !holder.isLibraryClass()) {
       holder.setVirtualMethods(processMethods(holder.virtualMethods()));
     }
@@ -77,29 +71,4 @@
     return methods == null ? virtualMethods : methods.toArray(new DexEncodedMethod[methods.size()]);
   }
 
-  private static class ScopedDexItemSet {
-
-    private static Equivalence<DexMethod> METHOD_EQUIVALENCE = MethodSignatureEquivalence.get();
-
-    private final ScopedDexItemSet parent;
-    private final Set<Wrapper<DexMethod>> items = new HashSet<>();
-
-    private ScopedDexItemSet(ScopedDexItemSet parent) {
-      this.parent = parent;
-    }
-
-    private boolean contains(Wrapper<DexMethod> item) {
-      return items.contains(item)
-          || ((parent != null) && parent.contains(item));
-    }
-
-    boolean addMethod(DexMethod method) {
-      Wrapper<DexMethod> wrapped = METHOD_EQUIVALENCE.wrap(method);
-      return !contains(wrapped) && items.add(wrapped);
-    }
-
-    ScopedDexItemSet getParent() {
-      return parent;
-    }
-  }
 }
diff --git a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
index 4c30d36..215ea88 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -31,9 +31,7 @@
 import com.android.tools.r8.logging.Log;
 import com.android.tools.r8.shaking.RootSetBuilder.RootSet;
 import com.android.tools.r8.utils.InternalOptions;
-import com.android.tools.r8.utils.MethodSignatureEquivalence;
 import com.android.tools.r8.utils.Timing;
-import com.google.common.base.Equivalence.Wrapper;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.ImmutableSortedSet;
@@ -160,12 +158,6 @@
    */
   private final Map<DexType, Set<DexAnnotation>> deferredAnnotations = new IdentityHashMap<>();
 
-  /**
-   * Methods that have been seen as not reachable due to related classes not being instantiated.
-   * As more instantiated types are collected this set needs to be re-visited.
-   */
-  private List<DexEncodedMethod> pendingAdditionalInstantiatedTypes = new ArrayList<>();
-
   public Enqueuer(AppInfoWithSubtyping appInfo, InternalOptions options) {
     this.appInfo = appInfo;
     this.options = options;
@@ -294,18 +286,7 @@
 
     @Override
     public boolean registerNewInstance(DexType type) {
-      if (instantiatedTypes.contains(type)) {
-        return false;
-      }
-      DexClass clazz = appInfo.definitionFor(type);
-      if (clazz == null) {
-        reportMissingClass(type);
-        return false;
-      }
-      if (Log.ENABLED) {
-        Log.verbose(getClass(), "Register new instatiation of `%s`.", clazz);
-      }
-      workList.add(Action.markInstantiated(clazz, KeepReason.instantiatedIn(currentMethod)));
+      markInstantiated(type, currentMethod);
       return true;
     }
 
@@ -343,30 +324,6 @@
       }
       return false;
     }
-
-    @Override
-    public boolean registerConstClass(DexType type) {
-      boolean result = registerTypeReference(type);
-      // For Proguard compatibility mark default initializer for live type as live.
-      if (options.forceProguardCompatibility) {
-        if (type.isArrayType()) {
-          return result;
-        }
-        assert type.isClassType();
-        DexClass holder = appInfo.definitionFor(type);
-        if (holder == null) {
-          // Don't call reportMissingClass(type) here. That already happened in the call to
-          // registerTypeReference(type).
-          return result;
-        }
-        if (holder.hasDefaultInitializer()) {
-          registerNewInstance(type);
-          DexEncodedMethod init = holder.getDefaultInitializer();
-          markDirectStaticOrConstructorMethodAsLive(init, KeepReason.reachableFromLiveType(type));
-        }
-      }
-      return result;
-    }
   }
 
   //
@@ -410,6 +367,9 @@
       if (options.forceProguardCompatibility) {
         if (holder.hasDefaultInitializer()) {
           DexEncodedMethod init = holder.getDefaultInitializer();
+          // TODO(68246915): For now just register the default constructor as the source of
+          // instantiation.
+          markInstantiated(type, init);
           markDirectStaticOrConstructorMethodAsLive(init, KeepReason.reachableFromLiveType(type));
         }
       }
@@ -510,11 +470,13 @@
    *
    * <p>Only methods that are visible in this type are considered. That is, only those methods that
    * are either defined directly on this type or that are defined on a supertype but are not
-   * shadowed by another inherited method.
+   * shadowed by another inherited method. Furthermore, default methods from implemented interfaces
+   * that are not otherwise shadowed are considered, too.
    */
-  private void transitionMethodsForInstantiatedClass(DexType type) {
-    Set<Wrapper<DexMethod>> seen = new HashSet<>();
-    MethodSignatureEquivalence equivalence = MethodSignatureEquivalence.get();
+  private void transitionMethodsForInstantiatedClass(DexType instantiatedType) {
+    ScopedDexMethodSet seen = new ScopedDexMethodSet();
+    Set<DexType> interfaces = Sets.newIdentityHashSet();
+    DexType type = instantiatedType;
     do {
       DexClass clazz = appInfo.definitionFor(type);
       if (clazz == null) {
@@ -525,15 +487,52 @@
       SetWithReason<DexEncodedMethod> reachableMethods = reachableVirtualMethods.get(type);
       if (reachableMethods != null) {
         for (DexEncodedMethod encodedMethod : reachableMethods.getItems()) {
-          Wrapper<DexMethod> ignoringClass = equivalence.wrap(encodedMethod.method);
-          if (!seen.contains(ignoringClass)) {
-            seen.add(ignoringClass);
-            markVirtualMethodAsLive(encodedMethod, KeepReason.reachableFromLiveType(type));
+          if (seen.addMethod(encodedMethod.method)) {
+            markVirtualMethodAsLive(encodedMethod,
+                KeepReason.reachableFromLiveType(instantiatedType));
           }
         }
       }
+      Collections.addAll(interfaces, clazz.interfaces.values);
       type = clazz.superType;
     } while (type != null && !instantiatedTypes.contains(type));
+    // The set now contains all virtual methods on the type and its supertype that are reachable.
+    // In a second step, we now look at interfaces. We have to do this in this order due to JVM
+    // semantics for default methods. A default method is only reachable if it is not overridden in
+    // any superclass. Also, it is not defined which default method is chosen if multiple
+    // interfaces define the same default method. Hence, for every interface (direct or indirect),
+    // we have to look at the interface chain and mark default methods as reachable, not taking
+    // the shadowing of other interface chains into account.
+    // See https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-5.html#jvms-5.4.3.3
+    for (DexType iface : interfaces) {
+      DexClass clazz = appInfo.definitionFor(iface);
+      if (clazz == null) {
+        reportMissingClass(iface);
+        // TODO(herhut): In essence, our subtyping chain is broken here. Handle that case better.
+        break;
+      }
+      transitionDefaultMethodsForInstantiatedClass(iface, instantiatedType, seen);
+    }
+  }
+
+  private void transitionDefaultMethodsForInstantiatedClass(DexType iface, DexType instantiatedType,
+      ScopedDexMethodSet seen) {
+    DexClass clazz = appInfo.definitionFor(iface);
+    assert clazz.accessFlags.isInterface();
+    SetWithReason<DexEncodedMethod> reachableMethods = reachableVirtualMethods.get(iface);
+    if (reachableMethods != null) {
+      seen = seen.newNestedScope();
+      for (DexEncodedMethod encodedMethod : reachableMethods.getItems()) {
+        assert !encodedMethod.accessFlags.isAbstract();
+        if (seen.addMethod(encodedMethod.method)) {
+          markVirtualMethodAsLive(encodedMethod,
+              KeepReason.reachableFromLiveType(instantiatedType));
+        }
+      }
+      for (DexType subInterface : clazz.interfaces.values) {
+        transitionDefaultMethodsForInstantiatedClass(subInterface, instantiatedType, seen);
+      }
+    }
   }
 
   /**
@@ -587,6 +586,21 @@
     enqueueRootItems(rootSet.getDependentItems(field));
   }
 
+  private void markInstantiated(DexType type, DexEncodedMethod method) {
+    if (instantiatedTypes.contains(type)) {
+      return;
+    }
+    DexClass clazz = appInfo.definitionFor(type);
+    if (clazz == null) {
+      reportMissingClass(type);
+      return;
+    }
+    if (Log.ENABLED) {
+      Log.verbose(getClass(), "Register new instatiation of `%s`.", clazz);
+    }
+    workList.add(Action.markInstantiated(clazz, KeepReason.instantiatedIn(method)));
+  }
+
   private void markDirectStaticOrConstructorMethodAsLive(
       DexEncodedMethod encodedMethod, KeepReason reason) {
     assert encodedMethod != null;
@@ -685,39 +699,33 @@
       SetWithReason<DexEncodedMethod> reachable = reachableVirtualMethods
           .computeIfAbsent(encodedMethod.method.holder, (ignore) -> new SetWithReason<>());
       if (reachable.add(encodedMethod, reason)) {
-        handleIsInstantiatedOrHasInstantiatedSubtype(encodedMethod);
-      }
-    }
-  }
-
-  private void handleIsInstantiatedOrHasInstantiatedSubtype(DexEncodedMethod encodedMethod) {
-    // If the holder type is instantiated, the method is live. Otherwise check whether we find
-    // a subtype that does not shadow this methods but is instantiated.
-    // Note that library classes are always considered instantiated, as we do not know where
-    // they are instantiated.
-    if (isInstantiatedOrHasInstantiatedSubtype(encodedMethod.method.holder)) {
-      if (instantiatedTypes.contains(encodedMethod.method.holder)) {
-        markVirtualMethodAsLive(encodedMethod,
-            KeepReason.reachableFromLiveType(encodedMethod.method.holder));
-      } else {
-        Deque<DexType> worklist = new ArrayDeque<>();
-        fillWorkList(worklist, encodedMethod.method.holder);
-        while (!worklist.isEmpty()) {
-          DexType current = worklist.pollFirst();
-          DexClass currentHolder = appInfo.definitionFor(current);
-          if (currentHolder == null
-              || currentHolder.findVirtualTarget(encodedMethod.method) != null) {
-            continue;
+        // If the holder type is instantiated, the method is live. Otherwise check whether we find
+        // a subtype that does not shadow this methods but is instantiated.
+        // Note that library classes are always considered instantiated, as we do not know where
+        // they are instantiated.
+        if (isInstantiatedOrHasInstantiatedSubtype(encodedMethod.method.holder)) {
+          if (instantiatedTypes.contains(encodedMethod.method.holder)) {
+            markVirtualMethodAsLive(encodedMethod,
+                KeepReason.reachableFromLiveType(encodedMethod.method.holder));
+          } else {
+            Deque<DexType> worklist = new ArrayDeque<>();
+            fillWorkList(worklist, encodedMethod.method.holder);
+            while (!worklist.isEmpty()) {
+              DexType current = worklist.pollFirst();
+              DexClass currentHolder = appInfo.definitionFor(current);
+              if (currentHolder == null
+                  || currentHolder.findVirtualTarget(encodedMethod.method) != null) {
+                continue;
+              }
+              if (instantiatedTypes.contains(current)) {
+                markVirtualMethodAsLive(encodedMethod, KeepReason.reachableFromLiveType(current));
+                break;
+              }
+              fillWorkList(worklist, current);
+            }
           }
-          if (instantiatedTypes.contains(current)) {
-            markVirtualMethodAsLive(encodedMethod, KeepReason.reachableFromLiveType(current));
-            break;
-          }
-          fillWorkList(worklist, current);
         }
       }
-    } else {
-      pendingAdditionalInstantiatedTypes.add(encodedMethod);
     }
   }
 
@@ -790,22 +798,38 @@
   private AppInfoWithLiveness trace(Timing timing) {
     timing.begin("Grow the tree.");
     try {
-      int instantiatedTypesCount = 0;
-      while (true) {
-        doTrace();
-        // If methods where not considered due to relevant types not being instantiated reconsider
-        // if more instantiated types where collected.
-        if (pendingAdditionalInstantiatedTypes.size() > 0
-            && instantiatedTypes.items.size() > instantiatedTypesCount) {
-          instantiatedTypesCount = instantiatedTypes.items.size();
-          List<DexEncodedMethod> reconsider = pendingAdditionalInstantiatedTypes;
-          pendingAdditionalInstantiatedTypes = new ArrayList<>();
-          reconsider.forEach(this::handleIsInstantiatedOrHasInstantiatedSubtype);
-        } else {
-          break;
+      while (!workList.isEmpty()) {
+        Action action = workList.poll();
+        switch (action.kind) {
+          case MARK_INSTANTIATED:
+            processNewlyInstantiatedClass((DexClass) action.target, action.reason);
+            break;
+          case MARK_REACHABLE_FIELD:
+            markFieldAsReachable((DexField) action.target, action.reason);
+            break;
+          case MARK_REACHABLE_VIRTUAL:
+            markVirtualMethodAsReachable((DexMethod) action.target, false, action.reason);
+            break;
+          case MARK_REACHABLE_INTERFACE:
+            markVirtualMethodAsReachable((DexMethod) action.target, true, action.reason);
+            break;
+          case MARK_REACHABLE_SUPER:
+            markSuperMethodAsReachable((DexMethod) action.target,
+                (DexEncodedMethod) action.context);
+            break;
+          case MARK_METHOD_KEPT:
+            markMethodAsKept((DexEncodedMethod) action.target, action.reason);
+            break;
+          case MARK_FIELD_KEPT:
+            markFieldAsKept((DexEncodedField) action.target, action.reason);
+            break;
+          case MARK_METHOD_LIVE:
+            processNewlyLiveMethod(((DexEncodedMethod) action.target), action.reason);
+            break;
+          default:
+            throw new IllegalArgumentException(action.kind.toString());
         }
       }
-
       if (Log.ENABLED) {
         Set<DexEncodedMethod> allLive = Sets.newIdentityHashSet();
         for (Entry<DexType, SetWithReason<DexEncodedMethod>> entry : reachableVirtualMethods
@@ -833,41 +857,6 @@
     return new AppInfoWithLiveness(appInfo, this);
   }
 
-  private void doTrace() {
-    while (!workList.isEmpty()) {
-      Action action = workList.poll();
-      switch (action.kind) {
-        case MARK_INSTANTIATED:
-          processNewlyInstantiatedClass((DexClass) action.target, action.reason);
-          break;
-        case MARK_REACHABLE_FIELD:
-          markFieldAsReachable((DexField) action.target, action.reason);
-          break;
-        case MARK_REACHABLE_VIRTUAL:
-          markVirtualMethodAsReachable((DexMethod) action.target, false, action.reason);
-          break;
-        case MARK_REACHABLE_INTERFACE:
-          markVirtualMethodAsReachable((DexMethod) action.target, true, action.reason);
-          break;
-        case MARK_REACHABLE_SUPER:
-          markSuperMethodAsReachable((DexMethod) action.target,
-              (DexEncodedMethod) action.context);
-          break;
-        case MARK_METHOD_KEPT:
-          markMethodAsKept((DexEncodedMethod) action.target, action.reason);
-          break;
-        case MARK_FIELD_KEPT:
-          markFieldAsKept((DexEncodedField) action.target, action.reason);
-          break;
-        case MARK_METHOD_LIVE:
-          processNewlyLiveMethod(((DexEncodedMethod) action.target), action.reason);
-          break;
-        default:
-          throw new IllegalArgumentException(action.kind.toString());
-      }
-    }
-  }
-
   private void markMethodAsKept(DexEncodedMethod target, KeepReason reason) {
     DexClass holder = appInfo.definitionFor(target.method.holder);
     // If this method no longer has a corresponding class then we have shaken it away before.
diff --git a/src/main/java/com/android/tools/r8/shaking/ScopedDexMethodSet.java b/src/main/java/com/android/tools/r8/shaking/ScopedDexMethodSet.java
new file mode 100644
index 0000000..612b88a
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/shaking/ScopedDexMethodSet.java
@@ -0,0 +1,45 @@
+// 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.shaking;
+
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.utils.MethodSignatureEquivalence;
+import com.google.common.base.Equivalence;
+import com.google.common.base.Equivalence.Wrapper;
+import java.util.HashSet;
+import java.util.Set;
+
+class ScopedDexMethodSet {
+
+  private static Equivalence<DexMethod> METHOD_EQUIVALENCE = MethodSignatureEquivalence.get();
+
+  private final ScopedDexMethodSet parent;
+  private final Set<Wrapper<DexMethod>> items = new HashSet<>();
+
+  public ScopedDexMethodSet() {
+    this(null);
+  }
+
+  private ScopedDexMethodSet(ScopedDexMethodSet parent) {
+    this.parent = parent;
+  }
+
+  public ScopedDexMethodSet newNestedScope() {
+    return new ScopedDexMethodSet(this);
+  }
+
+  private boolean contains(Wrapper<DexMethod> item) {
+    return items.contains(item)
+        || ((parent != null) && parent.contains(item));
+  }
+
+  public boolean addMethod(DexMethod method) {
+    Wrapper<DexMethod> wrapped = METHOD_EQUIVALENCE.wrap(method);
+    return !contains(wrapped) && items.add(wrapped);
+  }
+
+  public ScopedDexMethodSet getParent() {
+    return parent;
+  }
+}
diff --git a/src/test/examplesAndroidN/shaking/InterfaceWithDefault.java b/src/test/examplesAndroidN/shaking/InterfaceWithDefault.java
new file mode 100644
index 0000000..f32a754
--- /dev/null
+++ b/src/test/examplesAndroidN/shaking/InterfaceWithDefault.java
@@ -0,0 +1,11 @@
+// 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 shaking;
+
+public interface InterfaceWithDefault {
+
+  default void foo() {
+    System.out.println("Default method foo");
+  }
+}
diff --git a/src/test/examplesAndroidN/shaking/OtherInterface.java b/src/test/examplesAndroidN/shaking/OtherInterface.java
new file mode 100644
index 0000000..8831a1d
--- /dev/null
+++ b/src/test/examplesAndroidN/shaking/OtherInterface.java
@@ -0,0 +1,9 @@
+// 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 shaking;
+
+public interface OtherInterface {
+
+  void bar();
+}
diff --git a/src/test/examplesAndroidN/shaking/OtherInterfaceWithDefault.java b/src/test/examplesAndroidN/shaking/OtherInterfaceWithDefault.java
new file mode 100644
index 0000000..8d4dec6
--- /dev/null
+++ b/src/test/examplesAndroidN/shaking/OtherInterfaceWithDefault.java
@@ -0,0 +1,12 @@
+// 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 shaking;
+
+public interface OtherInterfaceWithDefault extends OtherInterface {
+
+  @Override
+  default void bar() {
+    System.out.println("bar from OtherInterfaceWithDefault");
+  }
+}
diff --git a/src/test/examplesAndroidN/shaking/Shaking.java b/src/test/examplesAndroidN/shaking/Shaking.java
new file mode 100644
index 0000000..353e9b4
--- /dev/null
+++ b/src/test/examplesAndroidN/shaking/Shaking.java
@@ -0,0 +1,16 @@
+// 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 shaking;
+
+public class Shaking {
+
+  public static void main(String... args) {
+    SubClassOne anInstance = new SubClassOne();
+    invokeFooOnInterface(anInstance);
+  }
+
+  private static void invokeFooOnInterface(InterfaceWithDefault anInstance) {
+    anInstance.foo();
+  }
+}
diff --git a/src/test/examplesAndroidN/shaking/SubClassOne.java b/src/test/examplesAndroidN/shaking/SubClassOne.java
new file mode 100644
index 0000000..7dfcf8d
--- /dev/null
+++ b/src/test/examplesAndroidN/shaking/SubClassOne.java
@@ -0,0 +1,29 @@
+// 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 shaking;
+
+public class SubClassOne implements InterfaceWithDefault, OtherInterfaceWithDefault {
+
+  @Override
+  public void foo() {
+    System.out.println("Method foo from SubClassOne");
+    makeSubClassTwoLive().foo();
+    asOtherInterface().bar();
+  }
+
+  private OtherInterface asOtherInterface() {
+    return new SubClassTwo();
+  }
+
+  @Override
+  public void bar() {
+    System.out.println("Method bar from SubClassOne");
+  }
+
+  private InterfaceWithDefault makeSubClassTwoLive() {
+    // Once we see this method, SubClassTwo will be live. This should also make the default method
+    // in the interface live, as SubClassTwo does not override it.
+    return new SubClassTwo();
+  }
+}
diff --git a/src/test/examplesAndroidN/shaking/SubClassTwo.java b/src/test/examplesAndroidN/shaking/SubClassTwo.java
new file mode 100644
index 0000000..95b2492
--- /dev/null
+++ b/src/test/examplesAndroidN/shaking/SubClassTwo.java
@@ -0,0 +1,8 @@
+// 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 shaking;
+
+public class SubClassTwo implements InterfaceWithDefault, OtherInterfaceWithDefault {
+  // Intentionally left empty.
+}
diff --git a/src/test/examplesAndroidN/shaking/keep-rules.txt b/src/test/examplesAndroidN/shaking/keep-rules.txt
new file mode 100644
index 0000000..791cebf
--- /dev/null
+++ b/src/test/examplesAndroidN/shaking/keep-rules.txt
@@ -0,0 +1,9 @@
+# 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.
+
+# Keep the application entry point. Get rid of everything that is not
+# reachable from there.
+-keep public class shaking.Shaking {
+  public static void main(...);
+}
\ No newline at end of file
diff --git a/src/test/java/com/android/tools/r8/R8RunExamplesTest.java b/src/test/java/com/android/tools/r8/R8RunExamplesTest.java
index 0fc2489..c79719a 100644
--- a/src/test/java/com/android/tools/r8/R8RunExamplesTest.java
+++ b/src/test/java/com/android/tools/r8/R8RunExamplesTest.java
@@ -39,6 +39,8 @@
 @RunWith(Parameterized.class)
 public class R8RunExamplesTest {
 
+  private static final boolean ONLY_RUN_CF_TESTS = false;
+
   enum Input {
     DX, JAVAC, JAVAC_ALL, JAVAC_NONE
   }
@@ -125,22 +127,25 @@
         "constants.Constants",
         "hello.Hello",
         "arithmetic.Arithmetic",
+        "barray.BArray",
     };
 
     List<String[]> fullTestList = new ArrayList<>(tests.length * 2);
-    for (String test : tests) {
-      fullTestList.add(makeTest(Input.JAVAC, CompilerUnderTest.D8, CompilationMode.DEBUG, test));
-      fullTestList.add(makeTest(Input.JAVAC_ALL, CompilerUnderTest.D8, CompilationMode.DEBUG,
-          test));
-      fullTestList.add(makeTest(Input.JAVAC_NONE, CompilerUnderTest.D8, CompilationMode.DEBUG,
-          test));
-      fullTestList.add(makeTest(Input.JAVAC_ALL, CompilerUnderTest.D8, CompilationMode.RELEASE,
-          test));
-      fullTestList.add(makeTest(Input.JAVAC_ALL, CompilerUnderTest.R8, CompilationMode.RELEASE,
-          test));
-      fullTestList.add(makeTest(Input.JAVAC_ALL, CompilerUnderTest.R8, CompilationMode.DEBUG,
-          test));
-      fullTestList.add(makeTest(Input.DX, CompilerUnderTest.R8, CompilationMode.RELEASE, test));
+    if (!ONLY_RUN_CF_TESTS) {
+      for (String test : tests) {
+        fullTestList.add(makeTest(Input.JAVAC, CompilerUnderTest.D8, CompilationMode.DEBUG, test));
+        fullTestList.add(makeTest(Input.JAVAC_ALL, CompilerUnderTest.D8, CompilationMode.DEBUG,
+            test));
+        fullTestList.add(makeTest(Input.JAVAC_NONE, CompilerUnderTest.D8, CompilationMode.DEBUG,
+            test));
+        fullTestList.add(makeTest(Input.JAVAC_ALL, CompilerUnderTest.D8, CompilationMode.RELEASE,
+            test));
+        fullTestList.add(makeTest(Input.JAVAC_ALL, CompilerUnderTest.R8, CompilationMode.RELEASE,
+            test));
+        fullTestList.add(makeTest(Input.JAVAC_ALL, CompilerUnderTest.R8, CompilationMode.DEBUG,
+            test));
+        fullTestList.add(makeTest(Input.DX, CompilerUnderTest.R8, CompilationMode.RELEASE, test));
+      }
     }
     // TODO(zerny): Once all tests pass create the java tests in the main test loop.
     for (String test : javaBytecodeTests) {
diff --git a/src/test/java/com/android/tools/r8/TestBase.java b/src/test/java/com/android/tools/r8/TestBase.java
index ea51c65..2128663 100644
--- a/src/test/java/com/android/tools/r8/TestBase.java
+++ b/src/test/java/com/android/tools/r8/TestBase.java
@@ -26,11 +26,15 @@
 import java.io.IOException;
 import java.nio.file.Path;
 import java.util.Arrays;
+import java.util.Enumeration;
+import java.util.HashSet;
 import java.util.List;
+import java.util.Set;
 import java.util.concurrent.ExecutionException;
 import java.util.function.Consumer;
 import java.util.jar.JarOutputStream;
 import java.util.zip.ZipEntry;
+import java.util.zip.ZipFile;
 import org.junit.Rule;
 import org.junit.rules.TemporaryFolder;
 
@@ -93,6 +97,25 @@
   }
 
   /**
+   * Read the names of classes in a jar.
+   */
+  protected Set<String> readClassesInJar(Path jar) throws IOException {
+    Set<String> result = new HashSet<>();
+    try (ZipFile zipFile = new ZipFile(jar.toFile())) {
+      final Enumeration<? extends ZipEntry> entries = zipFile.entries();
+      while (entries.hasMoreElements()) {
+        ZipEntry entry = entries.nextElement();
+        String name = entry.getName();
+        if (name.endsWith(".class")) {
+          result.add(name.substring(0, name.length() - ".class".length()).replace('/', '.'));
+        }
+      }
+    }
+    return result;
+  }
+
+
+  /**
    * Get the class name generated by javac.
    */
   protected String getJavacGeneratedClassName(Class clazz) {
diff --git a/src/test/java/com/android/tools/r8/ToolHelper.java b/src/test/java/com/android/tools/r8/ToolHelper.java
index 5753d84..2c4bc98 100644
--- a/src/test/java/com/android/tools/r8/ToolHelper.java
+++ b/src/test/java/com/android/tools/r8/ToolHelper.java
@@ -58,15 +58,17 @@
 public class ToolHelper {
 
   public static final String BUILD_DIR = "build/";
-  public static final String EXAMPLES_DIR = "src/test/examples/";
-  public static final String EXAMPLES_ANDROID_O_DIR = "src/test/examplesAndroidO/";
-  public static final String EXAMPLES_ANDROID_P_DIR = "src/test/examplesAndroidP/";
-  public static final String EXAMPLES_BUILD_DIR = BUILD_DIR + "test/examples/";
-  public static final String EXAMPLES_ANDROID_N_BUILD_DIR = BUILD_DIR + "test/examplesAndroidN/";
-  public static final String EXAMPLES_ANDROID_O_BUILD_DIR = BUILD_DIR + "test/examplesAndroidO/";
-  public static final String EXAMPLES_ANDROID_P_BUILD_DIR = BUILD_DIR + "test/examplesAndroidP/";
-  public static final String EXAMPLES_JAVA9_BUILD_DIR = BUILD_DIR + "test/examplesJava9/";
-  public static final String SMALI_BUILD_DIR = BUILD_DIR + "test/smali/";
+  public static final String TESTS_DIR = "src/test/";
+  public static final String EXAMPLES_DIR = TESTS_DIR + "examples/";
+  public static final String EXAMPLES_ANDROID_O_DIR = TESTS_DIR + "examplesAndroidO/";
+  public static final String EXAMPLES_ANDROID_P_DIR = TESTS_DIR + "examplesAndroidP/";
+  public static final String TESTS_BUILD_DIR = BUILD_DIR + "test/";
+  public static final String EXAMPLES_BUILD_DIR = TESTS_BUILD_DIR + "examples/";
+  public static final String EXAMPLES_ANDROID_N_BUILD_DIR = TESTS_BUILD_DIR + "examplesAndroidN/";
+  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_BUILD_DIR = TESTS_BUILD_DIR + "smali/";
 
   public static final String LINE_SEPARATOR = StringUtils.LINE_SEPARATOR;
   public final static String PATH_SEPARATOR = File.pathSeparator;
@@ -970,7 +972,7 @@
     }
   }
 
-  public static void runProguard(Path inJar, Path outJar, Path config) throws IOException {
+  public static String runProguard(Path inJar, Path outJar, Path config) throws IOException {
     List<String> command = new ArrayList<>();
     command.add(PROGUARD);
     command.add("-forceprocessing");  // Proguard just checks the creation time on the in/out jars.
@@ -987,6 +989,7 @@
     if (result.exitCode != 0) {
       fail("Proguard failed, exit code " + result.exitCode + ", stderr:\n" + result.stderr);
     }
+    return result.stdout;
   }
 
 
diff --git a/src/test/java/com/android/tools/r8/shaking/TreeShakingTest.java b/src/test/java/com/android/tools/r8/shaking/TreeShakingTest.java
index 756c93c..081b083 100644
--- a/src/test/java/com/android/tools/r8/shaking/TreeShakingTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/TreeShakingTest.java
@@ -29,6 +29,7 @@
 import com.google.common.collect.Lists;
 import java.io.File;
 import java.io.IOException;
+import java.nio.file.Files;
 import java.nio.file.Path;
 import java.nio.file.Paths;
 import java.util.ArrayList;
@@ -61,27 +62,31 @@
       .of(ANDROID_JAR, ToolHelper.EXAMPLES_BUILD_DIR + "shakinglib.jar"), Paths::get);
   private static final String EMPTY_FLAGS = "src/test/proguard/valid/empty.flags";
   private static final Set<String> IGNORED_FLAGS = ImmutableSet.of(
-      "minification:conflict-mapping.txt",
-      "minification:keep-rules-apply-conflict-mapping.txt"
+      "examples/minification:conflict-mapping.txt",
+      "examples/minification:keep-rules-apply-conflict-mapping.txt"
   );
   private static final Set<String> IGNORED = ImmutableSet.of(
       // there's no point in running those without obfuscation
-      "shaking1:keep-rules-repackaging.txt:DEX:NONE",
-      "shaking1:keep-rules-repackaging.txt:JAR:NONE",
-      "shaking16:keep-rules-1.txt:DEX:NONE",
-      "shaking16:keep-rules-1.txt:JAR:NONE",
-      "shaking16:keep-rules-2.txt:DEX:NONE",
-      "shaking16:keep-rules-2.txt:JAR:NONE",
-      "shaking15:keep-rules.txt:DEX:NONE",
-      "shaking15:keep-rules.txt:JAR:NONE",
-      "minifygeneric:keep-rules.txt:DEX:NONE",
-      "minifygeneric:keep-rules.txt:JAR:NONE",
-      "minifygenericwithinner:keep-rules.txt:DEX:NONE",
-      "minifygenericwithinner:keep-rules.txt:JAR:NONE"
+      "examples/shaking1:keep-rules-repackaging.txt:DEX:NONE",
+      "examples/shaking1:keep-rules-repackaging.txt:JAR:NONE",
+      "examples/shaking16:keep-rules-1.txt:DEX:NONE",
+      "examples/shaking16:keep-rules-1.txt:JAR:NONE",
+      "examples/shaking16:keep-rules-2.txt:DEX:NONE",
+      "examples/shaking16:keep-rules-2.txt:JAR:NONE",
+      "examples/shaking15:keep-rules.txt:DEX:NONE",
+      "examples/shaking15:keep-rules.txt:JAR:NONE",
+      "examples/minifygeneric:keep-rules.txt:DEX:NONE",
+      "examples/minifygeneric:keep-rules.txt:JAR:NONE",
+      "examples/minifygenericwithinner:keep-rules.txt:DEX:NONE",
+      "examples/minifygenericwithinner:keep-rules.txt:JAR:NONE",
+      // No prebuild DEX files for AndroidN
+      "examplesAndroidN/shaking:keep-rules.txt:DEX:NONE",
+      "examplesAndroidN/shaking:keep-rules.txt:DEX:JAVA",
+      "examplesAndroidN/shaking:keep-rules.txt:DEX:AGGRESSIVE"
   );
 
   // TODO(65355452): Reenable or remove inlining tests.
-  private static Set<String> SKIPPED = ImmutableSet.of("inlining");
+  private static Set<String> SKIPPED = ImmutableSet.of("examples/inlining");
 
   private final MinifyMode minify;
 
@@ -107,11 +112,11 @@
       BiConsumer<String, String> outputComparator,
       BiConsumer<DexInspector, DexInspector> dexComparator) {
     this.kind = kind;
-    originalDex = ToolHelper.EXAMPLES_BUILD_DIR + test + "/classes.dex";
+    originalDex = ToolHelper.TESTS_BUILD_DIR + test + "/classes.dex";
     if (kind == Frontend.DEX) {
       this.programFile = originalDex;
     } else {
-      this.programFile = ToolHelper.EXAMPLES_BUILD_DIR + test + ".jar";
+      this.programFile = ToolHelper.TESTS_BUILD_DIR + test + ".jar";
     }
     this.mainClass = mainClass;
     this.keepRulesFiles = keepRulesFiles;
@@ -622,160 +627,166 @@
   public static Collection<Object[]> data() {
     List<String> tests = Arrays
         .asList(
-            "shaking1",
-            "shaking2",
-            "shaking3",
-            "shaking4",
-            "shaking5",
-            "shaking6",
-            "shaking7",
-            "shaking8",
-            "shaking9",
-            "shaking10",
-            "shaking11",
-            "shaking12",
-            "shaking13",
-            "shaking14",
-            "shaking15",
-            "shaking16",
-            "shaking17",
-            "minification",
-            "minifygeneric",
-            "minifygenericwithinner",
-            "assumenosideeffects1",
-            "assumenosideeffects2",
-            "assumenosideeffects3",
-            "assumenosideeffects4",
-            "assumenosideeffects5",
-            "assumevalues1",
-            "assumevalues2",
-            "assumevalues3",
-            "assumevalues4",
-            "assumevalues5",
-            "annotationremoval",
-            "memberrebinding2",
-            "memberrebinding3",
-            "simpleproto1",
-            "simpleproto2",
-            "simpleproto3",
-            "nestedproto1",
-            "nestedproto2",
-            "enumproto",
-            "repeatedproto",
-            "oneofproto");
+            "examples/shaking1",
+            "examples/shaking2",
+            "examples/shaking3",
+            "examples/shaking4",
+            "examples/shaking5",
+            "examples/shaking6",
+            "examples/shaking7",
+            "examples/shaking8",
+            "examples/shaking9",
+            "examples/shaking10",
+            "examples/shaking11",
+            "examples/shaking12",
+            "examples/shaking13",
+            "examples/shaking14",
+            "examples/shaking15",
+            "examples/shaking16",
+            "examples/shaking17",
+            "examples/minification",
+            "examples/minifygeneric",
+            "examples/minifygenericwithinner",
+            "examples/assumenosideeffects1",
+            "examples/assumenosideeffects2",
+            "examples/assumenosideeffects3",
+            "examples/assumenosideeffects4",
+            "examples/assumenosideeffects5",
+            "examples/assumevalues1",
+            "examples/assumevalues2",
+            "examples/assumevalues3",
+            "examples/assumevalues4",
+            "examples/assumevalues5",
+            "examples/annotationremoval",
+            "examples/memberrebinding2",
+            "examples/memberrebinding3",
+            "examples/simpleproto1",
+            "examples/simpleproto2",
+            "examples/simpleproto3",
+            "examples/nestedproto1",
+            "examples/nestedproto2",
+            "examples/enumproto",
+            "examples/repeatedproto",
+            "examples/oneofproto",
+            "examplesAndroidN/shaking");
 
     // Keys can be the name of the test or the name of the test followed by a colon and the name
     // of the keep file.
     Map<String, Consumer<DexInspector>> inspections = new HashMap<>();
-    inspections.put("shaking1:keep-rules.txt", TreeShakingTest::shaking1HasNoClassUnused);
+    inspections.put("examples/shaking1:keep-rules.txt", TreeShakingTest::shaking1HasNoClassUnused);
+    inspections.put("examples/shaking1:keep-rules-repackaging.txt",
+        TreeShakingTest::shaking1IsCorrectlyRepackaged);
     inspections
-        .put("shaking1:keep-rules-repackaging.txt", TreeShakingTest::shaking1IsCorrectlyRepackaged);
-    inspections.put("shaking2:keep-rules.txt", TreeShakingTest::shaking2SuperClassIsAbstract);
-    inspections.put("shaking3:keep-by-tag.txt", TreeShakingTest::shaking3HasNoClassB);
-    inspections.put("shaking3:keep-by-tag-default.txt", TreeShakingTest::shaking3HasNoClassB);
-    inspections.put("shaking3:keep-by-tag-with-pattern.txt", TreeShakingTest::shaking3HasNoClassB);
-    inspections.put("shaking3:keep-by-tag-via-interface.txt", TreeShakingTest::shaking3HasNoClassB);
-    inspections.put("shaking3:keep-by-tag-on-method.txt", TreeShakingTest::shaking3HasNoClassB);
+        .put("examples/shaking2:keep-rules.txt", TreeShakingTest::shaking2SuperClassIsAbstract);
+    inspections.put("examples/shaking3:keep-by-tag.txt", TreeShakingTest::shaking3HasNoClassB);
     inspections
-        .put("shaking3:keep-no-abstract-classes.txt", TreeShakingTest::shaking3HasNoPrivateClass);
-    inspections.put("shaking5", TreeShakingTest::shaking5Inspection);
-    inspections.put("shaking6:keep-public.txt", TreeShakingTest::hasNoPrivateMethods);
-    inspections.put("shaking6:keep-non-public.txt", TreeShakingTest::hasNoPublicMethodsButPrivate);
+        .put("examples/shaking3:keep-by-tag-default.txt", TreeShakingTest::shaking3HasNoClassB);
+    inspections.put("examples/shaking3:keep-by-tag-with-pattern.txt",
+        TreeShakingTest::shaking3HasNoClassB);
+    inspections.put("examples/shaking3:keep-by-tag-via-interface.txt",
+        TreeShakingTest::shaking3HasNoClassB);
     inspections
-        .put("shaking6:keep-justAMethod-public.txt", TreeShakingTest::hasNoPrivateJustAMethod);
-    inspections.put("shaking6:keep-justAMethod-OnInt.txt", TreeShakingTest::hasOnlyIntJustAMethod);
+        .put("examples/shaking3:keep-by-tag-on-method.txt", TreeShakingTest::shaking3HasNoClassB);
+    inspections.put("examples/shaking3:keep-no-abstract-classes.txt",
+        TreeShakingTest::shaking3HasNoPrivateClass);
+    inspections.put("examples/shaking5", TreeShakingTest::shaking5Inspection);
+    inspections.put("examples/shaking6:keep-public.txt", TreeShakingTest::hasNoPrivateMethods);
+    inspections.put("examples/shaking6:keep-non-public.txt",
+        TreeShakingTest::hasNoPublicMethodsButPrivate);
+    inspections.put("examples/shaking6:keep-justAMethod-public.txt",
+        TreeShakingTest::hasNoPrivateJustAMethod);
+    inspections.put("examples/shaking6:keep-justAMethod-OnInt.txt",
+        TreeShakingTest::hasOnlyIntJustAMethod);
+    inspections.put("examples/shaking7:keep-public-fields.txt",
+        TreeShakingTest::shaking7HasOnlyPublicFields);
+    inspections.put("examples/shaking7:keep-double-fields.txt",
+        TreeShakingTest::shaking7HasOnlyDoubleFields);
+    inspections.put("examples/shaking7:keep-public-theDoubleField-fields.txt",
+        TreeShakingTest::shaking7HasOnlyPublicFieldsNamedTheDoubleField);
+    inspections.put("examples/shaking7:keep-public-theIntField-fields.txt",
+        TreeShakingTest::shaking7HasOnlyPublicFieldsNamedTheIntField);
+    inspections.put("examples/shaking8:keep-rules.txt",
+        TreeShakingTest::shaking8ThingClassIsAbstractAndEmpty);
     inspections
-        .put("shaking7:keep-public-fields.txt", TreeShakingTest::shaking7HasOnlyPublicFields);
+        .put("examples/shaking9:keep-rules.txt", TreeShakingTest::shaking9OnlySuperMethodsKept);
     inspections
-        .put("shaking7:keep-double-fields.txt", TreeShakingTest::shaking7HasOnlyDoubleFields);
-    inspections
-        .put("shaking7:keep-public-theDoubleField-fields.txt",
-            TreeShakingTest::shaking7HasOnlyPublicFieldsNamedTheDoubleField);
-    inspections
-        .put("shaking7:keep-public-theIntField-fields.txt",
-            TreeShakingTest::shaking7HasOnlyPublicFieldsNamedTheIntField);
-    inspections
-        .put("shaking8:keep-rules.txt", TreeShakingTest::shaking8ThingClassIsAbstractAndEmpty);
-    inspections
-        .put("shaking9:keep-rules.txt", TreeShakingTest::shaking9OnlySuperMethodsKept);
-    inspections
-        .put("shaking11:keep-rules.txt", TreeShakingTest::shaking11OnlyOneClassKept);
-    inspections
-        .put("shaking11:keep-rules-keep-method.txt", TreeShakingTest::shaking11BothMethodsKept);
-    inspections.put("shaking12:keep-rules.txt",
+        .put("examples/shaking11:keep-rules.txt", TreeShakingTest::shaking11OnlyOneClassKept);
+    inspections.put("examples/shaking11:keep-rules-keep-method.txt",
+        TreeShakingTest::shaking11BothMethodsKept);
+    inspections.put("examples/shaking12:keep-rules.txt",
             TreeShakingTest::shaking12OnlyInstantiatedClassesHaveConstructors);
-    inspections.put("shaking13:keep-rules.txt",
+    inspections.put("examples/shaking13:keep-rules.txt",
             TreeShakingTest::shaking13EnsureFieldWritesCorrect);
-    inspections.put("shaking14:keep-rules.txt",
+    inspections.put("examples/shaking14:keep-rules.txt",
             TreeShakingTest::shaking14EnsureRightStaticMethodsLive);
-    inspections.put("shaking15:keep-rules.txt", TreeShakingTest::shaking15testDictionary);
-    inspections.put("shaking17:keep-rules.txt", TreeShakingTest::abstractMethodRemains);
-    inspections.put("annotationremoval:keep-rules.txt",
+    inspections.put("examples/shaking15:keep-rules.txt", TreeShakingTest::shaking15testDictionary);
+    inspections.put("examples/shaking17:keep-rules.txt", TreeShakingTest::abstractMethodRemains);
+    inspections.put("examples/annotationremoval:keep-rules.txt",
             TreeShakingTest::annotationRemovalHasNoInnerClassAnnotations);
-    inspections.put("annotationremoval:keep-rules-keep-innerannotation.txt",
+    inspections.put("examples/annotationremoval:keep-rules-keep-innerannotation.txt",
             TreeShakingTest::annotationRemovalHasAllInnerClassAnnotations);
+    inspections.put("examples/simpleproto1:keep-rules.txt",
+        TreeShakingTest::simpleproto1UnusedFieldIsGone);
+    inspections.put("examples/simpleproto2:keep-rules.txt",
+        TreeShakingTest::simpleproto2UnusedFieldsAreGone);
+    inspections.put("examples/nestedproto1:keep-rules.txt",
+        TreeShakingTest::nestedproto1UnusedFieldsAreGone);
+    inspections.put("examples/nestedproto2:keep-rules.txt",
+        TreeShakingTest::nestedproto2UnusedFieldsAreGone);
     inspections
-        .put("simpleproto1:keep-rules.txt", TreeShakingTest::simpleproto1UnusedFieldIsGone);
+        .put("examples/enumproto:keep-rules.txt", TreeShakingTest::enumprotoUnusedFieldsAreGone);
     inspections
-        .put("simpleproto2:keep-rules.txt", TreeShakingTest::simpleproto2UnusedFieldsAreGone);
+        .put("examples/repeatedproto:keep-rules.txt", TreeShakingTest::repeatedUnusedFieldsAreGone);
     inspections
-        .put("nestedproto1:keep-rules.txt", TreeShakingTest::nestedproto1UnusedFieldsAreGone);
-    inspections
-        .put("nestedproto2:keep-rules.txt", TreeShakingTest::nestedproto2UnusedFieldsAreGone);
-    inspections
-        .put("enumproto:keep-rules.txt", TreeShakingTest::enumprotoUnusedFieldsAreGone);
-    inspections
-        .put("repeatedproto:keep-rules.txt", TreeShakingTest::repeatedUnusedFieldsAreGone);
-    inspections
-        .put("oneofproto:keep-rules.txt", TreeShakingTest::oneofprotoUnusedFieldsAreGone);
+        .put("examples/oneofproto:keep-rules.txt", TreeShakingTest::oneofprotoUnusedFieldsAreGone);
 
     // Keys can be the name of the test or the name of the test followed by a colon and the name
     // of the keep file.
     Map<String, Collection<List<String>>> optionalRules = new HashMap<>();
-    optionalRules.put("shaking1", ImmutableList.of(
+    optionalRules.put("examples/shaking1", ImmutableList.of(
         Collections.singletonList(EMPTY_FLAGS),
         Lists.newArrayList(EMPTY_FLAGS, EMPTY_FLAGS)));
     List<Object[]> testCases = new ArrayList<>();
 
     Map<String, BiConsumer<String, String>> outputComparators = new HashMap<>();
     outputComparators
-        .put("assumenosideeffects1",
+        .put("examples/assumenosideeffects1",
             TreeShakingTest::assumenosideeffects1CheckOutput);
     outputComparators
-        .put("assumenosideeffects2",
+        .put("examples/assumenosideeffects2",
             TreeShakingTest::assumenosideeffects2CheckOutput);
     outputComparators
-        .put("assumenosideeffects3",
+        .put("examples/assumenosideeffects3",
             TreeShakingTest::assumenosideeffects3CheckOutput);
     outputComparators
-        .put("assumenosideeffects4",
+        .put("examples/assumenosideeffects4",
             TreeShakingTest::assumenosideeffects4CheckOutput);
     outputComparators
-        .put("assumenosideeffects5",
+        .put("examples/assumenosideeffects5",
             TreeShakingTest::assumenosideeffects5CheckOutput);
     outputComparators
-        .put("assumevalues1",
+        .put("examples/assumevalues1",
             TreeShakingTest::assumevalues1CheckOutput);
     outputComparators
-        .put("assumevalues2",
+        .put("examples/assumevalues2",
             TreeShakingTest::assumevalues2CheckOutput);
     outputComparators
-        .put("assumevalues3",
+        .put("examples/assumevalues3",
             TreeShakingTest::assumevalues3CheckOutput);
     outputComparators
-        .put("assumevalues4",
+        .put("examples/assumevalues4",
             TreeShakingTest::assumevalues4CheckOutput);
     outputComparators
-        .put("assumevalues5",
+        .put("examples/assumevalues5",
             TreeShakingTest::assumevalues5CheckOutput);
 
     Map<String, BiConsumer<DexInspector, DexInspector>> dexComparators = new HashMap<>();
     dexComparators
-        .put("shaking1:keep-rules-dont-shrink.txt", TreeShakingTest::checkSameStructure);
+        .put("examples/shaking1:keep-rules-dont-shrink.txt", TreeShakingTest::checkSameStructure);
     dexComparators
-        .put("shaking2:keep-rules-dont-shrink.txt", TreeShakingTest::checkSameStructure);
+        .put("examples/shaking2:keep-rules-dont-shrink.txt", TreeShakingTest::checkSameStructure);
     dexComparators
-        .put("shaking4:keep-rules-dont-shrink.txt", TreeShakingTest::checkSameStructure);
+        .put("examples/shaking4:keep-rules-dont-shrink.txt", TreeShakingTest::checkSameStructure);
 
     Set<String> usedInspections = new HashSet<>();
     Set<String> usedOptionalRules = new HashSet<>();
@@ -784,7 +795,7 @@
 
     for (String test : tests) {
       String mainClass = deriveMainClass(test);
-      File[] keepFiles = new File(ToolHelper.EXAMPLES_DIR + "/" + test)
+      File[] keepFiles = new File(ToolHelper.TESTS_DIR + test)
           .listFiles(file -> file.isFile() && file.getName().endsWith(".txt"));
       for (File keepFile : keepFiles) {
         String keepName = keepFile.getName();
@@ -863,12 +874,13 @@
   }
 
   private static String deriveMainClass(String testName) {
+    String testBaseName = testName.substring(testName.lastIndexOf('/') + 1);
     StringBuilder mainClass = new StringBuilder(testName.length() * 2 + 1);
-    mainClass.append(testName);
+    mainClass.append(testBaseName);
     mainClass.append('.');
-    mainClass.append(Character.toUpperCase(testName.charAt(0)));
-    for (int i = 1; i < testName.length(); i++) {
-      char next = testName.charAt(i);
+    mainClass.append(Character.toUpperCase(testBaseName.charAt(0)));
+    for (int i = 1; i < testBaseName.length(); i++) {
+      char next = testBaseName.charAt(i);
       if (!Character.isAlphabetic(next)) {
         break;
       }
@@ -888,24 +900,32 @@
       builder.appendClasspath(ToolHelper.EXAMPLES_BUILD_DIR + "shakinglib/classes.dex");
     };
 
-    if (outputComparator != null) {
-      String output1 = ToolHelper.runArtNoVerificationErrors(
-          Collections.singletonList(originalDex), mainClass, extraArtArgs, null);
-      String output2 = ToolHelper.runArtNoVerificationErrors(
-          Collections.singletonList(generated.toString()), mainClass, extraArtArgs, null);
-      outputComparator.accept(output1, output2);
-    } else {
-      String output = ToolHelper.checkArtOutputIdentical(Collections.singletonList(originalDex),
-          Collections.singletonList(generated.toString()), mainClass,
-          extraArtArgs, null);
-    }
+    if (Files.exists(Paths.get(originalDex))) {
+      if (outputComparator != null) {
+        String output1 = ToolHelper.runArtNoVerificationErrors(
+            Collections.singletonList(originalDex), mainClass, extraArtArgs, null);
+        String output2 = ToolHelper.runArtNoVerificationErrors(
+            Collections.singletonList(generated.toString()), mainClass, extraArtArgs, null);
+        outputComparator.accept(output1, output2);
+      } else {
+        ToolHelper.checkArtOutputIdentical(Collections.singletonList(originalDex),
+            Collections.singletonList(generated.toString()), mainClass,
+            extraArtArgs, null);
+      }
 
-    if (dexComparator != null) {
-      DexInspector ref = new DexInspector(Paths.get(originalDex));
-      DexInspector inspector = new DexInspector(generated,
-          minify.isMinify() ? temp.getRoot().toPath().resolve(DEFAULT_PROGUARD_MAP_FILE).toString()
-              : null);
-      dexComparator.accept(ref, inspector);
+      if (dexComparator != null) {
+        DexInspector ref = new DexInspector(Paths.get(originalDex));
+        DexInspector inspector = new DexInspector(generated,
+            minify.isMinify() ? temp.getRoot().toPath().resolve(DEFAULT_PROGUARD_MAP_FILE)
+                .toString()
+                : null);
+        dexComparator.accept(ref, inspector);
+      }
+    } else {
+      Assert.assertNull(outputComparator);
+      Assert.assertNull(dexComparator);
+      ToolHelper.runArtNoVerificationErrors(
+          Collections.singletonList(generated.toString()), mainClass, extraArtArgs, null);
     }
 
     if (inspection != null) {
diff --git a/src/test/java/com/android/tools/r8/shaking/forceproguardcompatibility/ForceProguardCompatibilityTest.java b/src/test/java/com/android/tools/r8/shaking/forceproguardcompatibility/ForceProguardCompatibilityTest.java
index dae1163..30d9111 100644
--- a/src/test/java/com/android/tools/r8/shaking/forceproguardcompatibility/ForceProguardCompatibilityTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/forceproguardcompatibility/ForceProguardCompatibilityTest.java
@@ -20,6 +20,7 @@
 import java.io.File;
 import java.nio.file.Path;
 import java.util.List;
+import java.util.Set;
 import org.junit.Test;
 
 public class ForceProguardCompatibilityTest extends TestBase {
@@ -125,4 +126,50 @@
     runDefaultConstructorTest(false, TestClassWithDefaultConstructor.class, true);
     runDefaultConstructorTest(false, TestClassWithoutDefaultConstructor.class, false);
   }
+
+  public void testCheckCast(boolean forceProguardCompatibility, Class mainClass,
+      Class instantiatedClass, boolean containsCheckCast)
+      throws Exception {
+    R8Command.Builder builder = new CompatProguardCommandBuilder(forceProguardCompatibility, false);
+    builder.addProgramFiles(ToolHelper.getClassFileForTestClass(mainClass));
+    builder.addProgramFiles(ToolHelper.getClassFileForTestClass(instantiatedClass));
+    List<String> proguardConfig = ImmutableList.of(
+        "-keep class " + mainClass.getCanonicalName() + " {",
+        "  public static void main(java.lang.String[]);",
+        "}",
+        "-dontobfuscate");
+    builder.addProguardConfiguration(proguardConfig);
+
+    DexInspector inspector = new DexInspector(ToolHelper.runR8(builder.build()));
+    assertTrue(inspector.clazz(getJavacGeneratedClassName(mainClass)).isPresent());
+    ClassSubject clazz = inspector.clazz(getJavacGeneratedClassName(instantiatedClass));
+    assertEquals(containsCheckCast, clazz.isPresent());
+    assertEquals(containsCheckCast, clazz.isPresent());
+    if (clazz.isPresent()) {
+      assertEquals(forceProguardCompatibility && containsCheckCast, !clazz.isAbstract());
+    }
+
+    if (RUN_PROGUARD) {
+      Path proguardedJar = File.createTempFile("proguarded", ".jar", temp.getRoot()).toPath();
+      Path proguardConfigFile = File.createTempFile("proguard", ".config", temp.getRoot()).toPath();
+      FileUtils.writeTextFile(proguardConfigFile, proguardConfig);
+      ToolHelper.runProguard(jarTestClasses(ImmutableList.of(mainClass, instantiatedClass)),
+          proguardedJar, proguardConfigFile);
+      Set<String> classesAfterProguard = readClassesInJar(proguardedJar);
+      assertTrue(classesAfterProguard.contains(mainClass.getCanonicalName()));
+      assertEquals(
+          containsCheckCast, classesAfterProguard.contains(instantiatedClass.getCanonicalName()));
+    }
+  }
+
+  @Test
+  public void checkCastTest() throws Exception {
+    testCheckCast(true, TestMainWithCheckCast.class, TestClassWithDefaultConstructor.class, true);
+    testCheckCast(
+        true, TestMainWithoutCheckCast.class, TestClassWithDefaultConstructor.class, false);
+    testCheckCast(
+        false, TestMainWithCheckCast.class, TestClassWithDefaultConstructor.class, true);
+    testCheckCast(
+        false, TestMainWithoutCheckCast.class, TestClassWithDefaultConstructor.class, false);
+  }
 }
diff --git a/src/test/java/com/android/tools/r8/shaking/forceproguardcompatibility/TestMainWithCheckCast.java b/src/test/java/com/android/tools/r8/shaking/forceproguardcompatibility/TestMainWithCheckCast.java
new file mode 100644
index 0000000..d1eba28
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/forceproguardcompatibility/TestMainWithCheckCast.java
@@ -0,0 +1,15 @@
+// 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.shaking.forceproguardcompatibility;
+
+public class TestMainWithCheckCast {
+
+  public static void main(String[] args) throws Exception {
+    String thisPackage = TestMainWithCheckCast.class.getPackage().getName();
+    Object o = (TestClassWithDefaultConstructor)
+        Class.forName(thisPackage + ".TestClassWithDefaultConstructor").newInstance();
+    System.out.println("Instance of: " + o.getClass().getCanonicalName());
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/shaking/forceproguardcompatibility/TestMainWithoutCheckCast.java b/src/test/java/com/android/tools/r8/shaking/forceproguardcompatibility/TestMainWithoutCheckCast.java
new file mode 100644
index 0000000..1ba2549
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/forceproguardcompatibility/TestMainWithoutCheckCast.java
@@ -0,0 +1,14 @@
+// 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.shaking.forceproguardcompatibility;
+
+public class TestMainWithoutCheckCast {
+
+  public static void main(String[] args) throws Exception {
+    String thisPackage = TestMainWithoutCheckCast.class.getPackage().getName();
+    Object o = Class.forName(thisPackage + ".TestClassWithDefaultConstructor").newInstance();
+    System.out.println("Instantiated " + o.getClass().getCanonicalName());
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/shaking/includedescriptorclasses/IncludeDescriptorClassesTest.java b/src/test/java/com/android/tools/r8/shaking/includedescriptorclasses/IncludeDescriptorClassesTest.java
index 8bff0b3..308ce69 100644
--- a/src/test/java/com/android/tools/r8/shaking/includedescriptorclasses/IncludeDescriptorClassesTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/includedescriptorclasses/IncludeDescriptorClassesTest.java
@@ -24,21 +24,6 @@
 
 public class IncludeDescriptorClassesTest extends TestBase {
 
-  private Set<String> readJarClasses(Path jar) throws IOException {
-    Set<String> result = new HashSet<>();
-    try (ZipFile zipFile = new ZipFile(jar.toFile())) {
-      final Enumeration<? extends ZipEntry> entries = zipFile.entries();
-      while (entries.hasMoreElements()) {
-        ZipEntry entry = entries.nextElement();
-        String name = entry.getName();
-        if (name.endsWith(".class")) {
-          result.add(name.substring(0, name.length() - ".class".length()).replace('/', '.'));
-        }
-      }
-    }
-    return result;
-  }
-
   private class Result {
     final DexInspector inspector;
     final Set<String> classesAfterProguard;
@@ -92,7 +77,7 @@
     if (false) {
       Path proguardedJar = temp.newFile("proguarded.jar").toPath();
       ToolHelper.runProguard(jarTestClasses(classes), proguardedJar, proguardConfig);
-      classesAfterProguard = readJarClasses(proguardedJar);
+      classesAfterProguard = readClassesInJar(proguardedJar);
     }
 
     return new Result(inspector, classesAfterProguard);