diff --git a/src/main/java/com/android/tools/r8/Version.java b/src/main/java/com/android/tools/r8/Version.java
index 5344a61..74b730d 100644
--- a/src/main/java/com/android/tools/r8/Version.java
+++ b/src/main/java/com/android/tools/r8/Version.java
@@ -11,7 +11,7 @@
 
   // This field is accessed from release scripts using simple pattern matching.
   // Therefore, changing this field could break our release scripts.
-  public static final String LABEL = "v1.0.1";
+  public static final String LABEL = "v1.0.2";
 
   private Version() {
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java b/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
index 1e076dd..d6fcd3c 100644
--- a/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
+++ b/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
@@ -30,7 +30,6 @@
 import java.util.Map;
 import java.util.Map.Entry;
 import java.util.Set;
-import java.util.TreeSet;
 import java.util.function.Consumer;
 import java.util.function.Function;
 
@@ -553,34 +552,28 @@
     assert successors.contains(successor);
     assert successor.predecessors.contains(this);
     List<BasicBlock> removedBlocks = new ArrayList<>();
-    TreeSet<Pair> worklist = new TreeSet<>();
-    worklist.add(new Pair(this, successor));
-    while (!worklist.isEmpty()) {
-      Pair pair = worklist.pollFirst();
-      BasicBlock pred = pair.first;
-      BasicBlock succ = pair.second;
-      assert pred.successors.contains(succ);
-      assert succ.predecessors.contains(pred);
-      int size = pred.successors.size();
-      pred.removeSuccessor(succ);
-      assert size == pred.successors.size() + 1;
-      size = succ.predecessors.size();
-      succ.removePredecessor(pred);
-      assert size == succ.predecessors.size() + 1;
-      // A predecessor has been removed. If all remaining predecessors are dominated by this block
-      // schedule it for removal, as it is no longer reachable.
-      if (allPredecessorsDominated(succ, dominator)) {
-        removedBlocks.add(succ);
-        for (BasicBlock block : succ.successors) {
-          worklist.add(new Pair(succ, block));
+    for (BasicBlock dominated : dominator.dominatedBlocks(successor)) {
+      removedBlocks.add(dominated);
+      for (BasicBlock block : dominated.successors) {
+        block.removePredecessor(dominated);
+      }
+      dominated.successors.clear();
+      for (BasicBlock block : dominated.predecessors) {
+        block.removeSuccessor(dominated);
+      }
+      dominated.predecessors.clear();
+      for (Phi phi : dominated.getPhis()) {
+        for (Value operand : phi.getOperands()) {
+          operand.removePhiUser(phi);
         }
-        for (Instruction instruction : succ.getInstructions()) {
-          for (Value value : instruction.inValues) {
-            value.removeUser(instruction);
-          }
-          for (Value value : instruction.getDebugValues()) {
-            value.removeDebugUser(instruction);
-          }
+      }
+      dominated.getPhis().clear();
+      for (Instruction instruction : dominated.getInstructions()) {
+        for (Value value : instruction.inValues) {
+          value.removeUser(instruction);
+        }
+        for (Value value : instruction.getDebugValues()) {
+          value.removeDebugUser(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 eeb843c..0b3b021 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
@@ -1700,8 +1700,6 @@
   }
 
   public void simplifyIf(IRCode code) {
-    Supplier<DominatorTree> dominatorTreeMemoization = Suppliers
-        .memoize(() -> new DominatorTree(code));
     int color = code.reserveMarkingColor();
     for (BasicBlock block : code.blocks) {
       if (block.isMarked(color)) {
@@ -1711,7 +1709,7 @@
         // First rewrite zero comparison.
         rewriteIfWithConstZero(block);
 
-        if (simplifyKnownBooleanCondition(code, dominatorTreeMemoization, block, color)) {
+        if (simplifyKnownBooleanCondition(code, block, color)) {
           continue;
         }
 
@@ -1757,7 +1755,7 @@
         BasicBlock target = theIf.targetFromCondition(cond);
         BasicBlock deadTarget =
             target == theIf.getTrueTarget() ? theIf.fallthroughBlock() : theIf.getTrueTarget();
-        rewriteIfToGoto(dominatorTreeMemoization, block, theIf, target, deadTarget, color);
+        rewriteIfToGoto(code, block, theIf, target, deadTarget, color);
       }
     }
     code.removeMarkedBlocks(color);
@@ -1796,8 +1794,7 @@
    * which can be replaced by a fallthrough and the phi value can be replaced
    * by an xor instruction which is smaller.
    */
-  private boolean simplifyKnownBooleanCondition(IRCode code,
-      Supplier<DominatorTree> dominatorTreeMemoization, BasicBlock block, int color) {
+  private boolean simplifyKnownBooleanCondition(IRCode code, BasicBlock block, int color) {
     If theIf = block.exit().asIf();
     Value testValue = theIf.inValues().get(0);
     if (theIf.isZeroTest() && testValue.knownToBeBoolean()) {
@@ -1859,7 +1856,7 @@
           // If all phis were removed, there is no need for the diamond shape anymore
           // and it can be rewritten to a goto to one of the branches.
           if (deadPhis == targetBlock.getPhis().size()) {
-            rewriteIfToGoto(dominatorTreeMemoization, block, theIf, trueBlock, falseBlock, color);
+            rewriteIfToGoto(code, block, theIf, trueBlock, falseBlock, color);
             return true;
           }
         }
@@ -1901,9 +1898,10 @@
     return false;
   }
 
-  private void rewriteIfToGoto(Supplier<DominatorTree> dominatorTreeMemoization, BasicBlock block,
+  private void rewriteIfToGoto(IRCode code, BasicBlock block,
       If theIf, BasicBlock target, BasicBlock deadTarget, int color) {
-    List<BasicBlock> removedBlocks = block.unlink(deadTarget, dominatorTreeMemoization.get());
+    DominatorTree dominatorTree = new DominatorTree(code);
+    List<BasicBlock> removedBlocks = block.unlink(deadTarget, dominatorTree);
     for (BasicBlock removedBlock : removedBlocks) {
       if (!removedBlock.isMarked(color)) {
         removedBlock.mark(color);
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/DeadCodeRemover.java b/src/main/java/com/android/tools/r8/ir/optimize/DeadCodeRemover.java
index 88f9e63..5144704 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/DeadCodeRemover.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/DeadCodeRemover.java
@@ -12,19 +12,15 @@
 import com.android.tools.r8.ir.code.Phi;
 import com.android.tools.r8.ir.code.Value;
 import com.android.tools.r8.utils.InternalOptions;
-import com.google.common.base.Suppliers;
 import java.util.Iterator;
 import java.util.LinkedList;
 import java.util.Queue;
-import java.util.function.Supplier;
 
 public class DeadCodeRemover {
 
   public static void removeDeadCode(
       IRCode code, CodeRewriter codeRewriter, InternalOptions options) {
     Queue<BasicBlock> worklist = new LinkedList<>();
-    Supplier<DominatorTree> dominatorTreeMemoization = Suppliers
-        .memoize(() -> new DominatorTree(code));
     int color = code.reserveMarkingColor();
     worklist.addAll(code.blocks);
     for (BasicBlock block = worklist.poll(); block != null; block = worklist.poll()) {
@@ -34,7 +30,7 @@
       }
       removeDeadInstructions(worklist, code, block, options, color);
       removeDeadPhis(worklist, block, options, color);
-      removeUnneededCatchHandlers(worklist, block, dominatorTreeMemoization, color);
+      removeUnneededCatchHandlers(worklist, block, code, color);
     }
     code.removeMarkedBlocks(color);
     code.returnMarkingColor(color);
@@ -113,11 +109,12 @@
   }
 
   private static void removeUnneededCatchHandlers(Queue<BasicBlock> worklist, BasicBlock block,
-      Supplier<DominatorTree> dominatorTreeMemoization, int color) {
+      IRCode code, int color) {
     if (block.hasCatchHandlers() && !block.canThrow()) {
       CatchHandlers<BasicBlock> handlers = block.getCatchHandlers();
       for (BasicBlock target : handlers.getUniqueTargets()) {
-        for (BasicBlock unlinked : block.unlink(target, dominatorTreeMemoization.get())) {
+        DominatorTree dominatorTree = new DominatorTree(code);
+        for (BasicBlock unlinked : block.unlink(target, dominatorTree)) {
           if (!unlinked.isMarked(color)) {
             Iterator<Instruction> iterator = unlinked.iterator();
             while (iterator.hasNext()) {
diff --git a/src/test/java/com/android/tools/r8/jasmin/Regress72269635.java b/src/test/java/com/android/tools/r8/jasmin/Regress72269635.java
new file mode 100644
index 0000000..e92b8a9
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/jasmin/Regress72269635.java
@@ -0,0 +1,63 @@
+// Copyright (c) 2018, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.jasmin;
+
+import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.jasmin.JasminBuilder.ClassFileVersion;
+import com.android.tools.r8.naming.MemberNaming.MethodSignature;
+import com.android.tools.r8.utils.AndroidApp;
+import com.google.common.collect.ImmutableList;
+import org.junit.Test;
+
+public class Regress72269635 extends JasminTestBase {
+
+  @Test
+  public void testDeadBlocksRemoved() throws Exception {
+    JasminBuilder builder = new JasminBuilder(ClassFileVersion.JDK_1_4);
+    JasminBuilder.ClassBuilder clazz = builder.addClass("Test");
+
+    clazz.addStaticMethod("test", ImmutableList.of("IIII"), "J",
+        ".limit stack 3",
+        ".limit locals 5",
+        "L0:",
+        "  iconst_2",
+        "  ifge L0",
+        "L48:",
+        "  iload 3",
+        "  ifle L48",
+        "  goto L209",
+        "  aconst_null",
+        "  athrow",
+        "L209:",
+        "  aconst_null",
+        "  iconst_2",
+        "  newarray float",
+        "  if_acmpne L250",
+        "L240:",
+        "  iload 3",
+        "  pop",
+        "L250:",
+        "  iload 3",
+        "  ifgt L240",
+        "  iload 3",
+        "  istore 0",
+        "  goto L357",
+        "L318:",
+        "  iinc 0 1",
+        "L351:",
+        "  iinc 0 1",
+        "  goto L351",
+        "L357:",
+        "  iinc 0 1",
+        "L415:",
+        "  iinc 0 1",
+        "  goto L415"
+    );
+
+    // Just compiling this code used to throw exceptions because not all dead blocks
+    // were removed.
+    AndroidApp originalApplication = builder.build();
+    ToolHelper.runD8(originalApplication);
+  }
+}