diff --git a/compiler/optimizing/dominator_test.cc b/compiler/optimizing/dominator_test.cc
index 7623e42..61a7697 100644
--- a/compiler/optimizing/dominator_test.cc
+++ b/compiler/optimizing/dominator_test.cc
@@ -36,7 +36,13 @@
   ASSERT_EQ(graph->GetBlocks().Size(), blocks_length);
   for (size_t i = 0, e = blocks_length; i < e; ++i) {
     if (blocks[i] == -1) {
-      ASSERT_EQ(nullptr, graph->GetBlocks().Get(i)->GetDominator());
+      if (graph->GetBlocks().Get(i) == nullptr) {
+        // Dead block.
+      } else {
+        // Only the entry block has no dominator.
+        ASSERT_EQ(nullptr, graph->GetBlocks().Get(i)->GetDominator());
+        ASSERT_TRUE(graph->GetBlocks().Get(i)->IsEntryBlock());
+      }
     } else {
       ASSERT_NE(nullptr, graph->GetBlocks().Get(i)->GetDominator());
       ASSERT_EQ(blocks[i], graph->GetBlocks().Get(i)->GetDominator()->GetBlockId());
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index d8a8554..ada3487 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -51,9 +51,7 @@
   for (size_t i = 0; i < blocks_.Size(); ++i) {
     if (!visited.IsBitSet(i)) {
       HBasicBlock* block = blocks_.Get(i);
-      for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
-        RemoveAsUser(it.Current());
-      }
+      DCHECK(block->GetPhis().IsEmpty()) << "Phis are not inserted at this stage";
       for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
         RemoveAsUser(it.Current());
       }
@@ -61,19 +59,17 @@
   }
 }
 
-void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) const {
+void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) {
   for (size_t i = 0; i < blocks_.Size(); ++i) {
     if (!visited.IsBitSet(i)) {
       HBasicBlock* block = blocks_.Get(i);
+      // We only need to update the successor, which might be live.
       for (size_t j = 0; j < block->GetSuccessors().Size(); ++j) {
         block->GetSuccessors().Get(j)->RemovePredecessor(block);
       }
-      for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
-        block->RemovePhi(it.Current()->AsPhi(), /*ensure_safety=*/ false);
-      }
-      for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
-        block->RemoveInstruction(it.Current(), /*ensure_safety=*/ false);
-      }
+      // Remove the block from the list of blocks, so that further analyses
+      // never see it.
+      blocks_.Put(i, nullptr);
     }
   }
 }
@@ -258,6 +254,7 @@
   // (2): Simplify loops by having only one back edge, and one preheader.
   for (size_t i = 0; i < blocks_.Size(); ++i) {
     HBasicBlock* block = blocks_.Get(i);
+    if (block == nullptr) continue;
     if (block->GetSuccessors().Size() > 1) {
       for (size_t j = 0; j < block->GetSuccessors().Size(); ++j) {
         HBasicBlock* successor = block->GetSuccessors().Get(j);
@@ -274,8 +271,9 @@
 }
 
 bool HGraph::AnalyzeNaturalLoops() const {
-  for (size_t i = 0; i < blocks_.Size(); ++i) {
-    HBasicBlock* block = blocks_.Get(i);
+  // Order does not matter.
+  for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
+    HBasicBlock* block = it.Current();
     if (block->IsLoopHeader()) {
       HLoopInformation* info = block->GetLoopInformation();
       if (!info->Populate()) {
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 539e0b5..4bca9aa 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -253,7 +253,7 @@
                               ArenaBitVector* visited,
                               ArenaBitVector* visiting);
   void RemoveInstructionsAsUsersFromDeadBlocks(const ArenaBitVector& visited) const;
-  void RemoveDeadBlocks(const ArenaBitVector& visited) const;
+  void RemoveDeadBlocks(const ArenaBitVector& visited);
 
   template <class InstType, typename ValueType>
   InstType* CreateConstant(ValueType value, ArenaSafeMap<ValueType, InstType*>* cache);
diff --git a/test/473-remove-dead-block/expected.txt b/test/473-remove-dead-block/expected.txt
new file mode 100644
index 0000000..c09201e
--- /dev/null
+++ b/test/473-remove-dead-block/expected.txt
@@ -0,0 +1 @@
+123368133
diff --git a/test/473-remove-dead-block/info.txt b/test/473-remove-dead-block/info.txt
new file mode 100644
index 0000000..81de4e6
--- /dev/null
+++ b/test/473-remove-dead-block/info.txt
@@ -0,0 +1,3 @@
+Regression test for optimizing's dead block removing:
+Removing from predecessors require remove successor otherwise
+CFG remains in an unexpected shape causing further crash of compiler.
diff --git a/test/473-remove-dead-block/src/Main.java b/test/473-remove-dead-block/src/Main.java
new file mode 100644
index 0000000..cca2976
--- /dev/null
+++ b/test/473-remove-dead-block/src/Main.java
@@ -0,0 +1,42 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+class Main {
+  public static void main(String[] args) {
+    System.out.println(test(false, 5));
+  }
+
+  public static int test(boolean b, int i1) {
+    int j=4;
+    int s1=26294;
+
+    for (int i = 25; i > 1; --i) {
+      if (b) continue;
+      // javac/dx will remove the catch information, but
+      // keep the catch code around. The optimizing compiler
+      // used to crash in the presence of dead blocks like the
+      // code in catch.
+      try {
+        i1 = i1 * 26295 + (s1 / 26295);
+      } catch (Throwable exc2) {
+        for (j = 1; j < 39; ++j) {
+          j++;
+        }
+      }
+    }
+    return i1;
+  }
+}