diff --git a/compiler/dex/bb_optimizations.h b/compiler/dex/bb_optimizations.h
index b386334..b07a415 100644
--- a/compiler/dex/bb_optimizations.h
+++ b/compiler/dex/bb_optimizations.h
@@ -284,7 +284,8 @@
  */
 class BBOptimizations : public PassME {
  public:
-  BBOptimizations() : PassME("BBOptimizations", kNoNodes, "5_post_bbo_cfg") {
+  BBOptimizations()
+      : PassME("BBOptimizations", kNoNodes, kOptimizationBasicBlockChange, "5_post_bbo_cfg") {
   }
 
   bool Gate(const PassDataHolder* data) const {
@@ -314,6 +315,7 @@
     CompilationUnit* c_unit = down_cast<const PassMEDataHolder*>(data)->c_unit;
     DCHECK(c_unit != nullptr);
     c_unit->mir_graph->BasicBlockOptimizationEnd();
+    down_cast<PassMEDataHolder*>(data)->dirty = !c_unit->mir_graph->DfsOrdersUpToDate();
   }
 };
 
diff --git a/compiler/dex/mir_graph.cc b/compiler/dex/mir_graph.cc
index 72ad1e6..8b73863 100644
--- a/compiler/dex/mir_graph.cc
+++ b/compiler/dex/mir_graph.cc
@@ -2250,12 +2250,6 @@
   }
   predecessors.clear();
 
-  KillUnreachable(mir_graph);
-}
-
-void BasicBlock::KillUnreachable(MIRGraph* mir_graph) {
-  DCHECK(predecessors.empty());  // Unreachable.
-
   // Mark as dead and hidden.
   block_type = kDead;
   hidden = true;
@@ -2274,9 +2268,6 @@
   ChildBlockIterator iter(this, mir_graph);
   for (BasicBlock* succ_bb = iter.Next(); succ_bb != nullptr; succ_bb = iter.Next()) {
     succ_bb->ErasePredecessor(id);
-    if (succ_bb->predecessors.empty()) {
-      succ_bb->KillUnreachable(mir_graph);
-    }
   }
 
   // Remove links to children.
diff --git a/compiler/dex/mir_graph.h b/compiler/dex/mir_graph.h
index 5c5d229..23bdd87 100644
--- a/compiler/dex/mir_graph.h
+++ b/compiler/dex/mir_graph.h
@@ -410,18 +410,12 @@
 
   /**
    * @brief Kill the BasicBlock.
-   * @details Unlink predecessors to make this block unreachable, then KillUnreachable().
+   * @details Unlink predecessors and successors, remove all MIRs, set the block type to kDead
+   *          and set hidden to true.
    */
   void Kill(MIRGraph* mir_graph);
 
   /**
-   * @brief Kill the unreachable block and all blocks that become unreachable by killing this one.
-   * @details Set the block type to kDead and set hidden to true, remove all MIRs,
-   *          unlink all successors and recursively kill successors that become unreachable.
-   */
-  void KillUnreachable(MIRGraph* mir_graph);
-
-  /**
    * @brief Is ssa_reg the last SSA definition of that VR in the block?
    */
   bool IsSSALiveOut(const CompilationUnit* c_unit, int ssa_reg);
diff --git a/compiler/dex/mir_optimization.cc b/compiler/dex/mir_optimization.cc
index e00dea7..51511ee 100644
--- a/compiler/dex/mir_optimization.cc
+++ b/compiler/dex/mir_optimization.cc
@@ -485,9 +485,11 @@
             mir->ssa_rep->num_uses = 0;
             BasicBlock* successor_to_unlink = GetBasicBlock(edge_to_kill);
             successor_to_unlink->ErasePredecessor(bb->id);
-            if (successor_to_unlink->predecessors.empty()) {
-              successor_to_unlink->KillUnreachable(this);
-            }
+            // We have changed the graph structure.
+            dfs_orders_up_to_date_ = false;
+            domination_up_to_date_ = false;
+            topological_order_up_to_date_ = false;
+            // Keep MIR SSA rep, the worst that can happen is a Phi with just 1 input.
           }
           break;
         case Instruction::CMPL_FLOAT:
@@ -649,36 +651,36 @@
                * Phi node only contains our two cases as input, we will use the result
                * SSA name of the Phi node as our select result and delete the Phi.  If
                * the Phi node has more than two operands, we will arbitrarily use the SSA
