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 3d30b23..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
@@ -161,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/IRBuilder.java b/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java
index 6735863..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<>();
@@ -364,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();
@@ -430,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();
@@ -546,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.
@@ -581,7 +602,6 @@
     BasicBlock targetBlock = getTarget(moveExceptionItem.targetOffset);
     currentBlock.link(targetBlock);
     addToWorklist(targetBlock, targetIndex);
-    closeCurrentBlock();
   }
 
   // Helper to resolve switch payloads and build switch instructions (dex code only).
@@ -1502,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) {
@@ -1794,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);
   }
 
@@ -1886,6 +1929,7 @@
         info = new BlockInfo();
       }
       targets.put(offset, info);
+      offsets.put(info.block, offset);
     }
     return info;
   }
@@ -1959,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.
@@ -1973,6 +2029,33 @@
     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());