diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index e08e8fb..fcc7076 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -1654,21 +1654,77 @@
   // iteration.
   DCHECK(dominated_blocks_.empty());
 
-  // (1) Remove the block from all loops it is included in.
-  for (HLoopInformationOutwardIterator it(*this); !it.Done(); it.Advance()) {
-    HLoopInformation* loop_info = it.Current();
-    loop_info->Remove(this);
-    if (loop_info->IsBackEdge(*this)) {
-      // If this was the last back edge of the loop, we deliberately leave the
-      // loop in an inconsistent state and will fail GraphChecker unless the
-      // entire loop is removed during the pass.
-      loop_info->RemoveBackEdge(this);
-    }
+  // The following steps gradually remove the block from all its dependants in
+  // post order (b/27683071).
+
+  // (1) Store a basic block that we'll use in step (5) to find loops to be updated.
+  //     We need to do this before step (4) which destroys the predecessor list.
+  HBasicBlock* loop_update_start = this;
+  if (IsLoopHeader()) {
+    HLoopInformation* loop_info = GetLoopInformation();
+    // All other blocks in this loop should have been removed because the header
+    // was their dominator.
+    // Note that we do not remove `this` from `loop_info` as it is unreachable.
+    DCHECK(!loop_info->IsIrreducible());
+    DCHECK_EQ(loop_info->GetBlocks().NumSetBits(), 1u);
+    DCHECK_EQ(static_cast<uint32_t>(loop_info->GetBlocks().GetHighestBitSet()), GetBlockId());
+    loop_update_start = loop_info->GetPreHeader();
   }
 
-  // (2) Disconnect the block from its predecessors and update their
+  // (2) Disconnect the block from its successors and update their phis.
+  for (HBasicBlock* successor : successors_) {
+    // Delete this block from the list of predecessors.
+    size_t this_index = successor->GetPredecessorIndexOf(this);
+    successor->predecessors_.erase(successor->predecessors_.begin() + this_index);
+
+    // Check that `successor` has other predecessors, otherwise `this` is the
+    // dominator of `successor` which violates the order DCHECKed at the top.
+    DCHECK(!successor->predecessors_.empty());
+
+    // Remove this block's entries in the successor's phis. Skip exceptional
+    // successors because catch phi inputs do not correspond to predecessor
+    // blocks but throwing instructions. The inputs of the catch phis will be
+    // updated in step (3).
+    if (!successor->IsCatchBlock()) {
+      if (successor->predecessors_.size() == 1u) {
+        // The successor has just one predecessor left. Replace phis with the only
+        // remaining input.
+        for (HInstructionIterator phi_it(successor->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
+          HPhi* phi = phi_it.Current()->AsPhi();
+          phi->ReplaceWith(phi->InputAt(1 - this_index));
+          successor->RemovePhi(phi);
+        }
+      } else {
+        for (HInstructionIterator phi_it(successor->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
+          phi_it.Current()->AsPhi()->RemoveInputAt(this_index);
+        }
+      }
+    }
+  }
+  successors_.clear();
+
+  // (3) Remove instructions and phis. Instructions should have no remaining uses
+  //     except in catch phis. If an instruction is used by a catch phi at `index`,
+  //     remove `index`-th input of all phis in the catch block since they are
+  //     guaranteed dead. Note that we may miss dead inputs this way but the
+  //     graph will always remain consistent.
+  for (HBackwardInstructionIterator it(GetInstructions()); !it.Done(); it.Advance()) {
+    HInstruction* insn = it.Current();
+    RemoveUsesOfDeadInstruction(insn);
+    RemoveInstruction(insn);
+  }
+  for (HInstructionIterator it(GetPhis()); !it.Done(); it.Advance()) {
+    HPhi* insn = it.Current()->AsPhi();
+    RemoveUsesOfDeadInstruction(insn);
+    RemovePhi(insn);
+  }
+
+  // (4) Disconnect the block from its predecessors and update their
   //     control-flow instructions.
   for (HBasicBlock* predecessor : predecessors_) {
+    // We should not see any back edges as they would have been removed by step (3).
+    DCHECK(!IsInLoop() || !GetLoopInformation()->IsBackEdge(*predecessor));
+
     HInstruction* last_instruction = predecessor->GetLastInstruction();
     if (last_instruction->IsTryBoundary() && !IsCatchBlock()) {
       // This block is the only normal-flow successor of the TryBoundary which
@@ -1712,58 +1768,25 @@
   }
   predecessors_.clear();
 
-  // (3) Disconnect the block from its successors and update their phis.
-  for (HBasicBlock* successor : successors_) {
-    // Delete this block from the list of predecessors.
-    size_t this_index = successor->GetPredecessorIndexOf(this);
-    successor->predecessors_.erase(successor->predecessors_.begin() + this_index);
-
-    // Check that `successor` has other predecessors, otherwise `this` is the
-    // dominator of `successor` which violates the order DCHECKed at the top.
-    DCHECK(!successor->predecessors_.empty());
-
-    // Remove this block's entries in the successor's phis. Skip exceptional
-    // successors because catch phi inputs do not correspond to predecessor
-    // blocks but throwing instructions. Their inputs will be updated in step (4).
-    if (!successor->IsCatchBlock()) {
-      if (successor->predecessors_.size() == 1u) {
-        // The successor has just one predecessor left. Replace phis with the only
-        // remaining input.
-        for (HInstructionIterator phi_it(successor->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
-          HPhi* phi = phi_it.Current()->AsPhi();
-          phi->ReplaceWith(phi->InputAt(1 - this_index));
-          successor->RemovePhi(phi);
-        }
-      } else {
-        for (HInstructionIterator phi_it(successor->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
-          phi_it.Current()->AsPhi()->RemoveInputAt(this_index);
-        }
-      }
+  // (5) Remove the block from all loops it is included in. Skip the inner-most
+  //     loop if this is the loop header (see definition of `loop_update_start`)
+  //     because the loop header's predecessor list has been destroyed in step (4).
+  for (HLoopInformationOutwardIterator it(*loop_update_start); !it.Done(); it.Advance()) {
+    HLoopInformation* loop_info = it.Current();
+    loop_info->Remove(this);
+    if (loop_info->IsBackEdge(*this)) {
+      // If this was the last back edge of the loop, we deliberately leave the
+      // loop in an inconsistent state and will fail GraphChecker unless the
+      // entire loop is removed during the pass.
+      loop_info->RemoveBackEdge(this);
     }
   }
-  successors_.clear();
 
-  // (4) Remove instructions and phis. Instructions should have no remaining uses
-  //     except in catch phis. If an instruction is used by a catch phi at `index`,
-  //     remove `index`-th input of all phis in the catch block since they are
-  //     guaranteed dead. Note that we may miss dead inputs this way but the
-  //     graph will always remain consistent.
-  for (HBackwardInstructionIterator it(GetInstructions()); !it.Done(); it.Advance()) {
-    HInstruction* insn = it.Current();
-    RemoveUsesOfDeadInstruction(insn);
-    RemoveInstruction(insn);
-  }
-  for (HInstructionIterator it(GetPhis()); !it.Done(); it.Advance()) {
-    HPhi* insn = it.Current()->AsPhi();
-    RemoveUsesOfDeadInstruction(insn);
-    RemovePhi(insn);
-  }
-
-  // Disconnect from the dominator.
+  // (6) Disconnect from the dominator.
   dominator_->RemoveDominatedBlock(this);
   SetDominator(nullptr);
 
-  // Delete from the graph, update reverse post order.
+  // (7) Delete from the graph, update reverse post order.
   graph_->DeleteDeadEmptyBlock(this);
   SetGraph(nullptr);
 }