-               * name of the "true" path, delete the SSA name of the "false" path from the
+               * name of the "false" path, delete the SSA name of the "true" path from the
                * Phi node (and fix up the incoming arc list).
                */
               if (phi->ssa_rep->num_uses == 2) {
                 mir->ssa_rep->defs[0] = phi->ssa_rep->defs[0];
-                phi->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpNop);
+                // Rather than changing the Phi to kMirOpNop, remove it completely.
+                // This avoids leaving other Phis after kMirOpNop (i.e. a non-Phi) insn.
+                tk_tk->RemoveMIR(phi);
+                int dead_false_def = if_false->ssa_rep->defs[0];
+                raw_use_counts_[dead_false_def] = use_counts_[dead_false_def] = 0;
               } else {
-                int dead_def = if_false->ssa_rep->defs[0];
-                int live_def = if_true->ssa_rep->defs[0];
+                int live_def = if_false->ssa_rep->defs[0];
                 mir->ssa_rep->defs[0] = live_def;
-                BasicBlockId* incoming = phi->meta.phi_incoming;
-                for (int i = 0; i < phi->ssa_rep->num_uses; i++) {
-                  if (phi->ssa_rep->uses[i] == live_def) {
-                    incoming[i] = bb->id;
-                  }
-                }
-                for (int i = 0; i < phi->ssa_rep->num_uses; i++) {
-                  if (phi->ssa_rep->uses[i] == dead_def) {
-                    int last_slot = phi->ssa_rep->num_uses - 1;
-                    phi->ssa_rep->uses[i] = phi->ssa_rep->uses[last_slot];
-                    incoming[i] = incoming[last_slot];
-                  }
-                }
               }
-              phi->ssa_rep->num_uses--;
-              bb->taken = NullBasicBlockId;
-              tk->block_type = kDead;
-              for (MIR* tmir = ft->first_mir_insn; tmir != NULL; tmir = tmir->next) {
-                tmir->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpNop);
-              }
+              int dead_true_def = if_true->ssa_rep->defs[0];
+              raw_use_counts_[dead_true_def] = use_counts_[dead_true_def] = 0;
+              // We want to remove ft and tk and link bb directly to ft_ft. First, we need
+              // to update all Phi inputs correctly with UpdatePredecessor(ft->id, bb->id)
+              // since the live_def above comes from ft->first_mir_insn (if_false).
+              DCHECK(if_false == ft->first_mir_insn);
+              ft_ft->UpdatePredecessor(ft->id, bb->id);
+              // Correct the rest of the links between bb, ft and ft_ft.
+              ft->ErasePredecessor(bb->id);
+              ft->fall_through = NullBasicBlockId;
+              bb->fall_through = ft_ft->id;
+              // Now we can kill tk and ft.
+              tk->Kill(this);
+              ft->Kill(this);
+              // NOTE: DFS order, domination info and topological order are still usable
+              // despite the newly dead blocks.
             }
           }
         }
@@ -863,9 +865,6 @@
           BasicBlock* succ_bb = GetBasicBlock(succ_info->block);
           DCHECK(succ_bb->catch_entry);
           succ_bb->ErasePredecessor(bb->id);
-          if (succ_bb->predecessors.empty()) {
-            succ_bb->KillUnreachable(this);
-          }
         }
       }
     }
diff --git a/test/800-smali/expected.txt b/test/800-smali/expected.txt
index 5f86f1e..a55a137 100644
--- a/test/800-smali/expected.txt
+++ b/test/800-smali/expected.txt
@@ -9,4 +9,5 @@
 BadCaseInOpRegRegReg
 CmpLong
 FloatIntConstPassing
+b/18718277
 Done!
diff --git a/test/800-smali/smali/b_18718277.smali b/test/800-smali/smali/b_18718277.smali
new file mode 100644
index 0000000..b14ad20
--- /dev/null
+++ b/test/800-smali/smali/b_18718277.smali
@@ -0,0 +1,29 @@
+.class public LB18718277;
+
+.super Ljava/lang/Object;
+
+.method public static helper(I)I
+    .locals 1
+    add-int/lit8 v0, p0, 2
+    neg-int v0, v0
+    return v0
+.end method
+
+.method public static getInt()I
+    .registers 2
+    const/4 v1, 3
+    invoke-static {v1}, LB18718277;->helper(I)I
+    move-result v0
+    :outer_loop
+    if-eqz v1, :exit_outer_loop
+    const/4 v0, 0
+    if-eqz v0, :skip_dead_loop
+    :dead_loop
+    add-int/2addr v0, v0
+    if-gez v0, :dead_loop
+    :skip_dead_loop
+    add-int/lit8 v1, v1, -1
+    goto :outer_loop
+    :exit_outer_loop
+    return v0
+.end method
diff --git a/test/800-smali/src/Main.java b/test/800-smali/src/Main.java
index a2db051..70641b2 100644
--- a/test/800-smali/src/Main.java
+++ b/test/800-smali/src/Main.java
@@ -65,6 +65,7 @@
         testCases.add(new TestCase("BadCaseInOpRegRegReg", "BadCaseInOpRegRegReg", "getInt", null, null, 2));
         testCases.add(new TestCase("CmpLong", "CmpLong", "run", null, null, 0));
         testCases.add(new TestCase("FloatIntConstPassing", "FloatIntConstPassing", "run", null, null, 2));
+        testCases.add(new TestCase("b/18718277", "B18718277", "getInt", null, null, 0));
     }
 
     public void runTests() {