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 cb5aad0..72728a8 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
@@ -138,13 +138,10 @@
       if (predecessors.size() <= 1) {
         continue;
       }
-      // If any of the edges to the block are critical, we need to insert new blocks on each
-      // containing the move-exception instruction which must remain the first instruction.
-      if (block.entry() instanceof MoveException) {
-        nextBlockNumber = block.splitCriticalExceptionEdges(
-            nextBlockNumber, valueNumberGenerator, newBlocks::add);
-        continue;
-      }
+
+      // Exceptional edges are given unique header blocks and can have at most one predecessor.
+      assert !block.entry().isMoveException();
+
       for (int predIndex = 0; predIndex < predecessors.size(); predIndex++) {
         BasicBlock pred = predecessors.get(predIndex);
         if (!pred.hasOneNormalExit()) {
@@ -164,6 +161,27 @@
     blocks.addAll(newBlocks);
   }
 
+  public boolean verifySplitCriticalEdges() {
+    for (BasicBlock block : blocks) {
+      // If there are multiple incoming edges, check each has a split block.
+      List<BasicBlock> predecessors = block.getPredecessors();
+      if (predecessors.size() > 1) {
+        for (BasicBlock predecessor : predecessors) {
+          assert predecessor.hasOneNormalExit();
+          assert predecessor.getSuccessors().get(0) == block;
+        }
+      }
+      // If there are outgoing exceptional edges, check that each has a split block.
+      if (block.hasCatchHandlers()) {
+        for (BasicBlock handler : block.getCatchHandlers().getUniqueTargets()) {
+          assert handler.getPredecessors().size() == 1;
+          assert handler.getPredecessors().get(0) == block;
+        }
+      }
+    }
+    return true;
+  }
+
   /**
    * Trace blocks and attempt to put fallthrough blocks immediately after the block that
    * falls through. When we fail to do that we create a new fallthrough block with an explicit
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/CfSourceCode.java b/src/main/java/com/android/tools/r8/ir/conversion/CfSourceCode.java
index 309e1d0..4cbebcf 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/CfSourceCode.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/CfSourceCode.java
@@ -586,7 +586,7 @@
   }
 
   @Override
-  public int getMoveExceptionRegister() {
+  public int getMoveExceptionRegister(int instructionIndex) {
     return CfState.Slot.STACK_OFFSET;
   }
 
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/DexSourceCode.java b/src/main/java/com/android/tools/r8/ir/conversion/DexSourceCode.java
index 31ee706..b59794b 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/DexSourceCode.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/DexSourceCode.java
@@ -21,12 +21,12 @@
 import com.android.tools.r8.code.InvokeSuperRange;
 import com.android.tools.r8.code.InvokeVirtual;
 import com.android.tools.r8.code.InvokeVirtualRange;
+import com.android.tools.r8.code.MoveException;
 import com.android.tools.r8.code.MoveResult;
 import com.android.tools.r8.code.MoveResultObject;
 import com.android.tools.r8.code.MoveResultWide;
 import com.android.tools.r8.code.SwitchPayload;
 import com.android.tools.r8.code.Throw;
-import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.DebugLocalInfo;
 import com.android.tools.r8.graph.DexCode;
 import com.android.tools.r8.graph.DexCode.Try;
@@ -185,14 +185,19 @@
   }
 
   @Override
-  public int getMoveExceptionRegister() {
-    // No register, move-exception is manually entered during construction.
+  public int getMoveExceptionRegister(int instructionIndex) {
+    Instruction instruction = code.instructions[instructionIndex];
+    if (instruction instanceof MoveException) {
+      MoveException moveException = (MoveException) instruction;
+      return moveException.AA;
+    }
     return -1;
   }
 
   @Override
   public Position getDebugPositionAtOffset(int offset) {
-    throw new Unreachable();
+    DexDebugEntry entry = getDebugEntryAtOffset(offset);
+    return entry == null ? preamblePosition : getCanonicalPositionAppendCaller(entry);
   }
 
   @Override
@@ -225,23 +230,30 @@
     }
   }
 
+  private DexDebugEntry getDebugEntryAtOffset(int offset) {
+    DexDebugEntry current = null;
+    if (debugEntries != null) {
+      for (DexDebugEntry entry : debugEntries) {
+        if (entry.address > offset) {
+          break;
+        }
+        current = entry;
+      }
+    }
+    return current;
+  }
+
   private void updateDebugPosition(int instructionIndex, IRBuilder builder) {
     if (debugEntries == null || debugEntries.isEmpty()) {
       return;
     }
-    DexDebugEntry current = null;
     int offset = instructionOffset(instructionIndex);
-    for (DexDebugEntry entry : debugEntries) {
-      if (entry.address > offset) {
-        break;
-      }
-      current = entry;
-    }
-    if (current == null) {
+    DexDebugEntry entry = getDebugEntryAtOffset(offset);
+    if (entry == null) {
       currentPosition = preamblePosition;
     } else {
-      currentPosition = getCanonicalPositionAppendCaller(current);
-      if (current.lineEntry && current.address == offset) {
+      currentPosition = getCanonicalPositionAppendCaller(entry);
+      if (entry.lineEntry && entry.address == offset) {
         builder.addDebugPosition(currentPosition);
       }
     }
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java b/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java
index 5be54f5..963cf41 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java
@@ -93,6 +93,8 @@
 import it.unimi.dsi.fastutil.ints.IntIterator;
 import it.unimi.dsi.fastutil.ints.IntList;
 import it.unimi.dsi.fastutil.ints.IntSet;
+import it.unimi.dsi.fastutil.objects.Reference2IntMap;
+import it.unimi.dsi.fastutil.objects.Reference2IntOpenHashMap;
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.HashMap;
@@ -142,6 +144,13 @@
     }
   }
 
+  private static class SplitBlockWorklistItem extends WorklistItem {
+
+    public SplitBlockWorklistItem(BasicBlock block) {
+      super(block, -1);
+    }
+  }
+
   /**
    * Representation of lists of values that can be used as keys in maps. A list of
    * values is equal to another list of values if it contains exactly the same values
@@ -224,6 +233,10 @@
       return all;
     }
 
+    boolean hasJustOneNormalExit() {
+      return normalSuccessors.size() == 1 && exceptionalSuccessors.isEmpty();
+    }
+
     BlockInfo split(
         int blockStartOffset, int fallthroughOffset, Int2ReferenceMap<BlockInfo> targets) {
       BlockInfo fallthroughInfo = new BlockInfo();
@@ -279,6 +292,7 @@
 
   // Mapping from instruction offsets to basic-block targets.
   private final Int2ReferenceSortedMap<BlockInfo> targets = new Int2ReferenceAVLTreeMap<>();
+  private final Reference2IntMap<BasicBlock> offsets = new Reference2IntOpenHashMap<>();
 
   // Worklist of reachable blocks.
   private final Queue<Integer> traceBlocksWorklist = new LinkedList<>();
@@ -296,7 +310,6 @@
   private final LinkedList<BasicBlock> blocks = new LinkedList<>();
 
   private BasicBlock currentBlock = null;
-  private final List<BasicBlock.Pair> needGotoToCatchBlocks = new ArrayList<>();
   final private ValueNumberGenerator valueNumberGenerator;
   private final DexEncodedMethod method;
   private final AppInfo appInfo;
@@ -365,7 +378,9 @@
     source.setUp();
 
     // Create entry block (at a non-targetable address).
-    targets.put(INITIAL_BLOCK_OFFSET, new BlockInfo());
+    BlockInfo initialBlockInfo = new BlockInfo();
+    targets.put(INITIAL_BLOCK_OFFSET, initialBlockInfo);
+    offsets.put(initialBlockInfo.block, INITIAL_BLOCK_OFFSET);
 
     // Process reachable code paths starting from instruction 0.
     int instCount = source.instructionCount();
@@ -411,9 +426,6 @@
     // Check that the last block is closed and does not fall off the end.
     assert currentBlock == null;
 
-    // Handle where a catch handler hits the same block as the fallthrough.
-    handleFallthroughToCatchBlock();
-
     // Verify that we have properly filled all blocks
     // Must be after handle-catch (which has delayed edges),
     // but before handle-exit (which does not maintain predecessor counts).
@@ -434,9 +446,8 @@
     // Package up the IR code.
     IRCode ir = new IRCode(options, method, blocks, valueNumberGenerator, hasDebugPositions);
 
-    // Split critical edges to make sure that we have a place to insert phi moves if
-    // necessary.
-    ir.splitCriticalEdges();
+    // Verify critical edges are split so we have a place to insert phi moves if necessary.
+    assert ir.verifySplitCriticalEdges();
 
     for (BasicBlock block : blocks) {
       block.deduplicatePhis();
@@ -550,6 +561,12 @@
       // Process synthesized move-exception block specially.
       if (item instanceof MoveExceptionWorklistItem) {
         processMoveExceptionItem((MoveExceptionWorklistItem) item);
+        closeCurrentBlockGuaranteedNotToNeedEdgeSplitting();
+        continue;
+      }
+      // Split blocks are just pending close.
+      if (item instanceof SplitBlockWorklistItem) {
+        closeCurrentBlockGuaranteedNotToNeedEdgeSplitting();
         continue;
       }
       // Build IR for each dex instruction in the block.
@@ -571,20 +588,20 @@
 
   private void processMoveExceptionItem(MoveExceptionWorklistItem moveExceptionItem) {
     // TODO(zerny): Link with outer try-block handlers, if any. b/65203529
-    int moveExceptionDest = source.getMoveExceptionRegister();
-    assert moveExceptionDest >= 0;
     int targetIndex = source.instructionIndex(moveExceptionItem.targetOffset);
-    Value out = writeRegister(moveExceptionDest, ValueType.OBJECT, ThrowingInfo.NO_THROW, null);
-    Position position = source.getDebugPositionAtOffset(moveExceptionItem.targetOffset);
-    MoveException moveException = new MoveException(out);
-    moveException.setPosition(position);
-    currentBlock.add(moveException);
+    int moveExceptionDest = source.getMoveExceptionRegister(targetIndex);
+    if (moveExceptionDest >= 0) {
+      Value out = writeRegister(moveExceptionDest, ValueType.OBJECT, ThrowingInfo.NO_THROW, null);
+      Position position = source.getDebugPositionAtOffset(moveExceptionItem.targetOffset);
+      MoveException moveException = new MoveException(out);
+      moveException.setPosition(position);
+      currentBlock.add(moveException);
+    }
     Goto exit = new Goto();
     currentBlock.add(exit);
     BasicBlock targetBlock = getTarget(moveExceptionItem.targetOffset);
     currentBlock.link(targetBlock);
     addToWorklist(targetBlock, targetIndex);
-    closeCurrentBlock();
   }
 
   // Helper to resolve switch payloads and build switch instructions (dex code only).
@@ -976,11 +993,8 @@
   public void addGoto(int targetOffset) {
     addInstruction(new Goto());
     BasicBlock targetBlock = getTarget(targetOffset);
-    if (currentBlock.hasCatchSuccessor(targetBlock)) {
-      needGotoToCatchBlocks.add(new BasicBlock.Pair(currentBlock, targetBlock));
-    } else {
-      currentBlock.link(targetBlock);
-    }
+    assert !currentBlock.hasCatchSuccessor(targetBlock);
+    currentBlock.link(targetBlock);
     addToWorklist(targetBlock, source.instructionIndex(targetOffset));
     closeCurrentBlock();
   }
@@ -1292,25 +1306,20 @@
   }
 
   public void addMoveException(int dest) {
-    Value out = writeRegister(dest, ValueType.OBJECT, ThrowingInfo.NO_THROW);
-    assert !out.hasLocalInfo();
-    MoveException instruction = new MoveException(out);
-    assert !instruction.instructionTypeCanThrow();
-    if (currentBlock.getInstructions().size() == 1 && currentBlock.entry().isDebugPosition()) {
-      InstructionListIterator it = currentBlock.listIterator();
-      Instruction entry = it.next();
-      assert entry.getPosition().equals(source.getCurrentPosition());
-      attachLocalValues(instruction);
-      it.replaceCurrentInstruction(instruction);
-      return;
+    assert !currentBlock.getPredecessors().isEmpty();
+    assert currentBlock.getPredecessors().stream().allMatch(b -> b.entry().isMoveException());
+    assert verifyValueIsMoveException(readRegister(dest, ValueType.OBJECT));
+  }
+
+  private static boolean verifyValueIsMoveException(Value value) {
+    if (value.isPhi()) {
+      for (Value operand : value.asPhi().getOperands()) {
+        assert operand.definition.isMoveException();
+      }
+    } else {
+      assert value.definition.isMoveException();
     }
-    if (!currentBlock.getInstructions().isEmpty()) {
-      throw new CompilationError("Invalid MoveException instruction encountered. "
-          + "The MoveException instruction is not the first instruction in the block in "
-          + method.qualifiedName()
-          + ".");
-    }
-    addInstruction(instruction);
+    return true;
   }
 
   public void addMoveResult(int dest) {
@@ -1513,7 +1522,7 @@
   public void addThrow(int value) {
     Value in = readRegister(value, ValueType.OBJECT);
     addInstruction(new Throw(in));
-    closeCurrentBlock();
+    closeCurrentBlockGuaranteedNotToNeedEdgeSplitting();
   }
 
   public void addOr(NumericType type, int dest, int left, int right) {
@@ -1805,24 +1814,47 @@
     if (!throwingInstructionInCurrentBlock) {
       return;
     }
-    BasicBlock block = new BasicBlock();
+    // Note that when splitting the block in two we must update the CFG information so that we can
+    // correctly identify if the normal exits of the constructed block must be split once it is
+    // closed.
+    int currentBlockOffset = getOffset(currentBlock);
+    BlockInfo currentBlockInfo = getBlockInfo(currentBlockOffset);
+
+    BlockInfo info = new BlockInfo();
+    BasicBlock block = info.block;
     block.setNumber(nextBlockNumber++);
     blocks.add(block);
-    block.incrementUnfilledPredecessorCount();
+
+    // Compute some unused offset for the new block and link it in the CFG.
     int freshOffset = INITIAL_BLOCK_OFFSET - 1;
     while (targets.containsKey(freshOffset)) {
       freshOffset--;
     }
-    targets.put(freshOffset, null);
+    targets.put(freshOffset, info);
+    offsets.put(block, freshOffset);
+
+    // Copy over the exceptional successors.
     for (int offset : source.getCurrentCatchHandlers().getUniqueTargets()) {
+      info.addExceptionalSuccessor(offset);
       BlockInfo target = targets.get(offset);
       assert !target.block.isSealed();
       target.block.incrementUnfilledPredecessorCount();
       target.addExceptionalPredecessor(freshOffset);
     }
+
+    // Move all normal successors to the new block.
+    currentBlockInfo.normalSuccessors.forEach(info::addNormalSuccessor);
+    currentBlockInfo.normalSuccessors.clear();
+
+    // Link the two blocks.
     addInstruction(new Goto());
     currentBlock.link(block);
-    closeCurrentBlock();
+    block.incrementUnfilledPredecessorCount();
+    currentBlockInfo.addNormalSuccessor(freshOffset);
+    info.addNormalPredecessor(currentBlockOffset);
+
+    // The new block can only have a single predecessor and so we don't need to split between them.
+    closeCurrentBlockGuaranteedNotToNeedEdgeSplitting();
     setCurrentBlock(block);
   }
 
@@ -1843,29 +1875,19 @@
         assert !throwingInstructionInCurrentBlock;
         throwingInstructionInCurrentBlock = true;
         List<BasicBlock> targets = new ArrayList<>(catchHandlers.getAllTargets().size());
-        int moveExceptionDest = source.getMoveExceptionRegister();
-        if (moveExceptionDest < 0) {
-          for (int targetOffset : catchHandlers.getAllTargets()) {
-            BasicBlock target = getTarget(targetOffset);
-            addToWorklist(target, source.instructionIndex(targetOffset));
-            targets.add(target);
+        // Construct unique move-exception header blocks for each unique target.
+        Map<BasicBlock, BasicBlock> moveExceptionHeaders =
+            new IdentityHashMap<>(catchHandlers.getUniqueTargets().size());
+        for (int targetOffset : catchHandlers.getAllTargets()) {
+          BasicBlock target = getTarget(targetOffset);
+          BasicBlock header = moveExceptionHeaders.get(target);
+          if (header == null) {
+            header = new BasicBlock();
+            header.incrementUnfilledPredecessorCount();
+            moveExceptionHeaders.put(target, header);
+            ssaWorklist.add(new MoveExceptionWorklistItem(header, targetOffset));
           }
-        } else {
-          // If there is a well-defined move-exception destination register (eg, compiling from
-          // Java-bytecode) then we construct move-exception header blocks for each unique target.
-          Map<BasicBlock, BasicBlock> moveExceptionHeaders =
-              new IdentityHashMap<>(catchHandlers.getUniqueTargets().size());
-          for (int targetOffset : catchHandlers.getAllTargets()) {
-            BasicBlock target = getTarget(targetOffset);
-            BasicBlock header = moveExceptionHeaders.get(target);
-            if (header == null) {
-              header = new BasicBlock();
-              header.incrementUnfilledPredecessorCount();
-              moveExceptionHeaders.put(target, header);
-              ssaWorklist.add(new MoveExceptionWorklistItem(header, targetOffset));
-            }
-            targets.add(header);
-          }
+          targets.add(header);
         }
         currentBlock.linkCatchSuccessors(catchHandlers.getGuards(), targets);
       }
@@ -1907,6 +1929,7 @@
         info = new BlockInfo();
       }
       targets.put(offset, info);
+      offsets.put(info.block, offset);
     }
     return info;
   }
@@ -1980,11 +2003,23 @@
 
   // Private block helpers.
 
+  private BlockInfo getBlockInfo(int offset) {
+    return targets.get(offset);
+  }
+
+  private BlockInfo getBlockInfo(BasicBlock block) {
+    return getBlockInfo(getOffset(block));
+  }
+
   private BasicBlock getTarget(int offset) {
     return targets.get(offset).block;
   }
 
-  private void closeCurrentBlock() {
+  private int getOffset(BasicBlock block) {
+    return offsets.getInt(block);
+  }
+
+  private void closeCurrentBlockGuaranteedNotToNeedEdgeSplitting() {
     // TODO(zerny): To ensure liveness of locals throughout the entire block, we might want to
     // insert reads before closing the block. It is unclear if we can rely on a local-end to ensure
     // liveness in all blocks where the local should be live.
@@ -1994,48 +2029,41 @@
     throwingInstructionInCurrentBlock = false;
   }
 
+  private void closeCurrentBlock() {
+    assert currentBlock != null;
+    BlockInfo info = getBlockInfo(currentBlock);
+    if (!info.hasJustOneNormalExit()) {
+      // Exceptional edges are always split on construction, so no need to split edges to them.
+      for (int successorOffset : info.normalSuccessors) {
+        BlockInfo successorInfo = getBlockInfo(successorOffset);
+        if (successorInfo.predecessorCount() > 1) {
+          BasicBlock splitBlock = createSplitEdgeBlock(currentBlock, successorInfo.block);
+          ssaWorklist.add(new SplitBlockWorklistItem(splitBlock));
+        }
+      }
+    }
+    closeCurrentBlockGuaranteedNotToNeedEdgeSplitting();
+  }
+
+  private static BasicBlock createSplitEdgeBlock(BasicBlock source, BasicBlock target) {
+    BasicBlock splitBlock = new BasicBlock();
+    splitBlock.add(new Goto());
+    splitBlock.incrementUnfilledPredecessorCount();
+    splitBlock.getPredecessors().add(source);
+    splitBlock.getSuccessors().add(target);
+    source.replaceSuccessor(target, splitBlock);
+    target.replacePredecessor(source, splitBlock);
+    return splitBlock;
+  }
+
   private void closeCurrentBlockWithFallThrough(BasicBlock nextBlock) {
     assert currentBlock != null;
     addInstruction(new Goto());
-    if (currentBlock.hasCatchSuccessor(nextBlock)) {
-      needGotoToCatchBlocks.add(new BasicBlock.Pair(currentBlock, nextBlock));
-    } else {
-      currentBlock.link(nextBlock);
-    }
+    assert !currentBlock.hasCatchSuccessor(nextBlock);
+    currentBlock.link(nextBlock);
     closeCurrentBlock();
   }
 
-  private void handleFallthroughToCatchBlock() {
-    // When a catch handler for a block goes to the same block as the fallthrough for that
-    // block the graph only has one edge there. In these cases we add an additional block so the
-    // catch edge goes through that and then make the fallthrough go through a new direct edge.
-    for (BasicBlock.Pair pair : needGotoToCatchBlocks) {
-      BasicBlock source = pair.first;
-      BasicBlock target = pair.second;
-
-      // New block with one unfilled predecessor.
-      BasicBlock newBlock = BasicBlock.createGotoBlock(nextBlockNumber++, target);
-      blocks.add(newBlock);
-      newBlock.incrementUnfilledPredecessorCount();
-
-      // Link blocks.
-      source.replaceSuccessor(target, newBlock);
-      newBlock.getPredecessors().add(source);
-      source.getSuccessors().add(target);
-      target.getPredecessors().add(newBlock);
-
-      // Check that the successor indexes are correct.
-      assert source.hasCatchSuccessor(newBlock);
-      assert !source.hasCatchSuccessor(target);
-
-      // Mark the filled predecessors to the blocks.
-      if (source.isFilled()) {
-        newBlock.filledPredecessor(this);
-      }
-      target.filledPredecessor(this);
-    }
-  }
-
   /**
    * Change to control-flow graph to avoid repeated phi operands when all the same values
    * flow in from multiple predecessors.
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/JarSourceCode.java b/src/main/java/com/android/tools/r8/ir/conversion/JarSourceCode.java
index 5c25fba..53bbb7e 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/JarSourceCode.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/JarSourceCode.java
@@ -594,7 +594,12 @@
   }
 
   @Override
-  public int getMoveExceptionRegister() {
+  public int getMoveExceptionRegister(int instructionIndex) {
+    return getMoveExceptionRegister();
+  }
+
+  // In classfiles the register is always on top of stack.
+  private int getMoveExceptionRegister() {
     return state.startOfStack;
   }
 
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/SourceCode.java b/src/main/java/com/android/tools/r8/ir/conversion/SourceCode.java
index e95790a..bf2b51f 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/SourceCode.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/SourceCode.java
@@ -59,7 +59,8 @@
   void resolveAndBuildNewArrayFilledData(int arrayRef, int payloadOffset, IRBuilder builder);
 
   CatchHandlers<Integer> getCurrentCatchHandlers();
-  int getMoveExceptionRegister();
+
+  int getMoveExceptionRegister(int instructionIndex);
 
   // For debugging/verification purpose.
   boolean verifyRegister(int register);
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/Outliner.java b/src/main/java/com/android/tools/r8/ir/optimize/Outliner.java
index 6cb8f6e..e749479 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/Outliner.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/Outliner.java
@@ -1099,7 +1099,7 @@
     }
 
     @Override
-    public int getMoveExceptionRegister() {
+    public int getMoveExceptionRegister(int instructionIndex) {
       throw new Unreachable();
     }
 
diff --git a/src/main/java/com/android/tools/r8/ir/synthetic/SyntheticSourceCode.java b/src/main/java/com/android/tools/r8/ir/synthetic/SyntheticSourceCode.java
index 80a439a..c64d8ed 100644
--- a/src/main/java/com/android/tools/r8/ir/synthetic/SyntheticSourceCode.java
+++ b/src/main/java/com/android/tools/r8/ir/synthetic/SyntheticSourceCode.java
@@ -209,7 +209,7 @@
   }
 
   @Override
-  public int getMoveExceptionRegister() {
+  public int getMoveExceptionRegister(int instructionIndex) {
     throw new Unreachable();
   }
 
diff --git a/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java b/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java
index 28ca9fc..459fe7a 100644
--- a/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java
+++ b/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java
@@ -139,10 +139,20 @@
   }
 
   private void stripAttributes(DexProgramClass clazz) {
-    if (!keep.enclosingMethod && clazz.getEnclosingMethod() != null) {
+    // If [clazz] is mentioned by a keep rule, it could be used for reflection, and we therefore
+    // need to keep the enclosing method and inner classes attributes, if requested. In Proguard
+    // compatibility mode we keep these attributes independent of whether the given class is kept.
+    if (appInfo.isPinned(clazz.type) || options.forceProguardCompatibility) {
+      if (!keep.enclosingMethod) {
+        clazz.clearEnclosingMethod();
+      }
+      if (!keep.innerClasses) {
+        clazz.clearInnerClasses();
+      }
+    } else {
+      // These attributes are only relevant for reflection, and this class is not used for
+      // reflection. (Note that clearing these attributes can enable more vertical class merging.)
       clazz.clearEnclosingMethod();
-    }
-    if (!keep.innerClasses && !clazz.getInnerClasses().isEmpty()) {
       clazz.clearInnerClasses();
     }
   }
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 d42c68b..77a369d 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -112,6 +112,8 @@
   private final Set<DexField> protoLiteFields = Sets.newIdentityHashSet();
   private final Set<DexItem> identifierNameStrings = Sets.newIdentityHashSet();
 
+  /** Set of method signatures used in invoke-super instructions that cannot be resolved. */
+  private final Set<DexMethod> brokenSuperInvokes = Sets.newIdentityHashSet();
   /**
    * This map keeps a view of all virtual methods that are reachable from virtual invokes. A method
    * is reachable even if no live subtypes exist, so this is not sufficient for inclusion in the
@@ -1018,6 +1020,7 @@
     DexEncodedMethod resolutionTarget = appInfo.resolveMethod(method.holder, method)
         .asResultOfResolve();
     if (resolutionTarget == null) {
+      brokenSuperInvokes.add(method);
       reportMissingMethod(method);
       return;
     }
@@ -1517,6 +1520,8 @@
      * Set of all methods referenced in static invokes;
      */
     public final SortedSet<DexMethod> staticInvokes;
+    /** Set of method signatures used in invoke-super instructions that cannot be resolved. */
+    public final SortedSet<DexMethod> brokenSuperInvokes;
     /**
      * Set of all items that have to be kept independent of whether they are used.
      */
@@ -1583,6 +1588,8 @@
       this.superInvokes = joinInvokedMethods(enqueuer.superInvokes, TargetWithContext::getTarget);
       this.directInvokes = joinInvokedMethods(enqueuer.directInvokes);
       this.staticInvokes = joinInvokedMethods(enqueuer.staticInvokes);
+      this.brokenSuperInvokes =
+          ImmutableSortedSet.copyOf(DexMethod::slowCompareTo, enqueuer.brokenSuperInvokes);
       this.noSideEffects = enqueuer.rootSet.noSideEffects;
       this.assumedValues = enqueuer.rootSet.assumedValues;
       this.alwaysInline = enqueuer.rootSet.alwaysInline;
@@ -1621,6 +1628,7 @@
       this.superInvokes = previous.superInvokes;
       this.directInvokes = previous.directInvokes;
       this.staticInvokes = previous.staticInvokes;
+      this.brokenSuperInvokes = previous.brokenSuperInvokes;
       this.protoLiteFields = previous.protoLiteFields;
       this.alwaysInline = previous.alwaysInline;
       this.identifierNameStrings = previous.identifierNameStrings;
@@ -1657,6 +1665,7 @@
       this.superInvokes = rewriteMethodsConservatively(previous.superInvokes, lense);
       this.directInvokes = rewriteMethodsConservatively(previous.directInvokes, lense);
       this.staticInvokes = rewriteMethodsConservatively(previous.staticInvokes, lense);
+      this.brokenSuperInvokes = rewriteMethodsConservatively(previous.brokenSuperInvokes, lense);
       this.prunedTypes = rewriteItems(previous.prunedTypes, lense::lookupType);
       // TODO(herhut): Migrate these to Descriptors, as well.
       assert lense.assertNotModified(previous.noSideEffects.keySet());
@@ -1703,6 +1712,7 @@
       this.superInvokes = previous.superInvokes;
       this.directInvokes = previous.directInvokes;
       this.staticInvokes = previous.staticInvokes;
+      this.brokenSuperInvokes = previous.brokenSuperInvokes;
       this.protoLiteFields = previous.protoLiteFields;
       this.alwaysInline = previous.alwaysInline;
       this.identifierNameStrings = previous.identifierNameStrings;
diff --git a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
index c5d2144..6f935ee 100644
--- a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
+++ b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
@@ -6,7 +6,6 @@
 import com.android.tools.r8.errors.CompilationError;
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.AppInfo.ResolutionResult;
-import com.android.tools.r8.graph.DefaultUseRegistry;
 import com.android.tools.r8.graph.DexAnnotationSet;
 import com.android.tools.r8.graph.DexApplication;
 import com.android.tools.r8.graph.DexClass;
@@ -77,7 +76,6 @@
     ILLEGAL_ACCESS,
     NO_SIDE_EFFECTS,
     PINNED_SOURCE,
-    PINNED_TARGET,
     RESOLUTION_FOR_FIELDS_MAY_CHANGE,
     RESOLUTION_FOR_METHODS_MAY_CHANGE,
     STATIC_INITIALIZERS,
@@ -109,9 +107,6 @@
         case PINNED_SOURCE:
           message = "it should be kept";
           break;
-        case PINNED_TARGET:
-          message = "its target should be kept";
-          break;
         case RESOLUTION_FOR_FIELDS_MAY_CHANGE:
           message = "it could affect field resolution";
           break;
@@ -181,37 +176,24 @@
     extractPinnedItems(appInfo.alwaysInline, pinnedTypes, AbortReason.ALWAYS_INLINE);
     extractPinnedItems(appInfo.noSideEffects.keySet(), pinnedTypes, AbortReason.NO_SIDE_EFFECTS);
 
-    for (DexProgramClass clazz : classes) {
-      for (DexEncodedMethod method : clazz.methods()) {
-        // Avoid merging two types if this could remove a NoSuchMethodError, as illustrated by the
-        // following example. (Alternatively, it would be possible to merge A and B and rewrite the
-        // "invoke-super A.m" instruction into "invoke-super Object.m" to preserve the error. This
-        // situation should generally not occur in practice, though.)
-        //
-        //   class A {}
-        //   class B extends A {
-        //     public void m() {}
-        //   }
-        //   class C extends A {
-        //     public void m() {
-        //       invoke-super "A.m" <- should yield NoSuchMethodError, cannot merge A and B
-        //     }
-        //   }
-        if (!method.isStaticMethod()) {
-          method.registerCodeReferences(
-              new DefaultUseRegistry() {
-                @Override
-                public boolean registerInvokeSuper(DexMethod target) {
-                  DexClass targetClass = appInfo.definitionFor(target.getHolder());
-                  if (targetClass != null
-                      && targetClass.isProgramClass()
-                      && targetClass.lookupVirtualMethod(target) == null) {
-                    pinnedTypes.add(target.getHolder());
-                  }
-                  return true;
-                }
-              });
-        }
+    // Avoid merging two types if this could remove a NoSuchMethodError, as illustrated by the
+    // following example. (Alternatively, it would be possible to merge A and B and rewrite the
+    // "invoke-super A.m" instruction into "invoke-super Object.m" to preserve the error. This
+    // situation should generally not occur in practice, though.)
+    //
+    //   class A {}
+    //   class B extends A {
+    //     public void m() {}
+    //   }
+    //   class C extends A {
+    //     public void m() {
+    //       invoke-super "A.m" <- should yield NoSuchMethodError, cannot merge A and B
+    //     }
+    //   }
+    for (DexMethod signature : appInfo.brokenSuperInvokes) {
+      DexClass targetClass = appInfo.definitionFor(signature.holder);
+      if (targetClass != null && targetClass.isProgramClass()) {
+        pinnedTypes.add(signature.holder);
       }
     }
     return pinnedTypes;
@@ -469,13 +451,6 @@
 
       DexClass targetClass = appInfo.definitionFor(clazz.type.getSingleSubtype());
       assert !mergedClasses.containsKey(targetClass.type);
-      if (appInfo.isPinned(targetClass.type)) {
-        // We have to keep the target class intact, so we cannot merge it.
-        if (Log.ENABLED) {
-          AbortReason.PINNED_TARGET.printLogMessageForClass(clazz);
-        }
-        continue;
-      }
       if (clazz.hasClassInitializer() && targetClass.hasClassInitializer()) {
         // TODO(herhut): Handle class initializers.
         if (Log.ENABLED) {
@@ -1179,7 +1154,7 @@
     }
   }
 
-  private static class CollisionDetector {
+  private class CollisionDetector {
 
     private static final int NOT_FOUND = 1 << (Integer.SIZE - 1);
 
@@ -1204,27 +1179,30 @@
     }
 
     boolean mayCollide() {
+      timing.begin("collision detection");
       fillSeenPositions(invokes);
+      boolean result = false;
       // If the type is not used in methods at all, there cannot be any conflict.
-      if (seenPositions.isEmpty()) {
-        return false;
-      }
-      for (DexMethod method : invokes) {
-        Int2IntMap positionsMap = seenPositions.get(method.name);
-        if (positionsMap != null) {
-          int arity = method.getArity();
-          int previous = positionsMap.get(arity);
-          if (previous != NOT_FOUND) {
-            assert previous != 0;
-            int positions = computePositionsFor(method.proto, source, sourceProtoCache,
-                substituions);
-            if ((positions & previous) != 0) {
-              return true;
+      if (!seenPositions.isEmpty()) {
+        for (DexMethod method : invokes) {
+          Int2IntMap positionsMap = seenPositions.get(method.name);
+          if (positionsMap != null) {
+            int arity = method.getArity();
+            int previous = positionsMap.get(arity);
+            if (previous != NOT_FOUND) {
+              assert previous != 0;
+              int positions =
+                  computePositionsFor(method.proto, source, sourceProtoCache, substituions);
+              if ((positions & previous) != 0) {
+                result = true;
+                break;
+              }
             }
           }
         }
       }
-      return false;
+      timing.end();
+      return result;
     }
 
     private void fillSeenPositions(Collection<DexMethod> invokes) {
diff --git a/src/main/java/com/android/tools/r8/utils/Timing.java b/src/main/java/com/android/tools/r8/utils/Timing.java
index ff2aa68..e8cf59b 100644
--- a/src/main/java/com/android/tools/r8/utils/Timing.java
+++ b/src/main/java/com/android/tools/r8/utils/Timing.java
@@ -13,6 +13,8 @@
 // Finally a report is printed by:
 //     t.report();
 
+import java.util.LinkedHashMap;
+import java.util.Map;
 import java.util.Stack;
 
 public class Timing {
@@ -27,23 +29,28 @@
   static class Node {
     final String title;
 
-    final Stack<Node> sons = new Stack<>();
-    final long start_time;
-    long stop_time;
+    final Map<String, Node> children = new LinkedHashMap<>();
+    long duration = 0;
+    long start_time;
 
     Node(String title) {
       this.title = title;
       this.start_time = System.nanoTime();
-      this.stop_time = -1;
+    }
+
+    void restart() {
+      assert start_time == -1;
+      start_time = System.nanoTime();
     }
 
     void end() {
-      stop_time = System.nanoTime();
+      duration += System.nanoTime() - start_time;
+      start_time = -1;
       assert duration() >= 0;
     }
 
     long duration() {
-      return stop_time - start_time;
+      return duration;
     }
 
     @Override
@@ -66,15 +73,22 @@
         System.out.print("- ");
       }
       System.out.println(toString(top));
-      sons.forEach(p -> { p.report(depth + 1, top); });
+      children.values().forEach(p -> p.report(depth + 1, top));
     }
   }
 
 
   public void begin(String title) {
-    Node n = new Node(title);
-    stack.peek().sons.add(n);
-    stack.push(n);
+    Node parent = stack.peek();
+    Node child;
+    if (parent.children.containsKey(title)) {
+      child = parent.children.get(title);
+      child.restart();
+    } else {
+      child = new Node(title);
+      parent.children.put(title, child);
+    }
+    stack.push(child);
   }
 
   public void end() {
diff --git a/src/test/java/com/android/tools/r8/ir/SplitBlockTest.java b/src/test/java/com/android/tools/r8/ir/SplitBlockTest.java
index e7344a4..0cf2f53 100644
--- a/src/test/java/com/android/tools/r8/ir/SplitBlockTest.java
+++ b/src/test/java/com/android/tools/r8/ir/SplitBlockTest.java
@@ -196,7 +196,7 @@
 
   public void runCatchHandlerTest(boolean codeThrows, boolean twoGuards) throws Exception {
     final int secondBlockInstructions = 4;
-    final int initialBlockCount = 5;
+    final int initialBlockCount = 6;
     // Try split between all instructions in second block.
     for (int i = 1; i < secondBlockInstructions; i++) {
       TestApplication test = codeWithCatchHandlers(codeThrows, twoGuards);
@@ -235,7 +235,7 @@
   public void runCatchHandlerSplitThreeTest(boolean codeThrows, boolean twoGuards)
       throws Exception {
     final int secondBlockInstructions = 4;
-    final int initialBlockCount = 5;
+    final int initialBlockCount = 6;
     // Try split out all instructions in second block.
     for (int i = 1; i < secondBlockInstructions - 1; i++) {
       TestApplication test = codeWithCatchHandlers(codeThrows, twoGuards);
diff --git a/src/test/java/com/android/tools/r8/kotlin/KotlinLambdaMergingTest.java b/src/test/java/com/android/tools/r8/kotlin/KotlinLambdaMergingTest.java
index 08d43ae..e1431a6 100644
--- a/src/test/java/com/android/tools/r8/kotlin/KotlinLambdaMergingTest.java
+++ b/src/test/java/com/android/tools/r8/kotlin/KotlinLambdaMergingTest.java
@@ -31,7 +31,13 @@
       "-keepattributes InnerClasses,EnclosingMethod\n";
   private static final String KEEP_SIGNATURE_INNER_ENCLOSING =
       "-keepattributes Signature,InnerClasses,EnclosingMethod\n";
-  private Consumer<InternalOptions> optionsModifier = opts -> opts.enableClassInlining = false;
+  private Consumer<InternalOptions> optionsModifier =
+      opts -> {
+        opts.enableClassInlining = false;
+        // Ensure that enclosing method and inner class attributes are kept even on classes that are
+        // not explicitly mentioned by a keep rule.
+        opts.forceProguardCompatibility = true;
+      };
 
   abstract static class LambdaOrGroup {
     abstract boolean match(DexClass clazz);
diff --git a/src/test/java/com/android/tools/r8/maindexlist/MainDexListTests.java b/src/test/java/com/android/tools/r8/maindexlist/MainDexListTests.java
index 4214a67..101bf06 100644
--- a/src/test/java/com/android/tools/r8/maindexlist/MainDexListTests.java
+++ b/src/test/java/com/android/tools/r8/maindexlist/MainDexListTests.java
@@ -766,7 +766,7 @@
     }
 
     @Override
-    public int getMoveExceptionRegister() {
+    public int getMoveExceptionRegister(int instructionIndex) {
       throw new Unreachable();
     }
 
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 c9488b4..b6a1ac6 100644
--- a/src/test/java/com/android/tools/r8/shaking/TreeShakingTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/TreeShakingTest.java
@@ -18,6 +18,7 @@
 import com.android.tools.r8.utils.DexInspector.ClassSubject;
 import com.android.tools.r8.utils.DexInspector.FoundFieldSubject;
 import com.android.tools.r8.utils.DexInspector.FoundMethodSubject;
+import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.ListUtils;
 import com.android.tools.r8.utils.TestDescriptionWatcher;
 import com.google.common.collect.ImmutableList;
@@ -94,7 +95,8 @@
       String programFile,
       List<Path> jarLibraries,
       MinifyMode minify,
-      List<String> keepRulesFiles)
+      List<String> keepRulesFiles,
+      Consumer<InternalOptions> optionsConsumer)
       throws Exception {
     out = temp.getRoot().toPath().resolve("out.zip");
     proguardMap = temp.getRoot().toPath().resolve(DEFAULT_PROGUARD_MAP_FILE);
@@ -125,7 +127,14 @@
         throw new Unreachable();
     }
     ToolHelper.getAppBuilder(builder).addProgramFiles(Paths.get(programFile));
-    ToolHelper.runR8(builder.build(), options -> options.enableInlining = inline);
+    ToolHelper.runR8(
+        builder.build(),
+        options -> {
+          options.enableInlining = inline;
+          if (optionsConsumer != null) {
+            optionsConsumer.accept(options);
+          }
+        });
   }
 
   protected static void checkSameStructure(DexInspector ref, DexInspector inspector) {
@@ -163,6 +172,16 @@
       BiConsumer<DexInspector, DexInspector> dexComparator,
       List<String> keepRulesFiles)
       throws Exception {
+    runTest(inspection, outputComparator, dexComparator, keepRulesFiles, null);
+  }
+
+  protected void runTest(
+      Consumer<DexInspector> inspection,
+      BiConsumer<String, String> outputComparator,
+      BiConsumer<DexInspector, DexInspector> dexComparator,
+      List<String> keepRulesFiles,
+      Consumer<InternalOptions> optionsConsumer)
+      throws Exception {
     String originalDex = ToolHelper.TESTS_BUILD_DIR + name + "/classes.dex";
     String programFile;
     if (frontend == Frontend.DEX) {
@@ -183,7 +202,8 @@
               Paths.get(ToolHelper.EXAMPLES_BUILD_DIR + "shakinglib.jar"));
     }
 
-    generateTreeShakedVersion(backend, programFile, jarLibraries, minify, keepRulesFiles);
+    generateTreeShakedVersion(
+        backend, programFile, jarLibraries, minify, keepRulesFiles, optionsConsumer);
 
     if (backend == Backend.CF) {
       Path shakinglib = Paths.get(ToolHelper.EXAMPLES_BUILD_DIR, "shakinglib.jar");
diff --git a/src/test/java/com/android/tools/r8/shaking/examples/TreeShakingAnnotationremovalTest.java b/src/test/java/com/android/tools/r8/shaking/examples/TreeShakingAnnotationremovalTest.java
index d18210c..a235df5 100644
--- a/src/test/java/com/android/tools/r8/shaking/examples/TreeShakingAnnotationremovalTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/examples/TreeShakingAnnotationremovalTest.java
@@ -46,7 +46,12 @@
         TreeShakingAnnotationremovalTest::annotationRemovalHasNoInnerClassAnnotations,
         null,
         null,
-        ImmutableList.of("src/test/examples/annotationremoval/keep-rules.txt"));
+        ImmutableList.of("src/test/examples/annotationremoval/keep-rules.txt"),
+        options -> {
+          // To ensure that enclosing method and inner class attributes are kept even on classes
+          // that are not explicitly mentioned by a keep rule.
+          options.forceProguardCompatibility = true;
+        });
   }
 
   @Test
@@ -55,8 +60,12 @@
         TreeShakingAnnotationremovalTest::annotationRemovalHasAllInnerClassAnnotations,
         null,
         null,
-        ImmutableList.of(
-            "src/test/examples/annotationremoval/keep-rules-keep-innerannotation.txt"));
+        ImmutableList.of("src/test/examples/annotationremoval/keep-rules-keep-innerannotation.txt"),
+        options -> {
+          // To ensure that enclosing method and inner class attributes are kept even on classes
+          // that are not explicitly mentioned by a keep rule.
+          options.forceProguardCompatibility = true;
+        });
   }
 
   private static void annotationRemovalHasNoInnerClassAnnotations(DexInspector inspector) {
diff --git a/third_party/gmail/gmail_android_170604.16.tar.gz.sha1 b/third_party/gmail/gmail_android_170604.16.tar.gz.sha1
index f57ba90..9d9985c 100644
--- a/third_party/gmail/gmail_android_170604.16.tar.gz.sha1
+++ b/third_party/gmail/gmail_android_170604.16.tar.gz.sha1
@@ -1 +1 @@
-161c569821a5c9b4cb8e99de764f3449191af084
\ No newline at end of file
+a6d49ef4fb2094672a6f6be039c971727cc9fd34
\ No newline at end of file
diff --git a/third_party/youtube/youtube.android_12.22.tar.gz.sha1 b/third_party/youtube/youtube.android_12.22.tar.gz.sha1
index 8f6813c..056ff59 100644
--- a/third_party/youtube/youtube.android_12.22.tar.gz.sha1
+++ b/third_party/youtube/youtube.android_12.22.tar.gz.sha1
@@ -1 +1 @@
-73c4880898d734064815d0426d8fe84ee6d075b4
\ No newline at end of file
+57b5c53a80ba010d1faef7da1b643f8c72b3e4e8
\ No newline at end of file
diff --git a/tools/build_sample_apk.py b/tools/build_sample_apk.py
index b31ade4..90e34ed 100755
--- a/tools/build_sample_apk.py
+++ b/tools/build_sample_apk.py
@@ -13,7 +13,9 @@
 import shutil
 import subprocess
 import sys
+import time
 import utils
+import uuid
 
 ANDROID_JAR = 'third_party/android_jar/lib-v{api}/android.jar'
 DEFAULT_AAPT = 'aapt' # Assume in path.
@@ -22,6 +24,9 @@
 DEFAULT_JAVAC = 'javac'
 SRC_LOCATION = 'src/com/android/tools/r8/sample/{app}/*.java'
 DEFAULT_KEYSTORE = os.path.join(os.getenv('HOME'), '.android', 'debug.keystore')
+PACKAGE_PREFIX = 'com.android.tools.r8.sample'
+STANDARD_ACTIVITY = "R8Activity"
+BENCHMARK_ITERATIONS = 100
 
 SAMPLE_APKS = [
     'simple',
@@ -46,6 +51,12 @@
   result.add_option('--install',
                     help='Install the app (including featuresplit)',
                     default=False, action='store_true')
+  result.add_option('--benchmark',
+                    help='Benchmark the app on the phone with specialized markers',
+                    default=False, action='store_true')
+  result.add_option('--benchmark-output-dir',
+                    help='Store benchmark results here.',
+                    default=None)
   result.add_option('--app',
                     help='Which app to build',
                     default='simple',
@@ -86,6 +97,13 @@
 def get_split_path(app, split):
   return os.path.join(get_bin_path(app), split, 'classes.dex')
 
+def get_package_name(app):
+  return '%s.%s' % (PACKAGE_PREFIX, app)
+
+def get_qualified_activity(app):
+  # The activity specified to adb start is PACKAGE_NAME/.ACTIVITY
+  return '%s/.%s' % (get_package_name(app), STANDARD_ACTIVITY)
+
 def run_aapt_pack(aapt, api, app):
   with utils.ChangedWorkingDirectory(get_sample_dir(app)):
     args = ['package',
@@ -169,6 +187,71 @@
           dex]
   run_aapt(aapt, args)
 
+def kill(app):
+  args = ['shell', 'am', 'force-stop', get_package_name(app)]
+  run_adb(args)
+
+def start_logcat():
+  return subprocess.Popen(['adb', 'logcat'], stdout=subprocess.PIPE, stderr=subprocess.PIPE)
+
+def start(app):
+  args = ['shell', 'am', 'start', '-n', get_qualified_activity(app)]
+  run_adb(args)
+
+def clear_logcat():
+  args = ['logcat', '-c']
+  run_adb(args)
+
+def stop_logcat(popen):
+  popen.terminate()
+  lines = []
+  for l in popen.stdout:
+    if 'System.out' in l:
+      lines.append(l)
+  return lines
+
+def store_or_print_benchmarks(lines, output):
+  single_runs = []
+  total_time = None
+  # We assume that the individual runs are prefixed with 'Took: ' and the total time is
+  # prefixed with 'Total: '. The logcat lines looks like:
+  # 06-28 12:22:00.991 13698 13698 I System.out: Took: 61614
+  for l in lines:
+    if 'Took: ' in l:
+      timing = l.split('Took: ')[1]
+      single_runs.append(timing)
+    if 'Total: ' in l:
+      timing = l.split('Total: ')[1]
+      total_time = timing
+  assert len(single_runs) > 0
+  assert total_time
+  if not output:
+    print 'Individual timings: \n%s' % ''.join(single_runs)
+    print 'Total time: \n%s' % total_time
+    return
+
+  output_dir = os.path.join(output, str(uuid.uuid4()))
+  os.makedirs(output_dir)
+  single_run_file = os.path.join(output_dir, 'single_runs')
+  with open(single_run_file, 'w') as f:
+    f.writelines(single_runs)
+  total_file = os.path.join(output_dir, 'total')
+  with open(total_file, 'w') as f:
+    f.write(total_time)
+  print 'Result stored in %s and %s' % (single_run_file, total_file)
+
+def benchmark(app, output_dir):
+  # Ensure app is not running
+  kill(app)
+  clear_logcat()
+  logcat = start_logcat()
+  start(app)
+  # We could do better here by continiously parsing the logcat for a marker, but
+  # this works nicely with the current setup.
+  time.sleep(3)
+  kill(app)
+  store_or_print_benchmarks(stop_logcat(logcat), output_dir)
+
 def Main():
   (options, args) = parse_options()
   apks = []
@@ -202,7 +285,9 @@
   print('Generated apks available at: %s' % ' '.join(apks))
   if options.install:
     adb_install(apks)
-
+  if options.benchmark:
+    for _ in range(BENCHMARK_ITERATIONS):
+      benchmark(options.app, options.benchmark_output_dir)
 
 if __name__ == '__main__':
   sys.exit(Main())
diff --git a/tools/run_bootstrap_benchmark.py b/tools/run_bootstrap_benchmark.py
index 8230c71..bfc62e6 100755
--- a/tools/run_bootstrap_benchmark.py
+++ b/tools/run_bootstrap_benchmark.py
@@ -49,7 +49,7 @@
     print "BootstrapR8Dex(CodeSize):", os.path.getsize(d8_r8_output)
 
     dex(PINNED_PGR8_JAR, d8_pg_output)
-    print "BootstrapPG(CodeSize):", os.path.getsize(PINNED_PGR8_JAR)
-    print "BootstrapPGDex(CodeSize):", os.path.getsize(d8_pg_output)
+    print "BootstrapR8PG(CodeSize):", os.path.getsize(PINNED_PGR8_JAR)
+    print "BootstrapR8PGDex(CodeSize):", os.path.getsize(d8_pg_output)
 
-  sys.exit(0)
\ No newline at end of file
+  sys.exit(0)