diff --git a/compiler/dex/bb_optimizations.h b/compiler/dex/bb_optimizations.h
index fce23bc..fba0863 100644
--- a/compiler/dex/bb_optimizations.h
+++ b/compiler/dex/bb_optimizations.h
@@ -143,7 +143,7 @@
 class NullCheckElimination : public PassME {
  public:
   NullCheckElimination()
-    : PassME("NCE", kRepeatingTopologicalSortTraversal, "3_post_nce_cfg") {
+    : PassME("NCE", kRepeatingPreOrderDFSTraversal, "3_post_nce_cfg") {
   }
 
   bool Gate(const PassDataHolder* data) const {
@@ -195,7 +195,7 @@
 class ClassInitCheckElimination : public PassME {
  public:
   ClassInitCheckElimination()
-    : PassME("ClInitCheckElimination", kLoopRepeatingTopologicalSortTraversal) {
+    : PassME("ClInitCheckElimination", kRepeatingPreOrderDFSTraversal) {
   }
 
   bool Gate(const PassDataHolder* data) const {
@@ -271,7 +271,8 @@
     DCHECK(data != nullptr);
     CompilationUnit* c_unit = down_cast<const PassMEDataHolder*>(data)->c_unit;
     DCHECK(c_unit != nullptr);
-    return ((c_unit->disable_opt & (1 << kSuppressExceptionEdges)) != 0);
+    return c_unit->mir_graph->HasTryCatchBlocks() ||
+        ((c_unit->disable_opt & (1 << kSuppressExceptionEdges)) != 0);
   }
 
   bool Worker(PassDataHolder* data) const;
diff --git a/compiler/dex/compiler_enums.h b/compiler/dex/compiler_enums.h
index e4003bf..78da420 100644
--- a/compiler/dex/compiler_enums.h
+++ b/compiler/dex/compiler_enums.h
@@ -311,7 +311,8 @@
   kMIRCallee,                         // Instruction is inlined from callee.
   kMIRIgnoreSuspendCheck,
   kMIRDup,
-  kMIRMark,                           // Temporary node mark.
+  kMIRMark,                           // Temporary node mark can be used by
+                                      // opt passes for their private needs.
   kMIRStoreNonTemporal,
   kMIRLastMIRFlag,
 };
diff --git a/compiler/dex/local_value_numbering.cc b/compiler/dex/local_value_numbering.cc
index eb98916..0fb5e48 100644
--- a/compiler/dex/local_value_numbering.cc
+++ b/compiler/dex/local_value_numbering.cc
@@ -1448,6 +1448,10 @@
       }
       break;
 
+    case kMirOpNullCheck:
+      HandleNullCheck(mir, GetOperandValue(mir->ssa_rep->uses[0]));
+      break;
+
     case Instruction::INVOKE_DIRECT:
     case Instruction::INVOKE_DIRECT_RANGE:
     case Instruction::INVOKE_VIRTUAL:
diff --git a/compiler/dex/mir_dataflow.cc b/compiler/dex/mir_dataflow.cc
index 51b6709..0a6924c 100644
--- a/compiler/dex/mir_dataflow.cc
+++ b/compiler/dex/mir_dataflow.cc
@@ -118,10 +118,10 @@
   DF_DA | DF_REF_A | DF_NON_NULL_DST,
 
   // 1D MONITOR_ENTER vAA
-  DF_UA | DF_NULL_CHK_0 | DF_REF_A,
+  DF_UA | DF_NULL_CHK_A | DF_REF_A,
 
   // 1E MONITOR_EXIT vAA
-  DF_UA | DF_NULL_CHK_0 | DF_REF_A,
+  DF_UA | DF_NULL_CHK_A | DF_REF_A,
 
   // 1F CHK_CAST vAA, type@BBBB
   DF_UA | DF_REF_A | DF_UMS,
@@ -130,7 +130,7 @@
   DF_DA | DF_UB | DF_CORE_A | DF_REF_B | DF_UMS,
 
   // 21 ARRAY_LENGTH vA, vB
-  DF_DA | DF_UB | DF_NULL_CHK_0 | DF_CORE_A | DF_REF_B,
+  DF_DA | DF_UB | DF_NULL_CHK_B | DF_CORE_A | DF_REF_B,
 
   // 22 NEW_INSTANCE vAA, type@BBBB
   DF_DA | DF_NON_NULL_DST | DF_REF_A | DF_UMS,
@@ -235,88 +235,88 @@
   DF_NOP,
 
   // 44 AGET vAA, vBB, vCC
-  DF_DA | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_REF_B | DF_CORE_C | DF_LVN,
+  DF_DA | DF_UB | DF_UC | DF_NULL_CHK_B | DF_RANGE_CHK_C | DF_REF_B | DF_CORE_C | DF_LVN,
 
   // 45 AGET_WIDE vAA, vBB, vCC
-  DF_DA | DF_A_WIDE | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_REF_B | DF_CORE_C | DF_LVN,
+  DF_DA | DF_A_WIDE | DF_UB | DF_UC | DF_NULL_CHK_B | DF_RANGE_CHK_C | DF_REF_B | DF_CORE_C | DF_LVN,
 
   // 46 AGET_OBJECT vAA, vBB, vCC
-  DF_DA | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_REF_A | DF_REF_B | DF_CORE_C | DF_LVN,
+  DF_DA | DF_UB | DF_UC | DF_NULL_CHK_B | DF_RANGE_CHK_C | DF_REF_A | DF_REF_B | DF_CORE_C | DF_LVN,
 
   // 47 AGET_BOOLEAN vAA, vBB, vCC
-  DF_DA | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_REF_B | DF_CORE_C | DF_LVN,
+  DF_DA | DF_UB | DF_UC | DF_NULL_CHK_B | DF_RANGE_CHK_C | DF_REF_B | DF_CORE_C | DF_LVN,
 
   // 48 AGET_BYTE vAA, vBB, vCC
-  DF_DA | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_REF_B | DF_CORE_C | DF_LVN,
+  DF_DA | DF_UB | DF_UC | DF_NULL_CHK_B | DF_RANGE_CHK_C | DF_REF_B | DF_CORE_C | DF_LVN,
 
   // 49 AGET_CHAR vAA, vBB, vCC
-  DF_DA | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_REF_B | DF_CORE_C | DF_LVN,
+  DF_DA | DF_UB | DF_UC | DF_NULL_CHK_B | DF_RANGE_CHK_C | DF_REF_B | DF_CORE_C | DF_LVN,
 
   // 4A AGET_SHORT vAA, vBB, vCC
-  DF_DA | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_REF_B | DF_CORE_C | DF_LVN,
+  DF_DA | DF_UB | DF_UC | DF_NULL_CHK_B | DF_RANGE_CHK_C | DF_REF_B | DF_CORE_C | DF_LVN,
 
   // 4B APUT vAA, vBB, vCC
-  DF_UA | DF_UB | DF_UC | DF_NULL_CHK_1 | DF_RANGE_CHK_2 | DF_REF_B | DF_CORE_C | DF_LVN,
+  DF_UA | DF_UB | DF_UC | DF_NULL_CHK_B | DF_RANGE_CHK_C | DF_REF_B | DF_CORE_C | DF_LVN,
 
   // 4C APUT_WIDE vAA, vBB, vCC
-  DF_UA | DF_A_WIDE | DF_UB | DF_UC | DF_NULL_CHK_2 | DF_RANGE_CHK_3 | DF_REF_B | DF_CORE_C | DF_LVN,
+  DF_UA | DF_A_WIDE | DF_UB | DF_UC | DF_NULL_CHK_B | DF_RANGE_CHK_C | DF_REF_B | DF_CORE_C | DF_LVN,
 
   // 4D APUT_OBJECT vAA, vBB, vCC
-  DF_UA | DF_UB | DF_UC | DF_NULL_CHK_1 | DF_RANGE_CHK_2 | DF_REF_A | DF_REF_B | DF_CORE_C | DF_LVN,
+  DF_UA | DF_UB | DF_UC | DF_NULL_CHK_B | DF_RANGE_CHK_C | DF_REF_A | DF_REF_B | DF_CORE_C | DF_LVN,
 
   // 4E APUT_BOOLEAN vAA, vBB, vCC
-  DF_UA | DF_UB | DF_UC | DF_NULL_CHK_1 | DF_RANGE_CHK_2 | DF_REF_B | DF_CORE_C | DF_LVN,
+  DF_UA | DF_UB | DF_UC | DF_NULL_CHK_B | DF_RANGE_CHK_C | DF_REF_B | DF_CORE_C | DF_LVN,
 
   // 4F APUT_BYTE vAA, vBB, vCC
-  DF_UA | DF_UB | DF_UC | DF_NULL_CHK_1 | DF_RANGE_CHK_2 | DF_REF_B | DF_CORE_C | DF_LVN,
+  DF_UA | DF_UB | DF_UC | DF_NULL_CHK_B | DF_RANGE_CHK_C | DF_REF_B | DF_CORE_C | DF_LVN,
 
   // 50 APUT_CHAR vAA, vBB, vCC
-  DF_UA | DF_UB | DF_UC | DF_NULL_CHK_1 | DF_RANGE_CHK_2 | DF_REF_B | DF_CORE_C | DF_LVN,
+  DF_UA | DF_UB | DF_UC | DF_NULL_CHK_B | DF_RANGE_CHK_C | DF_REF_B | DF_CORE_C | DF_LVN,
 
   // 51 APUT_SHORT vAA, vBB, vCC
-  DF_UA | DF_UB | DF_UC | DF_NULL_CHK_1 | DF_RANGE_CHK_2 | DF_REF_B | DF_CORE_C | DF_LVN,
+  DF_UA | DF_UB | DF_UC | DF_NULL_CHK_B | DF_RANGE_CHK_C | DF_REF_B | DF_CORE_C | DF_LVN,
 
   // 52 IGET vA, vB, field@CCCC
-  DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_B | DF_IFIELD | DF_LVN,
+  DF_DA | DF_UB | DF_NULL_CHK_B | DF_REF_B | DF_IFIELD | DF_LVN,
 
   // 53 IGET_WIDE vA, vB, field@CCCC
-  DF_DA | DF_A_WIDE | DF_UB | DF_NULL_CHK_0 | DF_REF_B | DF_IFIELD | DF_LVN,
+  DF_DA | DF_A_WIDE | DF_UB | DF_NULL_CHK_B | DF_REF_B | DF_IFIELD | DF_LVN,
 
   // 54 IGET_OBJECT vA, vB, field@CCCC
-  DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_A | DF_REF_B | DF_IFIELD | DF_LVN,
+  DF_DA | DF_UB | DF_NULL_CHK_B | DF_REF_A | DF_REF_B | DF_IFIELD | DF_LVN,
 
   // 55 IGET_BOOLEAN vA, vB, field@CCCC
-  DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_B | DF_IFIELD | DF_LVN,
+  DF_DA | DF_UB | DF_NULL_CHK_B | DF_REF_B | DF_IFIELD | DF_LVN,
 
   // 56 IGET_BYTE vA, vB, field@CCCC
-  DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_B | DF_IFIELD | DF_LVN,
+  DF_DA | DF_UB | DF_NULL_CHK_B | DF_REF_B | DF_IFIELD | DF_LVN,
 
   // 57 IGET_CHAR vA, vB, field@CCCC
-  DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_B | DF_IFIELD | DF_LVN,
+  DF_DA | DF_UB | DF_NULL_CHK_B | DF_REF_B | DF_IFIELD | DF_LVN,
 
   // 58 IGET_SHORT vA, vB, field@CCCC
-  DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_B | DF_IFIELD | DF_LVN,
+  DF_DA | DF_UB | DF_NULL_CHK_B | DF_REF_B | DF_IFIELD | DF_LVN,
 
   // 59 IPUT vA, vB, field@CCCC
-  DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_B | DF_IFIELD | DF_LVN,
+  DF_UA | DF_UB | DF_NULL_CHK_B | DF_REF_B | DF_IFIELD | DF_LVN,
 
   // 5A IPUT_WIDE vA, vB, field@CCCC
-  DF_UA | DF_A_WIDE | DF_UB | DF_NULL_CHK_2 | DF_REF_B | DF_IFIELD | DF_LVN,
+  DF_UA | DF_A_WIDE | DF_UB | DF_NULL_CHK_B | DF_REF_B | DF_IFIELD | DF_LVN,
 
   // 5B IPUT_OBJECT vA, vB, field@CCCC
-  DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_A | DF_REF_B | DF_IFIELD | DF_LVN,
+  DF_UA | DF_UB | DF_NULL_CHK_B | DF_REF_A | DF_REF_B | DF_IFIELD | DF_LVN,
 
   // 5C IPUT_BOOLEAN vA, vB, field@CCCC
-  DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_B | DF_IFIELD | DF_LVN,
+  DF_UA | DF_UB | DF_NULL_CHK_B | DF_REF_B | DF_IFIELD | DF_LVN,
 
   // 5D IPUT_BYTE vA, vB, field@CCCC
-  DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_B | DF_IFIELD | DF_LVN,
+  DF_UA | DF_UB | DF_NULL_CHK_B | DF_REF_B | DF_IFIELD | DF_LVN,
 
   // 5E IPUT_CHAR vA, vB, field@CCCC
-  DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_B | DF_IFIELD | DF_LVN,
+  DF_UA | DF_UB | DF_NULL_CHK_B | DF_REF_B | DF_IFIELD | DF_LVN,
 
   // 5F IPUT_SHORT vA, vB, field@CCCC
-  DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_B | DF_IFIELD | DF_LVN,
+  DF_UA | DF_UB | DF_NULL_CHK_B | DF_REF_B | DF_IFIELD | DF_LVN,
 
   // 60 SGET vAA, field@BBBB
   DF_DA | DF_SFIELD | DF_UMS,
@@ -712,10 +712,10 @@
   DF_DA | DF_UB | DF_CORE_A | DF_CORE_B,
 
   // E3 IGET_VOLATILE
-  DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_B | DF_IFIELD | DF_LVN,
+  DF_DA | DF_UB | DF_NULL_CHK_B | DF_REF_B | DF_IFIELD | DF_LVN,
 
   // E4 IPUT_VOLATILE
-  DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_B | DF_IFIELD | DF_LVN,
+  DF_UA | DF_UB | DF_NULL_CHK_B | DF_REF_B | DF_IFIELD | DF_LVN,
 
   // E5 SGET_VOLATILE
   DF_DA | DF_SFIELD | DF_UMS,
@@ -724,13 +724,13 @@
   DF_UA | DF_SFIELD | DF_UMS,
 
   // E7 IGET_OBJECT_VOLATILE
-  DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_A | DF_REF_B | DF_IFIELD | DF_LVN,
+  DF_DA | DF_UB | DF_NULL_CHK_B | DF_REF_A | DF_REF_B | DF_IFIELD | DF_LVN,
 
   // E8 IGET_WIDE_VOLATILE
-  DF_DA | DF_A_WIDE | DF_UB | DF_NULL_CHK_0 | DF_REF_B | DF_IFIELD | DF_LVN,
+  DF_DA | DF_A_WIDE | DF_UB | DF_NULL_CHK_B | DF_REF_B | DF_IFIELD | DF_LVN,
 
   // E9 IPUT_WIDE_VOLATILE
-  DF_UA | DF_A_WIDE | DF_UB | DF_NULL_CHK_2 | DF_REF_B | DF_IFIELD | DF_LVN,
+  DF_UA | DF_A_WIDE | DF_UB | DF_NULL_CHK_B | DF_REF_B | DF_IFIELD | DF_LVN,
 
   // EA SGET_WIDE_VOLATILE
   DF_DA | DF_A_WIDE | DF_SFIELD | DF_UMS,
@@ -751,28 +751,28 @@
   DF_FORMAT_3RC,
 
   // F0 INVOKE_OBJECT_INIT_RANGE
-  DF_NOP | DF_NULL_CHK_0,
+  DF_NOP,
 
   // F1 RETURN_VOID_BARRIER
   DF_NOP,
 
   // F2 IGET_QUICK
-  DF_DA | DF_UB | DF_NULL_CHK_0 | DF_IFIELD | DF_LVN,
+  DF_DA | DF_UB | DF_NULL_CHK_B | DF_IFIELD | DF_LVN,
 
   // F3 IGET_WIDE_QUICK
-  DF_DA | DF_A_WIDE | DF_UB | DF_NULL_CHK_0 | DF_IFIELD | DF_LVN,
+  DF_DA | DF_A_WIDE | DF_UB | DF_NULL_CHK_B | DF_IFIELD | DF_LVN,
 
   // F4 IGET_OBJECT_QUICK
-  DF_DA | DF_UB | DF_NULL_CHK_0 | DF_IFIELD | DF_LVN,
+  DF_DA | DF_UB | DF_NULL_CHK_B | DF_IFIELD | DF_LVN,
 
   // F5 IPUT_QUICK
-  DF_UA | DF_UB | DF_NULL_CHK_1 | DF_IFIELD | DF_LVN,
+  DF_UA | DF_UB | DF_NULL_CHK_B | DF_IFIELD | DF_LVN,
 
   // F6 IPUT_WIDE_QUICK
-  DF_UA | DF_A_WIDE | DF_UB | DF_NULL_CHK_2 | DF_IFIELD | DF_LVN,
+  DF_UA | DF_A_WIDE | DF_UB | DF_NULL_CHK_B | DF_IFIELD | DF_LVN,
 
   // F7 IPUT_OBJECT_QUICK
-  DF_UA | DF_UB | DF_NULL_CHK_1 | DF_IFIELD | DF_LVN,
+  DF_UA | DF_UB | DF_NULL_CHK_B | DF_IFIELD | DF_LVN,
 
   // F8 INVOKE_VIRTUAL_QUICK
   DF_FORMAT_35C | DF_NULL_CHK_OUT0 | DF_UMS,
@@ -787,7 +787,7 @@
   DF_FORMAT_3RC | DF_NULL_CHK_OUT0 | DF_UMS,
 
   // FC IPUT_OBJECT_VOLATILE
-  DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_A | DF_REF_B | DF_IFIELD | DF_LVN,
+  DF_UA | DF_UB | DF_NULL_CHK_B | DF_REF_A | DF_REF_B | DF_IFIELD | DF_LVN,
 
   // FD SGET_OBJECT_VOLATILE
   DF_DA | DF_REF_A | DF_SFIELD | DF_UMS,
@@ -824,7 +824,7 @@
   DF_NOP,
 
   // 108 MIR_NULL_CHECK
-  DF_UA | DF_REF_A | DF_NULL_CHK_0 | DF_LVN,
+  DF_UA | DF_REF_A | DF_NULL_CHK_A | DF_LVN,
 
   // 109 MIR_RANGE_CHECK
   0,
@@ -893,10 +893,10 @@
   0,
 
   // 11F MirOpPackedArrayGet
-  DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_REF_B | DF_CORE_C | DF_LVN,
+  DF_UB | DF_UC | DF_NULL_CHK_B | DF_RANGE_CHK_C | DF_REF_B | DF_CORE_C | DF_LVN,
 
   // 120 MirOpPackedArrayPut
-  DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_REF_B | DF_CORE_C | DF_LVN,
+  DF_UB | DF_UC | DF_NULL_CHK_B | DF_RANGE_CHK_C | DF_REF_B | DF_CORE_C | DF_LVN,
 };
 
 /* Return the base virtual register for a SSA name */
@@ -1403,7 +1403,7 @@
       GetBlockName(bb, block_name1);
       GetBlockName(pred_bb, block_name2);
       DumpCFG("/sdcard/cfg/", false);
-      LOG(FATAL) << "Successor " << block_name1 << "not found from "
+      LOG(FATAL) << "Successor " << block_name1 << " not found from "
                  << block_name2;
     }
   }
diff --git a/compiler/dex/mir_field_info.h b/compiler/dex/mir_field_info.h
index 9745c41..1842a16 100644
--- a/compiler/dex/mir_field_info.h
+++ b/compiler/dex/mir_field_info.h
@@ -137,6 +137,7 @@
   // The member offset of the field, 0u if unresolved.
   MemberOffset field_offset_;
 
+  friend class NullCheckEliminationTest;
   friend class GlobalValueNumberingTest;
   friend class LocalValueNumberingTest;
 };
diff --git a/compiler/dex/mir_graph.cc b/compiler/dex/mir_graph.cc
index f0c9858..8dded79 100644
--- a/compiler/dex/mir_graph.cc
+++ b/compiler/dex/mir_graph.cc
@@ -86,6 +86,7 @@
       raw_use_counts_(arena->Adapter()),
       num_reachable_blocks_(0),
       max_num_reachable_blocks_(0),
+      dfs_orders_up_to_date_(false),
       dfs_order_(arena->Adapter(kArenaAllocDfsPreOrder)),
       dfs_post_order_(arena->Adapter(kArenaAllocDfsPostOrder)),
       dom_post_order_traversal_(arena->Adapter(kArenaAllocDomPostOrder)),
@@ -2224,7 +2225,7 @@
   }
 }
 
-void BasicBlock::Hide(CompilationUnit* c_unit) {
+void BasicBlock::Hide(MIRGraph* mir_graph) {
   // First lets make it a dalvik bytecode block so it doesn't have any special meaning.
   block_type = kDalvikByteCode;
 
@@ -2239,7 +2240,6 @@
   first_mir_insn = nullptr;
   last_mir_insn = nullptr;
 
-  MIRGraph* mir_graph = c_unit->mir_graph.get();
   for (BasicBlockId pred_id : predecessors) {
     BasicBlock* pred_bb = mir_graph->GetBasicBlock(pred_id);
     DCHECK(pred_bb != nullptr);
@@ -2262,6 +2262,48 @@
   successor_block_list_type = kNotUsed;
 }
 
+/*
+ * Kill an unreachable block and all blocks that become unreachable by killing this one.
+ */
+void BasicBlock::KillUnreachable(MIRGraph* mir_graph) {
+  DCHECK(predecessors.empty());  // Unreachable.
+
+  // Mark as dead and hidden.
+  block_type = kDead;
+  hidden = true;
+
+  // Detach it from its MIRs so we don't generate code for them. Also detached MIRs
+  // are updated to know that they no longer have a parent.
+  for (MIR* mir = first_mir_insn; mir != nullptr; mir = mir->next) {
+    mir->bb = NullBasicBlockId;
+  }
+  first_mir_insn = nullptr;
+  last_mir_insn = nullptr;
+
+  data_flow_info = nullptr;
+
+  // Erase this bb from all children's predecessors and kill unreachable children.
+  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.
+  fall_through = NullBasicBlockId;
+  taken = NullBasicBlockId;
+  successor_block_list_type = kNotUsed;
+
+  if (kIsDebugBuild) {
+    if (catch_entry) {
+      DCHECK_EQ(mir_graph->catches_.count(start_offset), 1u);
+      mir_graph->catches_.erase(start_offset);
+    }
+  }
+}
+
 bool BasicBlock::IsSSALiveOut(const CompilationUnit* c_unit, int ssa_reg) {
   // In order to determine if the ssa reg is live out, we scan all the MIRs. We remember
   // the last SSA number of the same dalvik register. At the end, if it is different than ssa_reg,
@@ -2333,17 +2375,34 @@
 void BasicBlock::ErasePredecessor(BasicBlockId old_pred) {
   auto pos = std::find(predecessors.begin(), predecessors.end(), old_pred);
   DCHECK(pos != predecessors.end());
-  predecessors.erase(pos);
+  // It's faster to move the back() to *pos than erase(pos).
+  *pos = predecessors.back();
+  predecessors.pop_back();
+  size_t idx = std::distance(predecessors.begin(), pos);
+  for (MIR* mir = first_mir_insn; mir != nullptr; mir = mir->next) {
+    if (static_cast<int>(mir->dalvikInsn.opcode) != kMirOpPhi) {
+      break;
+    }
+    DCHECK_EQ(mir->ssa_rep->num_uses - 1u, predecessors.size());
+    DCHECK_EQ(mir->meta.phi_incoming[idx], old_pred);
+    mir->meta.phi_incoming[idx] = mir->meta.phi_incoming[predecessors.size()];
+    mir->ssa_rep->uses[idx] = mir->ssa_rep->uses[predecessors.size()];
+    mir->ssa_rep->num_uses = predecessors.size();
+  }
 }
 
 void BasicBlock::UpdatePredecessor(BasicBlockId old_pred, BasicBlockId new_pred) {
   DCHECK_NE(new_pred, NullBasicBlockId);
   auto pos = std::find(predecessors.begin(), predecessors.end(), old_pred);
-  if (pos != predecessors.end()) {
-    *pos = new_pred;
-  } else {
-    // If not found, add it.
-    predecessors.push_back(new_pred);
+  DCHECK(pos != predecessors.end());
+  *pos = new_pred;
+  size_t idx = std::distance(predecessors.begin(), pos);
+  for (MIR* mir = first_mir_insn; mir != nullptr; mir = mir->next) {
+    if (static_cast<int>(mir->dalvikInsn.opcode) != kMirOpPhi) {
+      break;
+    }
+    DCHECK_EQ(mir->meta.phi_incoming[idx], old_pred);
+    mir->meta.phi_incoming[idx] = new_pred;
   }
 }
 
diff --git a/compiler/dex/mir_graph.h b/compiler/dex/mir_graph.h
index cc215bd..80303f6 100644
--- a/compiler/dex/mir_graph.h
+++ b/compiler/dex/mir_graph.h
@@ -49,17 +49,14 @@
   kFormat35c,
   kFormat3rc,
   kFormatExtended,       // Extended format for extended MIRs.
-  kNullCheckSrc0,        // Null check of uses[0].
-  kNullCheckSrc1,        // Null check of uses[1].
-  kNullCheckSrc2,        // Null check of uses[2].
+  kNullCheckA,           // Null check of A.
+  kNullCheckB,           // Null check of B.
   kNullCheckOut0,        // Null check out outgoing arg0.
   kDstNonNull,           // May assume dst is non-null.
   kRetNonNull,           // May assume retval is non-null.
   kNullTransferSrc0,     // Object copy src[0] -> dst.
   kNullTransferSrcN,     // Phi null check state transfer.
-  kRangeCheckSrc1,       // Range check of uses[1].
-  kRangeCheckSrc2,       // Range check of uses[2].
-  kRangeCheckSrc3,       // Range check of uses[3].
+  kRangeCheckC,          // Range check of C.
   kFPA,
   kFPB,
   kFPC,
@@ -88,17 +85,14 @@
 #define DF_FORMAT_35C           (UINT64_C(1) << kFormat35c)
 #define DF_FORMAT_3RC           (UINT64_C(1) << kFormat3rc)
 #define DF_FORMAT_EXTENDED      (UINT64_C(1) << kFormatExtended)
-#define DF_NULL_CHK_0           (UINT64_C(1) << kNullCheckSrc0)
-#define DF_NULL_CHK_1           (UINT64_C(1) << kNullCheckSrc1)
-#define DF_NULL_CHK_2           (UINT64_C(1) << kNullCheckSrc2)
+#define DF_NULL_CHK_A           (UINT64_C(1) << kNullCheckA)
+#define DF_NULL_CHK_B           (UINT64_C(1) << kNullCheckB)
 #define DF_NULL_CHK_OUT0        (UINT64_C(1) << kNullCheckOut0)
 #define DF_NON_NULL_DST         (UINT64_C(1) << kDstNonNull)
 #define DF_NON_NULL_RET         (UINT64_C(1) << kRetNonNull)
 #define DF_NULL_TRANSFER_0      (UINT64_C(1) << kNullTransferSrc0)
 #define DF_NULL_TRANSFER_N      (UINT64_C(1) << kNullTransferSrcN)
-#define DF_RANGE_CHK_1          (UINT64_C(1) << kRangeCheckSrc1)
-#define DF_RANGE_CHK_2          (UINT64_C(1) << kRangeCheckSrc2)
-#define DF_RANGE_CHK_3          (UINT64_C(1) << kRangeCheckSrc3)
+#define DF_RANGE_CHK_C          (UINT64_C(1) << kRangeCheckC)
 #define DF_FP_A                 (UINT64_C(1) << kFPA)
 #define DF_FP_B                 (UINT64_C(1) << kFPB)
 #define DF_FP_C                 (UINT64_C(1) << kFPC)
@@ -117,14 +111,11 @@
 
 #define DF_HAS_DEFS             (DF_DA)
 
-#define DF_HAS_NULL_CHKS        (DF_NULL_CHK_0 | \
-                                 DF_NULL_CHK_1 | \
-                                 DF_NULL_CHK_2 | \
+#define DF_HAS_NULL_CHKS        (DF_NULL_CHK_A | \
+                                 DF_NULL_CHK_B | \
                                  DF_NULL_CHK_OUT0)
 
-#define DF_HAS_RANGE_CHKS       (DF_RANGE_CHK_1 | \
-                                 DF_RANGE_CHK_2 | \
-                                 DF_RANGE_CHK_3)
+#define DF_HAS_RANGE_CHKS       (DF_RANGE_CHK_C)
 
 #define DF_HAS_NR_CHKS          (DF_HAS_NULL_CHKS | \
                                  DF_HAS_RANGE_CHKS)
@@ -132,9 +123,10 @@
 #define DF_A_IS_REG             (DF_UA | DF_DA)
 #define DF_B_IS_REG             (DF_UB)
 #define DF_C_IS_REG             (DF_UC)
-#define DF_IS_GETTER_OR_SETTER  (DF_IS_GETTER | DF_IS_SETTER)
 #define DF_USES_FP              (DF_FP_A | DF_FP_B | DF_FP_C)
 #define DF_NULL_TRANSFER        (DF_NULL_TRANSFER_0 | DF_NULL_TRANSFER_N)
+#define DF_IS_INVOKE            (DF_FORMAT_35C | DF_FORMAT_3RC)
+
 enum OatMethodAttributes {
   kIsLeaf,            // Method is leaf.
   kHasLoop,           // Method contains simple loop.
@@ -160,6 +152,7 @@
 #define MIR_CALLEE                      (1 << kMIRCallee)
 #define MIR_IGNORE_SUSPEND_CHECK        (1 << kMIRIgnoreSuspendCheck)
 #define MIR_DUP                         (1 << kMIRDup)
+#define MIR_MARK                        (1 << kMIRMark)
 #define MIR_STORE_NON_TEMPORAL          (1 << kMIRStoreNonTemporal)
 
 #define BLOCK_NAME_LEN 80
@@ -422,7 +415,12 @@
    *          remove itself from any predecessor edges, remove itself from any
    *          child's predecessor array.
    */
-  void Hide(CompilationUnit* c_unit);
+  void Hide(MIRGraph* mir_graph);
+
+  /**
+   *  @brief Kill the unreachable block and all blocks that become unreachable by killing this one.
+   */
+  void KillUnreachable(MIRGraph* mir_graph);
 
   /**
    * @brief Is ssa_reg the last SSA definition of that VR in the block?
@@ -1015,6 +1013,10 @@
     return GetFirstSpecialTempVR() + max_available_special_compiler_temps_;
   }
 
+  bool HasTryCatchBlocks() const {
+    return current_code_item_->tries_size_ != 0;
+  }
+
   void DumpCheckStats();
   MIR* FindMoveResult(BasicBlock* bb, MIR* mir);
   int SRegToVReg(int ssa_reg) const;
@@ -1150,6 +1152,10 @@
   void InsertPhiNodes();
   void DoDFSPreOrderSSARename(BasicBlock* block);
 
+  bool DfsOrdersUpToDate() const {
+    return dfs_orders_up_to_date_;
+  }
+
   /*
    * IsDebugBuild sanity check: keep track of the Dex PCs for catch entries so that later on
    * we can verify that all catch entries have native PC entries.
@@ -1246,6 +1252,7 @@
   ArenaVector<uint32_t> raw_use_counts_;  // Not weighted
   unsigned int num_reachable_blocks_;
   unsigned int max_num_reachable_blocks_;
+  bool dfs_orders_up_to_date_;
   ArenaVector<BasicBlockId> dfs_order_;
   ArenaVector<BasicBlockId> dfs_post_order_;
   ArenaVector<BasicBlockId> dom_post_order_traversal_;
@@ -1306,7 +1313,9 @@
   static const uint64_t oat_data_flow_attributes_[kMirOpLast];
   ArenaVector<BasicBlock*> gen_suspend_test_list_;  // List of blocks containing suspend tests
 
+  friend class MirOptimizationTest;
   friend class ClassInitCheckEliminationTest;
+  friend class NullCheckEliminationTest;
   friend class GlobalValueNumberingTest;
   friend class LocalValueNumberingTest;
   friend class TopologicalSortOrderTest;
diff --git a/compiler/dex/mir_optimization.cc b/compiler/dex/mir_optimization.cc
index 84c056d..00528e5 100644
--- a/compiler/dex/mir_optimization.cc
+++ b/compiler/dex/mir_optimization.cc
@@ -752,51 +752,101 @@
 /* Combine any basic blocks terminated by instructions that we now know can't throw */
 void MIRGraph::CombineBlocks(struct BasicBlock* bb) {
   // Loop here to allow combining a sequence of blocks
-  while (true) {
-    // Check termination conditions
-    if ((bb->first_mir_insn == NULL)
-        || (bb->data_flow_info == NULL)
-        || (bb->block_type == kExceptionHandling)
-        || (bb->block_type == kExitBlock)
-        || (bb->block_type == kDead)
-        || (bb->taken == NullBasicBlockId)
-        || (GetBasicBlock(bb->taken)->block_type != kExceptionHandling)
-        || (bb->successor_block_list_type != kNotUsed)
-        || (static_cast<int>(bb->last_mir_insn->dalvikInsn.opcode) != kMirOpCheck)) {
+  while ((bb->block_type == kDalvikByteCode) &&
+      (bb->last_mir_insn != nullptr) &&
+      (static_cast<int>(bb->last_mir_insn->dalvikInsn.opcode) == kMirOpCheck)) {
+    MIR* mir = bb->last_mir_insn;
+    DCHECK(bb->first_mir_insn !=  nullptr);
+
+    // Grab the attributes from the paired opcode.
+    MIR* throw_insn = mir->meta.throw_insn;
+    uint64_t df_attributes = GetDataFlowAttributes(throw_insn);
+
+    // Don't combine if the throw_insn can still throw NPE.
+    if ((df_attributes & DF_HAS_NULL_CHKS) != 0 &&
+        (throw_insn->optimization_flags & MIR_IGNORE_NULL_CHECK) == 0) {
+      break;
+    }
+    // Now whitelist specific instructions.
+    bool ok = false;
+    if ((df_attributes & DF_IFIELD) != 0) {
+      // Combine only if fast, otherwise weird things can happen.
+      const MirIFieldLoweringInfo& field_info = GetIFieldLoweringInfo(throw_insn);
+      ok = (df_attributes & DF_DA)  ? field_info.FastPut() : field_info.FastGet();
+    } else if ((df_attributes & DF_SFIELD) != 0) {
+      // Combine only if fast, otherwise weird things can happen.
+      const MirSFieldLoweringInfo& field_info = GetSFieldLoweringInfo(throw_insn);
+      bool fast = ((df_attributes & DF_DA)  ? field_info.FastPut() : field_info.FastGet());
+      // Don't combine if the SGET/SPUT can call <clinit>().
+      bool clinit = !field_info.IsInitialized() &&
+          (throw_insn->optimization_flags & MIR_IGNORE_CLINIT_CHECK) == 0;
+      ok = fast && !clinit;
+    } else if ((df_attributes & DF_HAS_RANGE_CHKS) != 0) {
+      // Only AGET/APUT have range checks. We have processed the AGET/APUT null check above.
+      DCHECK_NE(throw_insn->optimization_flags & MIR_IGNORE_NULL_CHECK, 0);
+      ok = ((throw_insn->optimization_flags & MIR_IGNORE_RANGE_CHECK) != 0);
+    } else if ((throw_insn->dalvikInsn.FlagsOf() & Instruction::kThrow) == 0) {
+      // We can encounter a non-throwing insn here thanks to inlining or other optimizations.
+      ok = true;
+    } else if (throw_insn->dalvikInsn.opcode == Instruction::ARRAY_LENGTH ||
+        throw_insn->dalvikInsn.opcode == Instruction::FILL_ARRAY_DATA ||
+        static_cast<int>(throw_insn->dalvikInsn.opcode) == kMirOpNullCheck) {
+      // No more checks for these (null check was processed above).
+      ok = true;
+    }
+    if (!ok) {
       break;
     }
 
-    // Test the kMirOpCheck instruction
-    MIR* mir = bb->last_mir_insn;
-    // Grab the attributes from the paired opcode
-    MIR* throw_insn = mir->meta.throw_insn;
-    uint64_t df_attributes = GetDataFlowAttributes(throw_insn);
-    bool can_combine = true;
-    if (df_attributes & DF_HAS_NULL_CHKS) {
-      can_combine &= ((throw_insn->optimization_flags & MIR_IGNORE_NULL_CHECK) != 0);
-    }
-    if (df_attributes & DF_HAS_RANGE_CHKS) {
-      can_combine &= ((throw_insn->optimization_flags & MIR_IGNORE_RANGE_CHECK) != 0);
-    }
-    if (!can_combine) {
-      break;
-    }
     // OK - got one.  Combine
     BasicBlock* bb_next = GetBasicBlock(bb->fall_through);
     DCHECK(!bb_next->catch_entry);
-    DCHECK_EQ(Predecessors(bb_next), 1U);
-    // Overwrite the kOpCheck insn with the paired opcode
+    DCHECK_EQ(bb_next->predecessors.size(), 1u);
+    // Overwrite the kMirOpCheck insn with the paired opcode.
     DCHECK_EQ(bb_next->first_mir_insn, throw_insn);
     *bb->last_mir_insn = *throw_insn;
+    // And grab the rest of the instructions from bb_next.
+    bb->last_mir_insn = bb_next->last_mir_insn;
+    throw_insn->next = nullptr;
+    bb_next->last_mir_insn = throw_insn;
+    // Mark acquired instructions as belonging to bb.
+    for (MIR* insn = mir; insn != nullptr; insn = insn->next) {
+      insn->bb = bb->id;
+    }
+    // Before we overwrite successors, remove their predecessor links to bb.
+    bb_next->ErasePredecessor(bb->id);
+    if (bb->taken != NullBasicBlockId) {
+      DCHECK_EQ(bb->successor_block_list_type, kNotUsed);
+      BasicBlock* bb_taken = GetBasicBlock(bb->taken);
+      // bb->taken will be overwritten below.
+      DCHECK_EQ(bb_taken->block_type, kExceptionHandling);
+      DCHECK_EQ(bb_taken->predecessors.size(), 1u);
+      DCHECK_EQ(bb_taken->predecessors[0], bb->id);
+      bb_taken->predecessors.clear();
+      bb_taken->block_type = kDead;
+      DCHECK(bb_taken->data_flow_info == nullptr);
+    } else {
+      DCHECK_EQ(bb->successor_block_list_type, kCatch);
+      for (SuccessorBlockInfo* succ_info : bb->successor_blocks) {
+        if (succ_info->block != NullBasicBlockId) {
+          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);
+          }
+        }
+      }
+    }
     // Use the successor info from the next block
     bb->successor_block_list_type = bb_next->successor_block_list_type;
     bb->successor_blocks.swap(bb_next->successor_blocks);  // Swap instead of copying.
+    bb_next->successor_block_list_type = kNotUsed;
     // Use the ending block linkage from the next block
     bb->fall_through = bb_next->fall_through;
-    GetBasicBlock(bb->taken)->block_type = kDead;  // Kill the unused exception block
+    bb_next->fall_through = NullBasicBlockId;
     bb->taken = bb_next->taken;
-    // Include the rest of the instructions
-    bb->last_mir_insn = bb_next->last_mir_insn;
+    bb_next->taken = NullBasicBlockId;
     /*
      * If lower-half of pair of blocks to combine contained
      * a return or a conditional branch or an explicit throw,
@@ -805,15 +855,30 @@
     bb->terminated_by_return = bb_next->terminated_by_return;
     bb->conditional_branch = bb_next->conditional_branch;
     bb->explicit_throw = bb_next->explicit_throw;
+    // Merge the use_lvn flag.
+    bb->use_lvn |= bb_next->use_lvn;
+
+    // Kill the unused block.
+    bb_next->data_flow_info = nullptr;
 
     /*
      * NOTE: we aren't updating all dataflow info here.  Should either make sure this pass
      * happens after uses of i_dominated, dom_frontier or update the dataflow info here.
+     * NOTE: GVN uses bb->data_flow_info->live_in_v which is unaffected by the block merge.
      */
 
-    // Kill bb_next and remap now-dead id to parent
+    // Kill bb_next and remap now-dead id to parent.
     bb_next->block_type = kDead;
+    bb_next->data_flow_info = nullptr;  // Must be null for dead blocks. (Relied on by the GVN.)
     block_id_map_.Overwrite(bb_next->id, bb->id);
+    // Update predecessors in children.
+    ChildBlockIterator iter(bb, this);
+    for (BasicBlock* child = iter.Next(); child != nullptr; child = iter.Next()) {
+      child->UpdatePredecessor(bb_next->id, bb->id);
+    }
+
+    // DFS orders are not up to date anymore.
+    dfs_orders_up_to_date_ = false;
 
     // Now, loop back and see if we can keep going
   }
@@ -827,12 +892,21 @@
 
   DCHECK(temp_scoped_alloc_.get() == nullptr);
   temp_scoped_alloc_.reset(ScopedArenaAllocator::Create(&cu_->arena_stack));
-  temp_bit_vector_size_ = GetNumSSARegs();
+  temp_bit_vector_size_ = GetNumOfCodeVRs();
   temp_bit_vector_ = new (temp_scoped_alloc_.get()) ArenaBitVector(
       temp_scoped_alloc_.get(), temp_bit_vector_size_, false, kBitMapNullCheck);
   temp_bit_matrix_ = static_cast<ArenaBitVector**>(
       temp_scoped_alloc_->Alloc(sizeof(ArenaBitVector*) * GetNumBlocks(), kArenaAllocMisc));
   std::fill_n(temp_bit_matrix_, GetNumBlocks(), nullptr);
+
+  // reset MIR_MARK
+  AllNodesIterator iter(this);
+  for (BasicBlock* bb = iter.Next(); bb != nullptr; bb = iter.Next()) {
+    for (MIR* mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
+      mir->optimization_flags &= ~MIR_MARK;
+    }
+  }
+
   return true;
 }
 
@@ -840,100 +914,96 @@
  * Eliminate unnecessary null checks for a basic block.
  */
 bool MIRGraph::EliminateNullChecks(BasicBlock* bb) {
-  if (bb->data_flow_info == nullptr) return false;
+  if (bb->block_type != kDalvikByteCode && bb->block_type != kEntryBlock) {
+    // Ignore the kExitBlock as well.
+    DCHECK(bb->first_mir_insn == nullptr);
+    return false;
+  }
 
-  ArenaBitVector* ssa_regs_to_check = temp_bit_vector_;
+  ArenaBitVector* vregs_to_check = temp_bit_vector_;
   /*
    * Set initial state. Catch blocks don't need any special treatment.
    */
   if (bb->block_type == kEntryBlock) {
-    ssa_regs_to_check->ClearAllBits();
+    vregs_to_check->ClearAllBits();
     // Assume all ins are objects.
     for (uint16_t in_reg = GetFirstInVR();
          in_reg < GetNumOfCodeVRs(); in_reg++) {
-      ssa_regs_to_check->SetBit(in_reg);
+      vregs_to_check->SetBit(in_reg);
     }
     if ((cu_->access_flags & kAccStatic) == 0) {
-      // If non-static method, mark "this" as non-null
+      // If non-static method, mark "this" as non-null.
       int this_reg = GetFirstInVR();
-      ssa_regs_to_check->ClearBit(this_reg);
+      vregs_to_check->ClearBit(this_reg);
     }
-  } else if (bb->predecessors.size() == 1) {
-    BasicBlock* pred_bb = GetBasicBlock(bb->predecessors[0]);
-    // pred_bb must have already been processed at least once.
-    DCHECK(temp_bit_matrix_[pred_bb->id] != nullptr);
-    ssa_regs_to_check->Copy(temp_bit_matrix_[pred_bb->id]);
-    if (pred_bb->block_type == kDalvikByteCode) {
-      // Check to see if predecessor had an explicit null-check.
-      MIR* last_insn = pred_bb->last_mir_insn;
-      if (last_insn != nullptr) {
-        Instruction::Code last_opcode = last_insn->dalvikInsn.opcode;
-        if (last_opcode == Instruction::IF_EQZ) {
-          if (pred_bb->fall_through == bb->id) {
-            // The fall-through of a block following a IF_EQZ, set the vA of the IF_EQZ to show that
-            // it can't be null.
-            ssa_regs_to_check->ClearBit(last_insn->ssa_rep->uses[0]);
-          }
-        } else if (last_opcode == Instruction::IF_NEZ) {
-          if (pred_bb->taken == bb->id) {
-            // The taken block following a IF_NEZ, set the vA of the IF_NEZ to show that it can't be
-            // null.
-            ssa_regs_to_check->ClearBit(last_insn->ssa_rep->uses[0]);
+  } else {
+    DCHECK_EQ(bb->block_type, kDalvikByteCode);
+    // Starting state is union of all incoming arcs.
+    bool copied_first = false;
+    for (BasicBlockId pred_id : bb->predecessors) {
+      if (temp_bit_matrix_[pred_id] == nullptr) {
+        continue;
+      }
+      BasicBlock* pred_bb = GetBasicBlock(pred_id);
+      DCHECK(pred_bb != nullptr);
+      MIR* null_check_insn = nullptr;
+      if (pred_bb->block_type == kDalvikByteCode) {
+        // Check to see if predecessor had an explicit null-check.
+        MIR* last_insn = pred_bb->last_mir_insn;
+        if (last_insn != nullptr) {
+          Instruction::Code last_opcode = last_insn->dalvikInsn.opcode;
+          if ((last_opcode == Instruction::IF_EQZ && pred_bb->fall_through == bb->id) ||
+              (last_opcode == Instruction::IF_NEZ && pred_bb->taken == bb->id)) {
+            // Remember the null check insn if there's no other predecessor requiring null check.
+            if (!copied_first || !vregs_to_check->IsBitSet(last_insn->dalvikInsn.vA)) {
+              null_check_insn = last_insn;
+            }
           }
         }
       }
-    }
-  } else {
-    // Starting state is union of all incoming arcs
-    bool copied_first = false;
-    for (BasicBlockId pred_id : bb->predecessors) {
-      BasicBlock* pred_bb = GetBasicBlock(pred_id);
-      DCHECK(pred_bb != nullptr);
-      DCHECK(pred_bb->data_flow_info != nullptr);
-      if (temp_bit_matrix_[pred_bb->id] == nullptr) {
-        continue;
-      }
       if (!copied_first) {
         copied_first = true;
-        ssa_regs_to_check->Copy(temp_bit_matrix_[pred_bb->id]);
+        vregs_to_check->Copy(temp_bit_matrix_[pred_id]);
       } else {
-        ssa_regs_to_check->Union(temp_bit_matrix_[pred_bb->id]);
+        vregs_to_check->Union(temp_bit_matrix_[pred_id]);
+      }
+      if (null_check_insn != nullptr) {
+        vregs_to_check->ClearBit(null_check_insn->dalvikInsn.vA);
       }
     }
     DCHECK(copied_first);  // At least one predecessor must have been processed before this bb.
   }
-  // At this point, ssa_regs_to_check shows which sregs have an object definition with
+  // At this point, vregs_to_check shows which sregs have an object definition with
   // no intervening uses.
 
   // Walk through the instruction in the block, updating as necessary
   for (MIR* mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
-    if (mir->ssa_rep == NULL) {
-        continue;
-    }
-
     uint64_t df_attributes = GetDataFlowAttributes(mir);
 
+    DCHECK_EQ(df_attributes & DF_NULL_TRANSFER_N, 0u);  // No Phis yet.
+
     // Might need a null check?
     if (df_attributes & DF_HAS_NULL_CHKS) {
-      int src_idx;
-      if (df_attributes & DF_NULL_CHK_1) {
-        src_idx = 1;
-      } else if (df_attributes & DF_NULL_CHK_2) {
-        src_idx = 2;
+      int src_vreg;
+      if (df_attributes & DF_NULL_CHK_OUT0) {
+        DCHECK_NE(df_attributes & DF_IS_INVOKE, 0u);
+        src_vreg = mir->dalvikInsn.vC;
+      } else if (df_attributes & DF_NULL_CHK_B) {
+        DCHECK_NE(df_attributes & DF_REF_B, 0u);
+        src_vreg = mir->dalvikInsn.vB;
       } else {
-        src_idx = 0;
+        DCHECK_NE(df_attributes & DF_NULL_CHK_A, 0u);
+        DCHECK_NE(df_attributes & DF_REF_A, 0u);
+        src_vreg = mir->dalvikInsn.vA;
       }
-      int src_sreg = mir->ssa_rep->uses[src_idx];
-      if (!ssa_regs_to_check->IsBitSet(src_sreg)) {
+      if (!vregs_to_check->IsBitSet(src_vreg)) {
         // Eliminate the null check.
-        mir->optimization_flags |= MIR_IGNORE_NULL_CHECK;
+        mir->optimization_flags |= MIR_MARK;
       } else {
         // Do the null check.
-        // TODO: Rewrite the pass to converge first before doing any modifications so that
-        // we don't lose the MIR_IGNORE_NULL_CHECK here if previously set by some other pass.
-        mir->optimization_flags &= ~MIR_IGNORE_NULL_CHECK;
-        // Mark s_reg as null-checked
-        ssa_regs_to_check->ClearBit(src_sreg);
+        mir->optimization_flags &= ~MIR_MARK;
+        // Mark src_vreg as null-checked.
+        vregs_to_check->ClearBit(src_vreg);
       }
     }
 
@@ -947,66 +1017,41 @@
      * Note: we can't tell if a CONST definition might be used as an object, so treat
      * them all as object definitions.
      */
-    if (((df_attributes & (DF_DA | DF_REF_A)) == (DF_DA | DF_REF_A)) ||
+    if ((df_attributes & (DF_DA | DF_REF_A)) == (DF_DA | DF_REF_A) ||
         (df_attributes & DF_SETS_CONST))  {
-      ssa_regs_to_check->SetBit(mir->ssa_rep->defs[0]);
+      vregs_to_check->SetBit(mir->dalvikInsn.vA);
     }
 
-    // Now, remove mark from all object definitions we know are non-null.
+    // Then, remove mark from all object definitions we know are non-null.
     if (df_attributes & DF_NON_NULL_DST) {
       // Mark target of NEW* as non-null
-      ssa_regs_to_check->ClearBit(mir->ssa_rep->defs[0]);
+      DCHECK_NE(df_attributes & DF_REF_A, 0u);
+      vregs_to_check->ClearBit(mir->dalvikInsn.vA);
     }
 
     // Mark non-null returns from invoke-style NEW*
     if (df_attributes & DF_NON_NULL_RET) {
       MIR* next_mir = mir->next;
       // Next should be an MOVE_RESULT_OBJECT
-      if (next_mir &&
-          next_mir->dalvikInsn.opcode == Instruction::MOVE_RESULT_OBJECT) {
-        // Mark as null checked
-        ssa_regs_to_check->ClearBit(next_mir->ssa_rep->defs[0]);
+      if (UNLIKELY(next_mir == nullptr)) {
+        // The MethodVerifier makes sure there's no MOVE_RESULT at the catch entry or branch
+        // target, so the MOVE_RESULT cannot be broken away into another block.
+        LOG(WARNING) << "Unexpected end of block following new";
+      } else if (UNLIKELY(next_mir->dalvikInsn.opcode != Instruction::MOVE_RESULT_OBJECT)) {
+        LOG(WARNING) << "Unexpected opcode following new: " << next_mir->dalvikInsn.opcode;
       } else {
-        if (next_mir) {
-          LOG(WARNING) << "Unexpected opcode following new: " << next_mir->dalvikInsn.opcode;
-        } else if (bb->fall_through != NullBasicBlockId) {
-          // Look in next basic block
-          struct BasicBlock* next_bb = GetBasicBlock(bb->fall_through);
-          for (MIR* tmir = next_bb->first_mir_insn; tmir != NULL;
-            tmir =tmir->next) {
-            if (MIR::DecodedInstruction::IsPseudoMirOp(tmir->dalvikInsn.opcode)) {
-              continue;
-            }
-            // First non-pseudo should be MOVE_RESULT_OBJECT
-            if (tmir->dalvikInsn.opcode == Instruction::MOVE_RESULT_OBJECT) {
-              // Mark as null checked
-              ssa_regs_to_check->ClearBit(tmir->ssa_rep->defs[0]);
-            } else {
-              LOG(WARNING) << "Unexpected op after new: " << tmir->dalvikInsn.opcode;
-            }
-            break;
-          }
-        }
+        // Mark as null checked.
+        vregs_to_check->ClearBit(next_mir->dalvikInsn.vA);
       }
     }
 
-    /*
-     * Propagate nullcheck state on register copies (including
-     * Phi pseudo copies.  For the latter, nullcheck state is
-     * the "or" of all the Phi's operands.
-     */
-    if (df_attributes & (DF_NULL_TRANSFER_0 | DF_NULL_TRANSFER_N)) {
-      int tgt_sreg = mir->ssa_rep->defs[0];
-      int operands = (df_attributes & DF_NULL_TRANSFER_0) ? 1 :
-          mir->ssa_rep->num_uses;
-      bool needs_null_check = false;
-      for (int i = 0; i < operands; i++) {
-        needs_null_check |= ssa_regs_to_check->IsBitSet(mir->ssa_rep->uses[i]);
-      }
-      if (needs_null_check) {
-        ssa_regs_to_check->SetBit(tgt_sreg);
+    // Propagate null check state on register copies.
+    if (df_attributes & DF_NULL_TRANSFER_0) {
+      DCHECK_EQ(df_attributes | ~(DF_DA | DF_REF_A | DF_UB | DF_REF_B), static_cast<uint64_t>(-1));
+      if (vregs_to_check->IsBitSet(mir->dalvikInsn.vB)) {
+        vregs_to_check->SetBit(mir->dalvikInsn.vA);
       } else {
-        ssa_regs_to_check->ClearBit(tgt_sreg);
+        vregs_to_check->ClearBit(mir->dalvikInsn.vA);
       }
     }
   }
@@ -1016,15 +1061,15 @@
   ArenaBitVector* old_ending_ssa_regs_to_check = temp_bit_matrix_[bb->id];
   if (old_ending_ssa_regs_to_check == nullptr) {
     DCHECK(temp_scoped_alloc_.get() != nullptr);
-    nce_changed = ssa_regs_to_check->GetHighestBitSet() != -1;
-    temp_bit_matrix_[bb->id] = ssa_regs_to_check;
-    // Create a new ssa_regs_to_check for next BB.
+    nce_changed = vregs_to_check->GetHighestBitSet() != -1;
+    temp_bit_matrix_[bb->id] = vregs_to_check;
+    // Create a new vregs_to_check for next BB.
     temp_bit_vector_ = new (temp_scoped_alloc_.get()) ArenaBitVector(
         temp_scoped_alloc_.get(), temp_bit_vector_size_, false, kBitMapNullCheck);
-  } else if (!ssa_regs_to_check->SameBitsSet(old_ending_ssa_regs_to_check)) {
+  } else if (!vregs_to_check->SameBitsSet(old_ending_ssa_regs_to_check)) {
     nce_changed = true;
-    temp_bit_matrix_[bb->id] = ssa_regs_to_check;
-    temp_bit_vector_ = old_ending_ssa_regs_to_check;  // Reuse for ssa_regs_to_check for next BB.
+    temp_bit_matrix_[bb->id] = vregs_to_check;
+    temp_bit_vector_ = old_ending_ssa_regs_to_check;  // Reuse for vregs_to_check for next BB.
   }
   return nce_changed;
 }
@@ -1036,6 +1081,18 @@
   temp_bit_matrix_ = nullptr;
   DCHECK(temp_scoped_alloc_.get() != nullptr);
   temp_scoped_alloc_.reset();
+
+  // converge MIR_MARK with MIR_IGNORE_NULL_CHECK
+  AllNodesIterator iter(this);
+  for (BasicBlock* bb = iter.Next(); bb != nullptr; bb = iter.Next()) {
+    for (MIR* mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
+      constexpr int kMarkToIgnoreNullCheckShift = kMIRMark - kMIRIgnoreNullCheck;
+      COMPILE_ASSERT(kMarkToIgnoreNullCheckShift > 0, check_valid_shift_right);
+      uint16_t mirMarkAdjustedToIgnoreNullCheck =
+          (mir->optimization_flags & MIR_MARK) >> kMarkToIgnoreNullCheckShift;
+      mir->optimization_flags |= mirMarkAdjustedToIgnoreNullCheck;
+    }
+  }
 }
 
 /*
@@ -1100,26 +1157,27 @@
     // First, find all SGET/SPUTs that may need class initialization checks, record INVOKE_STATICs.
     AllNodesIterator iter(this);
     for (BasicBlock* bb = iter.Next(); bb != nullptr; bb = iter.Next()) {
-      for (MIR* mir = bb->first_mir_insn; mir != nullptr; mir = mir->next) {
-        DCHECK(bb->data_flow_info != nullptr);
-        if (mir->dalvikInsn.opcode >= Instruction::SGET &&
-            mir->dalvikInsn.opcode <= Instruction::SPUT_SHORT) {
-          const MirSFieldLoweringInfo& field_info = GetSFieldLoweringInfo(mir);
-          uint16_t index = 0xffffu;
-          if (!field_info.IsInitialized()) {
-            DCHECK_LT(class_to_index_map.size(), 0xffffu);
-            MapEntry entry = {
-                // Treat unresolved fields as if each had its own class.
-                field_info.IsResolved() ? field_info.DeclaringDexFile()
-                                        : nullptr,
-                field_info.IsResolved() ? field_info.DeclaringClassIndex()
-                                        : field_info.FieldIndex(),
-                static_cast<uint16_t>(class_to_index_map.size())
-            };
-            index = class_to_index_map.insert(entry).first->index;
+      if (bb->block_type == kDalvikByteCode) {
+        for (MIR* mir = bb->first_mir_insn; mir != nullptr; mir = mir->next) {
+          if (mir->dalvikInsn.opcode >= Instruction::SGET &&
+              mir->dalvikInsn.opcode <= Instruction::SPUT_SHORT) {
+            const MirSFieldLoweringInfo& field_info = GetSFieldLoweringInfo(mir);
+            uint16_t index = 0xffffu;
+            if (!field_info.IsInitialized()) {
+              DCHECK_LT(class_to_index_map.size(), 0xffffu);
+              MapEntry entry = {
+                  // Treat unresolved fields as if each had its own class.
+                  field_info.IsResolved() ? field_info.DeclaringDexFile()
+                                          : nullptr,
+                  field_info.IsResolved() ? field_info.DeclaringClassIndex()
+                                          : field_info.FieldIndex(),
+                  static_cast<uint16_t>(class_to_index_map.size())
+              };
+              index = class_to_index_map.insert(entry).first->index;
+            }
+            // Using offset/2 for index into temp_insn_data_.
+            temp_insn_data_[mir->offset / 2u] = index;
           }
-          // Using offset/2 for index into temp_insn_data_.
-          temp_insn_data_[mir->offset / 2u] = index;
         }
       }
     }
@@ -1148,7 +1206,9 @@
  */
 bool MIRGraph::EliminateClassInitChecks(BasicBlock* bb) {
   DCHECK_EQ((cu_->disable_opt & (1 << kClassInitCheckElimination)), 0u);
-  if (bb->data_flow_info == nullptr) {
+  if (bb->block_type != kDalvikByteCode && bb->block_type != kEntryBlock) {
+    // Ignore the kExitBlock as well.
+    DCHECK(bb->first_mir_insn == nullptr);
     return false;
   }
 
@@ -1163,7 +1223,6 @@
     BasicBlock* pred_bb = GetBasicBlock(bb->predecessors[0]);
     // pred_bb must have already been processed at least once.
     DCHECK(pred_bb != nullptr);
-    DCHECK(pred_bb->data_flow_info != nullptr);
     DCHECK(temp_bit_matrix_[pred_bb->id] != nullptr);
     classes_to_check->Copy(temp_bit_matrix_[pred_bb->id]);
   } else {
@@ -1172,7 +1231,6 @@
     for (BasicBlockId pred_id : bb->predecessors) {
       BasicBlock* pred_bb = GetBasicBlock(pred_id);
       DCHECK(pred_bb != nullptr);
-      DCHECK(pred_bb->data_flow_info != nullptr);
       if (temp_bit_matrix_[pred_bb->id] == nullptr) {
         continue;
       }
diff --git a/compiler/dex/mir_optimization_test.cc b/compiler/dex/mir_optimization_test.cc
index 55e547e..337d4ef 100644
--- a/compiler/dex/mir_optimization_test.cc
+++ b/compiler/dex/mir_optimization_test.cc
@@ -23,15 +23,8 @@
 
 namespace art {
 
-class ClassInitCheckEliminationTest : public testing::Test {
+class MirOptimizationTest : public testing::Test {
  protected:
-  struct SFieldDef {
-    uint16_t field_idx;
-    uintptr_t declaring_dex_file;
-    uint16_t declaring_class_idx;
-    uint16_t declaring_field_idx;
-  };
-
   struct BBDef {
     static constexpr size_t kMaxSuccessors = 4;
     static constexpr size_t kMaxPredecessors = 4;
@@ -44,9 +37,12 @@
   };
 
   struct MIRDef {
-    Instruction::Code opcode;
     BasicBlockId bbid;
-    uint32_t field_or_method_info;
+    Instruction::Code opcode;
+    uint32_t field_info;
+    uint32_t vA;
+    uint32_t vB;
+    uint32_t vC;
   };
 
 #define DEF_SUCC0() \
@@ -72,32 +68,6 @@
 #define DEF_BB(type, succ, pred) \
     { type, succ, pred }
 
-#define DEF_MIR(opcode, bb, field_info) \
-    { opcode, bb, field_info }
-
-  void DoPrepareSFields(const SFieldDef* defs, size_t count) {
-    cu_.mir_graph->sfield_lowering_infos_.clear();
-    cu_.mir_graph->sfield_lowering_infos_.reserve(count);
-    for (size_t i = 0u; i != count; ++i) {
-      const SFieldDef* def = &defs[i];
-      MirSFieldLoweringInfo field_info(def->field_idx);
-      if (def->declaring_dex_file != 0u) {
-        field_info.declaring_dex_file_ = reinterpret_cast<const DexFile*>(def->declaring_dex_file);
-        field_info.declaring_class_idx_ = def->declaring_class_idx;
-        field_info.declaring_field_idx_ = def->declaring_field_idx;
-        field_info.flags_ = MirSFieldLoweringInfo::kFlagIsStatic;
-      }
-      ASSERT_EQ(def->declaring_dex_file != 0u, field_info.IsResolved());
-      ASSERT_FALSE(field_info.IsInitialized());
-      cu_.mir_graph->sfield_lowering_infos_.push_back(field_info);
-    }
-  }
-
-  template <size_t count>
-  void PrepareSFields(const SFieldDef (&defs)[count]) {
-    DoPrepareSFields(defs, count);
-  }
-
   void DoPrepareBasicBlocks(const BBDef* defs, size_t count) {
     cu_.mir_graph->block_id_map_.clear();
     cu_.mir_graph->block_list_.clear();
@@ -145,6 +115,63 @@
     DoPrepareBasicBlocks(defs, count);
   }
 
+  void PrepareSingleBlock() {
+    static const BBDef bbs[] = {
+        DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
+        DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
+        DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(3)),
+        DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(1)),
+    };
+    PrepareBasicBlocks(bbs);
+  }
+
+  void PrepareDiamond() {
+    static const BBDef bbs[] = {
+        DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
+        DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
+        DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(6)),
+        DEF_BB(kDalvikByteCode, DEF_SUCC2(4, 5), DEF_PRED1(1)),
+        DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)),
+        DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)),
+        DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED2(4, 5)),
+    };
+    PrepareBasicBlocks(bbs);
+  }
+
+  void PrepareLoop() {
+    static const BBDef bbs[] = {
+        DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
+        DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
+        DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(5)),
+        DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(1)),
+        DEF_BB(kDalvikByteCode, DEF_SUCC2(5, 4), DEF_PRED2(3, 4)),  // "taken" loops to self.
+        DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(4)),
+    };
+    PrepareBasicBlocks(bbs);
+  }
+
+  void PrepareCatch() {
+    static const BBDef bbs[] = {
+        DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
+        DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
+        DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(6)),
+        DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(1)),     // The top.
+        DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)),     // The throwing insn.
+        DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)),     // Catch handler.
+        DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED2(4, 5)),  // The merged block.
+    };
+    PrepareBasicBlocks(bbs);
+    BasicBlock* catch_handler = cu_.mir_graph->GetBasicBlock(5u);
+    catch_handler->catch_entry = true;
+    // Add successor block info to the check block.
+    BasicBlock* check_bb = cu_.mir_graph->GetBasicBlock(3u);
+    check_bb->successor_block_list_type = kCatch;
+    SuccessorBlockInfo* successor_block_info = reinterpret_cast<SuccessorBlockInfo*>
+        (cu_.arena.Alloc(sizeof(SuccessorBlockInfo), kArenaAllocSuccessor));
+    successor_block_info->block = catch_handler->id;
+    check_bb->successor_blocks.push_back(successor_block_info);
+  }
+
   void DoPrepareMIRs(const MIRDef* defs, size_t count) {
     mir_count_ = count;
     mirs_ = reinterpret_cast<MIR*>(cu_.arena.Alloc(sizeof(MIR) * count, kArenaAllocMIR));
@@ -157,9 +184,15 @@
       BasicBlock* bb = cu_.mir_graph->block_list_[def->bbid];
       bb->AppendMIR(mir);
       if (def->opcode >= Instruction::SGET && def->opcode <= Instruction::SPUT_SHORT) {
-        ASSERT_LT(def->field_or_method_info, cu_.mir_graph->sfield_lowering_infos_.size());
-        mir->meta.sfield_lowering_info = def->field_or_method_info;
+        ASSERT_LT(def->field_info, cu_.mir_graph->sfield_lowering_infos_.size());
+        mir->meta.sfield_lowering_info = def->field_info;
+      } else if (def->opcode >= Instruction::IGET && def->opcode <= Instruction::IPUT_SHORT) {
+        ASSERT_LT(def->field_info, cu_.mir_graph->ifield_lowering_infos_.size());
+        mir->meta.ifield_lowering_info = def->field_info;
       }
+      mir->dalvikInsn.vA = def->vA;
+      mir->dalvikInsn.vB = def->vB;
+      mir->dalvikInsn.vC = def->vC;
       mir->ssa_rep = nullptr;
       mir->offset = 2 * i;  // All insns need to be at least 2 code units long.
       mir->optimization_flags = 0u;
@@ -179,29 +212,14 @@
     DoPrepareMIRs(defs, count);
   }
 
-  void PerformClassInitCheckElimination() {
-    cu_.mir_graph->SSATransformationStart();
-    cu_.mir_graph->ComputeDFSOrders();
-    cu_.mir_graph->ComputeDominators();
-    cu_.mir_graph->ComputeTopologicalSortOrder();
-    cu_.mir_graph->SSATransformationEnd();
-    bool gate_result = cu_.mir_graph->EliminateClassInitChecksGate();
-    ASSERT_TRUE(gate_result);
-    LoopRepeatingTopologicalSortIterator iterator(cu_.mir_graph.get());
-    bool change = false;
-    for (BasicBlock* bb = iterator.Next(change); bb != nullptr; bb = iterator.Next(change)) {
-      change = cu_.mir_graph->EliminateClassInitChecks(bb);
-    }
-    cu_.mir_graph->EliminateClassInitChecksEnd();
-  }
-
-  ClassInitCheckEliminationTest()
+  MirOptimizationTest()
       : pool_(),
         cu_(&pool_),
         mir_count_(0u),
         mirs_(nullptr),
         code_item_(nullptr) {
     cu_.mir_graph.reset(new MIRGraph(&cu_, &cu_.arena));
+    cu_.access_flags = kAccStatic;  // Don't let "this" interfere with this test.
   }
 
   ArenaPool pool_;
@@ -211,6 +229,109 @@
   DexFile::CodeItem* code_item_;
 };
 
+class ClassInitCheckEliminationTest : public MirOptimizationTest {
+ protected:
+  struct SFieldDef {
+    uint16_t field_idx;
+    uintptr_t declaring_dex_file;
+    uint16_t declaring_class_idx;
+    uint16_t declaring_field_idx;
+  };
+
+  void DoPrepareSFields(const SFieldDef* defs, size_t count) {
+    cu_.mir_graph->sfield_lowering_infos_.clear();
+    cu_.mir_graph->sfield_lowering_infos_.reserve(count);
+    for (size_t i = 0u; i != count; ++i) {
+      const SFieldDef* def = &defs[i];
+      MirSFieldLoweringInfo field_info(def->field_idx);
+      if (def->declaring_dex_file != 0u) {
+        field_info.declaring_dex_file_ = reinterpret_cast<const DexFile*>(def->declaring_dex_file);
+        field_info.declaring_class_idx_ = def->declaring_class_idx;
+        field_info.declaring_field_idx_ = def->declaring_field_idx;
+        field_info.flags_ = MirSFieldLoweringInfo::kFlagIsStatic;
+      }
+      ASSERT_EQ(def->declaring_dex_file != 0u, field_info.IsResolved());
+      ASSERT_FALSE(field_info.IsInitialized());
+      cu_.mir_graph->sfield_lowering_infos_.push_back(field_info);
+    }
+  }
+
+  template <size_t count>
+  void PrepareSFields(const SFieldDef (&defs)[count]) {
+    DoPrepareSFields(defs, count);
+  }
+
+  void PerformClassInitCheckElimination() {
+    cu_.mir_graph->ComputeDFSOrders();
+    bool gate_result = cu_.mir_graph->EliminateClassInitChecksGate();
+    ASSERT_TRUE(gate_result);
+    RepeatingPreOrderDfsIterator iterator(cu_.mir_graph.get());
+    bool change = false;
+    for (BasicBlock* bb = iterator.Next(change); bb != nullptr; bb = iterator.Next(change)) {
+      change = cu_.mir_graph->EliminateClassInitChecks(bb);
+    }
+    cu_.mir_graph->EliminateClassInitChecksEnd();
+  }
+
+  ClassInitCheckEliminationTest()
+      : MirOptimizationTest() {
+  }
+};
+
+class NullCheckEliminationTest : public MirOptimizationTest {
+ protected:
+  struct IFieldDef {
+    uint16_t field_idx;
+    uintptr_t declaring_dex_file;
+    uint16_t declaring_class_idx;
+    uint16_t declaring_field_idx;
+  };
+
+  void DoPrepareIFields(const IFieldDef* defs, size_t count) {
+    cu_.mir_graph->ifield_lowering_infos_.clear();
+    cu_.mir_graph->ifield_lowering_infos_.reserve(count);
+    for (size_t i = 0u; i != count; ++i) {
+      const IFieldDef* def = &defs[i];
+      MirIFieldLoweringInfo field_info(def->field_idx);
+      if (def->declaring_dex_file != 0u) {
+        field_info.declaring_dex_file_ = reinterpret_cast<const DexFile*>(def->declaring_dex_file);
+        field_info.declaring_class_idx_ = def->declaring_class_idx;
+        field_info.declaring_field_idx_ = def->declaring_field_idx;
+      }
+      ASSERT_EQ(def->declaring_dex_file != 0u, field_info.IsResolved());
+      cu_.mir_graph->ifield_lowering_infos_.push_back(field_info);
+    }
+  }
+
+  template <size_t count>
+  void PrepareIFields(const IFieldDef (&defs)[count]) {
+    DoPrepareIFields(defs, count);
+  }
+
+  void PerformNullCheckElimination() {
+    // Make vregs in range [100, 1000) input registers, i.e. requiring a null check.
+    code_item_->registers_size_ = 1000;
+    code_item_->ins_size_ = 900;
+
+    cu_.mir_graph->ComputeDFSOrders();
+    bool gate_result = cu_.mir_graph->EliminateNullChecksGate();
+    ASSERT_TRUE(gate_result);
+    RepeatingPreOrderDfsIterator iterator(cu_.mir_graph.get());
+    bool change = false;
+    for (BasicBlock* bb = iterator.Next(change); bb != nullptr; bb = iterator.Next(change)) {
+      change = cu_.mir_graph->EliminateNullChecks(bb);
+    }
+    cu_.mir_graph->EliminateNullChecksEnd();
+  }
+
+  NullCheckEliminationTest()
+      : MirOptimizationTest() {
+  }
+};
+
+#define DEF_SGET_SPUT_V0(bb, opcode, field_info) \
+    { bb, opcode, field_info, 0u, 0u, 0u }
+
 TEST_F(ClassInitCheckEliminationTest, SingleBlock) {
   static const SFieldDef sfields[] = {
       { 0u, 1u, 0u, 0u },
@@ -220,31 +341,25 @@
       { 4u, 1u, 3u, 4u },  // Same declaring class as sfield[3].
       { 5u, 0u, 0u, 0u },  // Unresolved.
   };
-  static const BBDef bbs[] = {
-      DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
-      DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
-      DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(3)),
-      DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(1)),
-  };
   static const MIRDef mirs[] = {
-      DEF_MIR(Instruction::SPUT, 3u, 5u),  // Unresolved.
-      DEF_MIR(Instruction::SPUT, 3u, 0u),
-      DEF_MIR(Instruction::SGET, 3u, 1u),
-      DEF_MIR(Instruction::SGET, 3u, 2u),
-      DEF_MIR(Instruction::SGET, 3u, 5u),  // Unresolved.
-      DEF_MIR(Instruction::SGET, 3u, 0u),
-      DEF_MIR(Instruction::SGET, 3u, 1u),
-      DEF_MIR(Instruction::SGET, 3u, 2u),
-      DEF_MIR(Instruction::SGET, 3u, 5u),  // Unresolved.
-      DEF_MIR(Instruction::SGET, 3u, 3u),
-      DEF_MIR(Instruction::SGET, 3u, 4u),
+      DEF_SGET_SPUT_V0(3u, Instruction::SPUT, 5u),  // Unresolved.
+      DEF_SGET_SPUT_V0(3u, Instruction::SPUT, 0u),
+      DEF_SGET_SPUT_V0(3u, Instruction::SGET, 1u),
+      DEF_SGET_SPUT_V0(3u, Instruction::SGET, 2u),
+      DEF_SGET_SPUT_V0(3u, Instruction::SGET, 5u),  // Unresolved.
+      DEF_SGET_SPUT_V0(3u, Instruction::SGET, 0u),
+      DEF_SGET_SPUT_V0(3u, Instruction::SGET, 1u),
+      DEF_SGET_SPUT_V0(3u, Instruction::SGET, 2u),
+      DEF_SGET_SPUT_V0(3u, Instruction::SGET, 5u),  // Unresolved.
+      DEF_SGET_SPUT_V0(3u, Instruction::SGET, 3u),
+      DEF_SGET_SPUT_V0(3u, Instruction::SGET, 4u),
   };
   static const bool expected_ignore_clinit_check[] = {
       false, false, false, false, true, true, true, true, true, false, true
   };
 
   PrepareSFields(sfields);
-  PrepareBasicBlocks(bbs);
+  PrepareSingleBlock();
   PrepareMIRs(mirs);
   PerformClassInitCheckElimination();
   ASSERT_EQ(arraysize(expected_ignore_clinit_check), mir_count_);
@@ -268,40 +383,31 @@
       { 9u, 1u, 8u, 9u },  // Same declaring class as sfield[8].
       { 10u, 0u, 0u, 0u },  // Unresolved.
   };
-  static const BBDef bbs[] = {
-      DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
-      DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
-      DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(6)),
-      DEF_BB(kDalvikByteCode, DEF_SUCC2(4, 5), DEF_PRED1(1)),
-      DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)),
-      DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)),
-      DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED2(4, 5)),
-  };
   static const MIRDef mirs[] = {
       // NOTE: MIRs here are ordered by unique tests. They will be put into appropriate blocks.
-      DEF_MIR(Instruction::SGET, 3u, 10u),  // Unresolved.
-      DEF_MIR(Instruction::SPUT, 3u, 10u),  // Unresolved.
-      DEF_MIR(Instruction::SPUT, 3u, 0u),
-      DEF_MIR(Instruction::SGET, 6u, 0u),  // Eliminated (block #3 dominates #6).
-      DEF_MIR(Instruction::SPUT, 4u, 1u),
-      DEF_MIR(Instruction::SGET, 6u, 1u),  // Not eliminated (block #4 doesn't dominate #6).
-      DEF_MIR(Instruction::SGET, 3u, 2u),
-      DEF_MIR(Instruction::SGET, 4u, 2u),  // Eliminated (block #3 dominates #4).
-      DEF_MIR(Instruction::SGET, 3u, 3u),
-      DEF_MIR(Instruction::SGET, 5u, 3u),  // Eliminated (block #3 dominates #5).
-      DEF_MIR(Instruction::SGET, 3u, 4u),
-      DEF_MIR(Instruction::SGET, 6u, 4u),  // Eliminated (block #3 dominates #6).
-      DEF_MIR(Instruction::SGET, 4u, 5u),
-      DEF_MIR(Instruction::SGET, 6u, 5u),  // Not eliminated (block #4 doesn't dominate #6).
-      DEF_MIR(Instruction::SGET, 5u, 6u),
-      DEF_MIR(Instruction::SGET, 6u, 6u),  // Not eliminated (block #5 doesn't dominate #6).
-      DEF_MIR(Instruction::SGET, 4u, 7u),
-      DEF_MIR(Instruction::SGET, 5u, 7u),
-      DEF_MIR(Instruction::SGET, 6u, 7u),  // Eliminated (initialized in both blocks #3 and #4).
-      DEF_MIR(Instruction::SGET, 4u, 8u),
-      DEF_MIR(Instruction::SGET, 5u, 9u),
-      DEF_MIR(Instruction::SGET, 6u, 8u),  // Eliminated (with sfield[9] in block #5).
-      DEF_MIR(Instruction::SPUT, 6u, 9u),  // Eliminated (with sfield[8] in block #4).
+      DEF_SGET_SPUT_V0(3u, Instruction::SGET, 10u),  // Unresolved.
+      DEF_SGET_SPUT_V0(3u, Instruction::SPUT, 10u),  // Unresolved.
+      DEF_SGET_SPUT_V0(3u, Instruction::SPUT, 0u),
+      DEF_SGET_SPUT_V0(6u, Instruction::SGET, 0u),  // Eliminated (BB #3 dominates #6).
+      DEF_SGET_SPUT_V0(4u, Instruction::SPUT, 1u),
+      DEF_SGET_SPUT_V0(6u, Instruction::SGET, 1u),  // Not eliminated (BB #4 doesn't dominate #6).
+      DEF_SGET_SPUT_V0(3u, Instruction::SGET, 2u),
+      DEF_SGET_SPUT_V0(4u, Instruction::SGET, 2u),  // Eliminated (BB #3 dominates #4).
+      DEF_SGET_SPUT_V0(3u, Instruction::SGET, 3u),
+      DEF_SGET_SPUT_V0(5u, Instruction::SGET, 3u),  // Eliminated (BB #3 dominates #5).
+      DEF_SGET_SPUT_V0(3u, Instruction::SGET, 4u),
+      DEF_SGET_SPUT_V0(6u, Instruction::SGET, 4u),  // Eliminated (BB #3 dominates #6).
+      DEF_SGET_SPUT_V0(4u, Instruction::SGET, 5u),
+      DEF_SGET_SPUT_V0(6u, Instruction::SGET, 5u),  // Not eliminated (BB #4 doesn't dominate #6).
+      DEF_SGET_SPUT_V0(5u, Instruction::SGET, 6u),
+      DEF_SGET_SPUT_V0(6u, Instruction::SGET, 6u),  // Not eliminated (BB #5 doesn't dominate #6).
+      DEF_SGET_SPUT_V0(4u, Instruction::SGET, 7u),
+      DEF_SGET_SPUT_V0(5u, Instruction::SGET, 7u),
+      DEF_SGET_SPUT_V0(6u, Instruction::SGET, 7u),  // Eliminated (initialized in both #3 and #4).
+      DEF_SGET_SPUT_V0(4u, Instruction::SGET, 8u),
+      DEF_SGET_SPUT_V0(5u, Instruction::SGET, 9u),
+      DEF_SGET_SPUT_V0(6u, Instruction::SGET, 8u),  // Eliminated (with sfield[9] in BB #5).
+      DEF_SGET_SPUT_V0(6u, Instruction::SPUT, 9u),  // Eliminated (with sfield[8] in BB #4).
   };
   static const bool expected_ignore_clinit_check[] = {
       false, true,          // Unresolved: sfield[10], method[2]
@@ -317,7 +423,7 @@
   };
 
   PrepareSFields(sfields);
-  PrepareBasicBlocks(bbs);
+  PrepareDiamond();
   PrepareMIRs(mirs);
   PerformClassInitCheckElimination();
   ASSERT_EQ(arraysize(expected_ignore_clinit_check), mir_count_);
@@ -332,26 +438,18 @@
       { 0u, 1u, 0u, 0u },
       { 1u, 1u, 1u, 1u },
   };
-  static const BBDef bbs[] = {
-      DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
-      DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
-      DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(5)),
-      DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(1)),
-      DEF_BB(kDalvikByteCode, DEF_SUCC2(5, 4), DEF_PRED2(3, 4)),  // "taken" loops to self.
-      DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(4)),
-  };
   static const MIRDef mirs[] = {
-      DEF_MIR(Instruction::SGET, 3u, 0u),
-      DEF_MIR(Instruction::SGET, 4u, 1u),
-      DEF_MIR(Instruction::SGET, 5u, 0u),  // Eliminated.
-      DEF_MIR(Instruction::SGET, 5u, 1u),  // Eliminated.
+      DEF_SGET_SPUT_V0(3u, Instruction::SGET, 0u),
+      DEF_SGET_SPUT_V0(4u, Instruction::SGET, 1u),
+      DEF_SGET_SPUT_V0(5u, Instruction::SGET, 0u),  // Eliminated.
+      DEF_SGET_SPUT_V0(5u, Instruction::SGET, 1u),  // Eliminated.
   };
   static const bool expected_ignore_clinit_check[] = {
       false, false, true, true
   };
 
   PrepareSFields(sfields);
-  PrepareBasicBlocks(bbs);
+  PrepareLoop();
   PrepareMIRs(mirs);
   PerformClassInitCheckElimination();
   ASSERT_EQ(arraysize(expected_ignore_clinit_check), mir_count_);
@@ -368,42 +466,24 @@
       { 2u, 1u, 2u, 2u },
       { 3u, 1u, 3u, 3u },
   };
-  static const BBDef bbs[] = {
-      DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
-      DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
-      DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(6)),
-      DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(1)),     // The top.
-      DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)),     // The throwing insn.
-      DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)),     // Catch handler.
-      DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED2(4, 5)),  // The merged block.
-  };
   static const MIRDef mirs[] = {
-      DEF_MIR(Instruction::SGET, 3u, 0u),  // Before the exception edge.
-      DEF_MIR(Instruction::SGET, 3u, 1u),  // Before the exception edge.
-      DEF_MIR(Instruction::SGET, 4u, 2u),  // After the exception edge.
-      DEF_MIR(Instruction::SGET, 4u, 3u),  // After the exception edge.
-      DEF_MIR(Instruction::SGET, 5u, 0u),  // In catch handler; class init check eliminated.
-      DEF_MIR(Instruction::SGET, 5u, 2u),  // In catch handler; class init check not eliminated.
-      DEF_MIR(Instruction::SGET, 6u, 0u),  // Class init check eliminated.
-      DEF_MIR(Instruction::SGET, 6u, 1u),  // Class init check eliminated.
-      DEF_MIR(Instruction::SGET, 6u, 2u),  // Class init check eliminated.
-      DEF_MIR(Instruction::SGET, 6u, 3u),  // Class init check not eliminated.
+      DEF_SGET_SPUT_V0(3u, Instruction::SGET, 0u),  // Before the exception edge.
+      DEF_SGET_SPUT_V0(3u, Instruction::SGET, 1u),  // Before the exception edge.
+      DEF_SGET_SPUT_V0(4u, Instruction::SGET, 2u),  // After the exception edge.
+      DEF_SGET_SPUT_V0(4u, Instruction::SGET, 3u),  // After the exception edge.
+      DEF_SGET_SPUT_V0(5u, Instruction::SGET, 0u),  // In catch handler; clinit check eliminated.
+      DEF_SGET_SPUT_V0(5u, Instruction::SGET, 2u),  // In catch handler; clinit check not eliminated.
+      DEF_SGET_SPUT_V0(6u, Instruction::SGET, 0u),  // Class init check eliminated.
+      DEF_SGET_SPUT_V0(6u, Instruction::SGET, 1u),  // Class init check eliminated.
+      DEF_SGET_SPUT_V0(6u, Instruction::SGET, 2u),  // Class init check eliminated.
+      DEF_SGET_SPUT_V0(6u, Instruction::SGET, 3u),  // Class init check not eliminated.
   };
   static const bool expected_ignore_clinit_check[] = {
       false, false, false, false, true, false, true, true, true, false
   };
 
   PrepareSFields(sfields);
-  PrepareBasicBlocks(bbs);
-  BasicBlock* catch_handler = cu_.mir_graph->GetBasicBlock(5u);
-  catch_handler->catch_entry = true;
-  // Add successor block info to the check block.
-  BasicBlock* check_bb = cu_.mir_graph->GetBasicBlock(3u);
-  check_bb->successor_block_list_type = kCatch;
-  SuccessorBlockInfo* successor_block_info = reinterpret_cast<SuccessorBlockInfo*>
-      (cu_.arena.Alloc(sizeof(SuccessorBlockInfo), kArenaAllocSuccessor));
-  successor_block_info->block = catch_handler->id;
-  check_bb->successor_blocks.push_back(successor_block_info);
+  PrepareCatch();
   PrepareMIRs(mirs);
   PerformClassInitCheckElimination();
   ASSERT_EQ(arraysize(expected_ignore_clinit_check), mir_count_);
@@ -413,4 +493,189 @@
   }
 }
 
+#define DEF_IGET_IPUT(bb, opcode, vA, vB, field_info) \
+    { bb, opcode, field_info, vA, vB, 0u }
+#define DEF_AGET_APUT(bb, opcode, vA, vB, vC) \
+    { bb, opcode, 0u, vA, vB, vC }
+#define DEF_INVOKE(bb, opcode, vC) \
+    { bb, opcode, 0u, 0u, 0u, vC }
+#define DEF_OTHER1(bb, opcode, vA) \
+    { bb, opcode, 0u, vA, 0u, 0u }
+#define DEF_OTHER2(bb, opcode, vA, vB) \
+    { bb, opcode, 0u, vA, vB, 0u }
+
+TEST_F(NullCheckEliminationTest, SingleBlock) {
+  static const IFieldDef ifields[] = {
+      { 0u, 1u, 0u, 0u },
+      { 1u, 1u, 0u, 1u },
+      { 2u, 1u, 0u, 2u },  // Object.
+  };
+  static const MIRDef mirs[] = {
+      DEF_IGET_IPUT(3u, Instruction::IGET_OBJECT, 0u, 100u, 2u),
+      DEF_IGET_IPUT(3u, Instruction::IGET, 1u, 0u, 1u),
+      DEF_IGET_IPUT(3u, Instruction::IGET_OBJECT, 2u, 100u, 2u),  // Differs from 0u (no LVN here).
+      DEF_IGET_IPUT(3u, Instruction::IGET, 3u, 2u, 1u),
+      DEF_IGET_IPUT(3u, Instruction::IGET, 4u, 101u, 0u),
+      DEF_IGET_IPUT(3u, Instruction::IGET, 5u, 102u, 0u),
+      DEF_IGET_IPUT(3u, Instruction::IGET, 6u, 103u, 0u),
+      DEF_IGET_IPUT(3u, Instruction::IGET, 7u, 103u, 1u),
+      DEF_IGET_IPUT(3u, Instruction::IPUT, 8u, 104u, 0u),
+      DEF_IGET_IPUT(3u, Instruction::IPUT, 9u, 104u, 1u),
+      DEF_IGET_IPUT(3u, Instruction::IGET, 10u, 105u, 0u),
+      DEF_IGET_IPUT(3u, Instruction::IPUT, 11u, 105u, 1u),
+      DEF_IGET_IPUT(3u, Instruction::IPUT, 12u, 106u, 0u),
+      DEF_IGET_IPUT(3u, Instruction::IGET, 13u, 106u, 1u),
+      DEF_INVOKE(3u, Instruction::INVOKE_DIRECT, 107),
+      DEF_IGET_IPUT(3u, Instruction::IGET, 15u, 107u, 1u),
+      DEF_IGET_IPUT(3u, Instruction::IGET, 16u, 108u, 0u),
+      DEF_INVOKE(3u, Instruction::INVOKE_DIRECT, 108),
+      DEF_AGET_APUT(3u, Instruction::AGET, 18u, 109u, 110u),
+      DEF_AGET_APUT(3u, Instruction::APUT, 19u, 109u, 111u),
+      DEF_OTHER2(3u, Instruction::ARRAY_LENGTH, 20u, 112u),
+      DEF_AGET_APUT(3u, Instruction::AGET, 21u, 112u, 113u),
+      DEF_OTHER1(3u, Instruction::MONITOR_ENTER, 114u),
+      DEF_OTHER1(3u, Instruction::MONITOR_EXIT, 114u),
+  };
+  static const bool expected_ignore_null_check[] = {
+      false, false, true, false /* Not doing LVN. */,
+      false, true /* Set before running NCE. */,
+      false, true,  // IGET, IGET
+      false, true,  // IPUT, IPUT
+      false, true,  // IGET, IPUT
+      false, true,  // IPUT, IGET
+      false, true,  // INVOKE, IGET
+      false, true,  // IGET, INVOKE
+      false, true,  // AGET, APUT
+      false, true,  // ARRAY_LENGTH, AGET
+      false, true,  // MONITOR_ENTER, MONITOR_EXIT
+  };
+
+  PrepareIFields(ifields);
+  PrepareSingleBlock();
+  PrepareMIRs(mirs);
+
+  // Mark IGET 5u as null-checked to test that NCE doesn't clear this flag.
+  mirs_[5u].optimization_flags |= MIR_IGNORE_NULL_CHECK;
+
+  PerformNullCheckElimination();
+  ASSERT_EQ(arraysize(expected_ignore_null_check), mir_count_);
+  for (size_t i = 0u; i != arraysize(mirs); ++i) {
+    EXPECT_EQ(expected_ignore_null_check[i],
+              (mirs_[i].optimization_flags & MIR_IGNORE_NULL_CHECK) != 0) << i;
+  }
+}
+
+TEST_F(NullCheckEliminationTest, Diamond) {
+  static const IFieldDef ifields[] = {
+      { 0u, 1u, 0u, 0u },
+      { 1u, 1u, 0u, 1u },
+      { 2u, 1u, 0u, 2u },  // int[].
+  };
+  static const MIRDef mirs[] = {
+      // NOTE: MIRs here are ordered by unique tests. They will be put into appropriate blocks.
+      DEF_IGET_IPUT(3u, Instruction::IPUT, 0u, 100u, 0u),
+      DEF_IGET_IPUT(6u, Instruction::IGET, 1u, 100u, 1u),  // Eliminated (BB #3 dominates #6).
+      DEF_IGET_IPUT(3u, Instruction::IGET, 2u, 101u, 0u),
+      DEF_IGET_IPUT(4u, Instruction::IPUT, 3u, 101u, 0u),  // Eliminated (BB #3 dominates #4).
+      DEF_IGET_IPUT(3u, Instruction::IGET, 4u, 102u, 0u),
+      DEF_IGET_IPUT(5u, Instruction::IPUT, 5u, 102u, 1u),  // Eliminated (BB #3 dominates #5).
+      DEF_IGET_IPUT(4u, Instruction::IPUT, 6u, 103u, 0u),
+      DEF_IGET_IPUT(6u, Instruction::IPUT, 7u, 103u, 1u),  // Not eliminated (going through BB #5).
+      DEF_IGET_IPUT(5u, Instruction::IGET, 8u, 104u, 1u),
+      DEF_IGET_IPUT(6u, Instruction::IGET, 9u, 104u, 0u),  // Not eliminated (going through BB #4).
+      DEF_INVOKE(4u, Instruction::INVOKE_DIRECT, 105u),
+      DEF_IGET_IPUT(5u, Instruction::IGET, 11u, 105u, 1u),
+      DEF_IGET_IPUT(6u, Instruction::IPUT, 12u, 105u, 0u),  // Eliminated.
+      DEF_IGET_IPUT(3u, Instruction::IGET_OBJECT, 13u, 106u, 2u),
+      DEF_OTHER1(3u, Instruction::IF_EQZ, 13u),            // Last insn in the BB #3.
+      DEF_OTHER2(5u, Instruction::NEW_ARRAY, 13u, 107u),
+      DEF_AGET_APUT(6u, Instruction::AGET, 16u, 13u, 108u),  // Eliminated.
+  };
+  static const bool expected_ignore_null_check[] = {
+      false, true,   // BB #3 IPUT, BB #6 IGET
+      false, true,   // BB #3 IGET, BB #4 IPUT
+      false, true,   // BB #3 IGET, BB #5 IPUT
+      false, false,  // BB #4 IPUT, BB #6 IPUT
+      false, false,  // BB #5 IGET, BB #6 IGET
+      false, false, true,  // BB #4 INVOKE, BB #5 IGET, BB #6 IPUT
+      false, false,  // BB #3 IGET_OBJECT & IF_EQZ
+      false, true,   // BB #5 NEW_ARRAY, BB #6 AGET
+  };
+
+  PrepareIFields(ifields);
+  PrepareDiamond();
+  PrepareMIRs(mirs);
+  PerformNullCheckElimination();
+  ASSERT_EQ(arraysize(expected_ignore_null_check), mir_count_);
+  for (size_t i = 0u; i != arraysize(mirs); ++i) {
+    EXPECT_EQ(expected_ignore_null_check[i],
+              (mirs_[i].optimization_flags & MIR_IGNORE_NULL_CHECK) != 0) << i;
+  }
+}
+
+TEST_F(NullCheckEliminationTest, Loop) {
+  static const IFieldDef ifields[] = {
+      { 0u, 1u, 0u, 0u },
+      { 1u, 1u, 1u, 1u },
+  };
+  static const MIRDef mirs[] = {
+      DEF_IGET_IPUT(3u, Instruction::IGET, 0u, 100u, 0u),
+      DEF_IGET_IPUT(4u, Instruction::IGET, 1u, 101u, 0u),
+      DEF_IGET_IPUT(5u, Instruction::IGET, 2u, 100u, 1u),  // Eliminated.
+      DEF_IGET_IPUT(5u, Instruction::IGET, 3u, 101u, 1u),  // Eliminated.
+      DEF_IGET_IPUT(3u, Instruction::IGET, 4u, 102u, 0u),
+      DEF_IGET_IPUT(4u, Instruction::IGET, 5u, 102u, 1u),  // Not eliminated (MOVE_OBJECT_16).
+      DEF_OTHER2(4u, Instruction::MOVE_OBJECT_16, 102u, 103u),
+  };
+  static const bool expected_ignore_null_check[] = {
+      false, false, true, true,
+      false, false, false,
+  };
+
+  PrepareIFields(ifields);
+  PrepareLoop();
+  PrepareMIRs(mirs);
+  PerformNullCheckElimination();
+  ASSERT_EQ(arraysize(expected_ignore_null_check), mir_count_);
+  for (size_t i = 0u; i != arraysize(mirs); ++i) {
+    EXPECT_EQ(expected_ignore_null_check[i],
+              (mirs_[i].optimization_flags & MIR_IGNORE_NULL_CHECK) != 0) << i;
+  }
+}
+
+TEST_F(NullCheckEliminationTest, Catch) {
+  static const IFieldDef ifields[] = {
+      { 0u, 1u, 0u, 0u },
+      { 1u, 1u, 1u, 1u },
+  };
+  static const MIRDef mirs[] = {
+      DEF_IGET_IPUT(3u, Instruction::IGET, 0u, 100u, 0u),  // Before the exception edge.
+      DEF_IGET_IPUT(3u, Instruction::IGET, 1u, 101u, 0u),  // Before the exception edge.
+      DEF_IGET_IPUT(4u, Instruction::IGET, 2u, 102u, 0u),  // After the exception edge.
+      DEF_IGET_IPUT(4u, Instruction::IGET, 3u, 103u, 0u),  // After the exception edge.
+      DEF_IGET_IPUT(5u, Instruction::IGET, 4u, 100u, 1u),  // In catch handler; eliminated.
+      DEF_IGET_IPUT(5u, Instruction::IGET, 5u, 102u, 1u),  // In catch handler; not eliminated.
+      DEF_IGET_IPUT(6u, Instruction::IGET, 6u, 100u, 0u),  // Null check eliminated.
+      DEF_IGET_IPUT(6u, Instruction::IGET, 6u, 101u, 1u),  // Null check eliminated.
+      DEF_IGET_IPUT(6u, Instruction::IGET, 6u, 102u, 0u),  // Null check eliminated.
+      DEF_IGET_IPUT(6u, Instruction::IGET, 6u, 103u, 1u),  // Null check not eliminated.
+  };
+  static const bool expected_ignore_null_check[] = {
+      false, false, false, false, true, false, true, true, true, false
+  };
+
+  PrepareIFields(ifields);
+  PrepareCatch();
+  PrepareMIRs(mirs);
+  PerformNullCheckElimination();
+  ASSERT_EQ(arraysize(expected_ignore_null_check), mir_count_);
+  for (size_t i = 0u; i != arraysize(mirs); ++i) {
+    EXPECT_EQ(expected_ignore_null_check[i],
+              (mirs_[i].optimization_flags & MIR_IGNORE_NULL_CHECK) != 0) << i;
+  }
+}
+
+// Undefine MIR_DEF for null check elimination.
+#undef MIR_DEF
+
 }  // namespace art
diff --git a/compiler/dex/pass.h b/compiler/dex/pass.h
index c377426..e349eed 100644
--- a/compiler/dex/pass.h
+++ b/compiler/dex/pass.h
@@ -85,6 +85,9 @@
     // Unused parameter.
     UNUSED(data);
 
+    // Passes that do all their work in Start() or End() should not allow useless node iteration.
+    DCHECK(false) << "Unsupported default Worker() used for " << GetName();
+
     // BasicBlock did not change.
     return false;
   }
diff --git a/compiler/dex/pass_driver_me_opts.cc b/compiler/dex/pass_driver_me_opts.cc
index cd3ffd4..a2bf8b4 100644
--- a/compiler/dex/pass_driver_me_opts.cc
+++ b/compiler/dex/pass_driver_me_opts.cc
@@ -20,6 +20,7 @@
 #include "dataflow_iterator.h"
 #include "dataflow_iterator-inl.h"
 #include "pass_driver_me_opts.h"
+#include "post_opt_passes.h"
 
 namespace art {
 
@@ -35,13 +36,15 @@
 const Pass* const PassDriver<PassDriverMEOpts>::g_passes[] = {
   GetPassInstance<CacheFieldLoweringInfo>(),
   GetPassInstance<CacheMethodLoweringInfo>(),
-  GetPassInstance<SpecialMethodInliner>(),
-  GetPassInstance<CodeLayout>(),
-  GetPassInstance<NullCheckElimination>(),
-  GetPassInstance<TypeInference>(),
+  GetPassInstance<CalculatePredecessors>(),
+  GetPassInstance<DFSOrders>(),
   GetPassInstance<ClassInitCheckElimination>(),
-  GetPassInstance<GlobalValueNumberingPass>(),
+  GetPassInstance<SpecialMethodInliner>(),
+  GetPassInstance<NullCheckElimination>(),
   GetPassInstance<BBCombine>(),
+  GetPassInstance<CodeLayout>(),
+  GetPassInstance<TypeInference>(),
+  GetPassInstance<GlobalValueNumberingPass>(),
   GetPassInstance<BBOptimizations>(),
 };
 
diff --git a/compiler/dex/pass_driver_me_post_opt.cc b/compiler/dex/pass_driver_me_post_opt.cc
index 4acab6c..e6238e9 100644
--- a/compiler/dex/pass_driver_me_post_opt.cc
+++ b/compiler/dex/pass_driver_me_post_opt.cc
@@ -33,7 +33,6 @@
 const Pass* const PassDriver<PassDriverMEPostOpt>::g_passes[] = {
   GetPassInstance<InitializeData>(),
   GetPassInstance<ClearPhiInstructions>(),
-  GetPassInstance<CalculatePredecessors>(),
   GetPassInstance<DFSOrders>(),
   GetPassInstance<BuildDomination>(),
   GetPassInstance<TopologicalSortOrders>(),
diff --git a/compiler/dex/post_opt_passes.h b/compiler/dex/post_opt_passes.h
index e7805ba..7b84ba8 100644
--- a/compiler/dex/post_opt_passes.h
+++ b/compiler/dex/post_opt_passes.h
@@ -30,7 +30,7 @@
  */
 class InitializeData : public PassME {
  public:
-  InitializeData() : PassME("InitializeData") {
+  InitializeData() : PassME("InitializeData", kNoNodes) {
   }
 
   void Start(PassDataHolder* data) const {
@@ -76,7 +76,7 @@
  */
 class CalculatePredecessors : public PassME {
  public:
-  CalculatePredecessors() : PassME("CalculatePredecessors") {
+  CalculatePredecessors() : PassME("CalculatePredecessors", kNoNodes) {
   }
 
   void Start(PassDataHolder* data) const;
@@ -88,7 +88,14 @@
  */
 class DFSOrders : public PassME {
  public:
-  DFSOrders() : PassME("DFSOrders") {
+  DFSOrders() : PassME("DFSOrders", kNoNodes) {
+  }
+
+  bool Gate(const PassDataHolder* data) const {
+    DCHECK(data != nullptr);
+    CompilationUnit* c_unit = down_cast<const PassMEDataHolder*>(data)->c_unit;
+    DCHECK(c_unit != nullptr);
+    return !c_unit->mir_graph->DfsOrdersUpToDate();
   }
 
   void Start(PassDataHolder* data) const {
@@ -105,7 +112,7 @@
  */
 class BuildDomination : public PassME {
  public:
-  BuildDomination() : PassME("BuildDomination") {
+  BuildDomination() : PassME("BuildDomination", kNoNodes) {
   }
 
   void Start(PassDataHolder* data) const {
@@ -133,7 +140,7 @@
  */
 class TopologicalSortOrders : public PassME {
  public:
-  TopologicalSortOrders() : PassME("TopologicalSortOrders") {
+  TopologicalSortOrders() : PassME("TopologicalSortOrders", kNoNodes) {
   }
 
   void Start(PassDataHolder* data) const {
@@ -150,7 +157,7 @@
  */
 class DefBlockMatrix : public PassME {
  public:
-  DefBlockMatrix() : PassME("DefBlockMatrix") {
+  DefBlockMatrix() : PassME("DefBlockMatrix", kNoNodes) {
   }
 
   void Start(PassDataHolder* data) const {
@@ -167,7 +174,7 @@
  */
 class CreatePhiNodes : public PassME {
  public:
-  CreatePhiNodes() : PassME("CreatePhiNodes") {
+  CreatePhiNodes() : PassME("CreatePhiNodes", kNoNodes) {
   }
 
   void Start(PassDataHolder* data) const {
@@ -185,7 +192,7 @@
 
 class ClearVisitedFlag : public PassME {
  public:
-  ClearVisitedFlag() : PassME("ClearVisitedFlag") {
+  ClearVisitedFlag() : PassME("ClearVisitedFlag", kNoNodes) {
   }
 
   void Start(PassDataHolder* data) const {
@@ -202,7 +209,7 @@
  */
 class SSAConversion : public PassME {
  public:
-  SSAConversion() : PassME("SSAConversion") {
+  SSAConversion() : PassME("SSAConversion", kNoNodes) {
   }
 
   void Start(PassDataHolder* data) const {
@@ -241,7 +248,7 @@
  */
 class PerformInitRegLocations : public PassME {
  public:
-  PerformInitRegLocations() : PassME("PerformInitRegLocation") {
+  PerformInitRegLocations() : PassME("PerformInitRegLocation", kNoNodes) {
   }
 
   void Start(PassDataHolder* data) const {
@@ -286,7 +293,7 @@
  */
 class FreeData : public PassME {
  public:
-  FreeData() : PassME("FreeData") {
+  FreeData() : PassME("FreeData", kNoNodes) {
   }
 
   void End(PassDataHolder* data) const {
diff --git a/compiler/dex/ssa_transformation.cc b/compiler/dex/ssa_transformation.cc
index 4388041..412f85d 100644
--- a/compiler/dex/ssa_transformation.cc
+++ b/compiler/dex/ssa_transformation.cc
@@ -66,8 +66,9 @@
 }
 
 void MIRGraph::RecordDFSOrders(BasicBlock* block) {
-  DCHECK(temp_scoped_alloc_.get() != nullptr);
-  ScopedArenaVector<BasicBlock*> succ(temp_scoped_alloc_->Adapter());
+  ScopedArenaAllocator allocator(&cu_->arena_stack);
+  ScopedArenaVector<BasicBlock*> succ(allocator.Adapter());
+  succ.reserve(GetNumBlocks());
   MarkPreOrder(block);
   succ.push_back(block);
   while (!succ.empty()) {
@@ -107,10 +108,11 @@
     AllNodesIterator iter(this);
     for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
       if (!bb->visited) {
-        bb->Hide(cu_);
+        bb->Hide(this);
       }
     }
   }
+  dfs_orders_up_to_date_ = true;
 }
 
 /*
diff --git a/compiler/optimizing/code_generator.cc b/compiler/optimizing/code_generator.cc
index 29dbd8b..408e13e 100644
--- a/compiler/optimizing/code_generator.cc
+++ b/compiler/optimizing/code_generator.cc
@@ -36,7 +36,7 @@
   const GrowableArray<HBasicBlock*>& blocks = GetGraph()->GetBlocks();
   DCHECK(blocks.Get(0) == GetGraph()->GetEntryBlock());
   DCHECK(GoesToNextBlock(GetGraph()->GetEntryBlock(), blocks.Get(1)));
-  block_labels_.SetSize(blocks.Size());
+  Initialize();
 
   DCHECK_EQ(frame_size_, kUninitializedFrameSize);
   if (!is_leaf) {
@@ -54,7 +54,7 @@
   HGraphVisitor* instruction_visitor = GetInstructionVisitor();
   for (size_t i = 0, e = blocks.Size(); i < e; ++i) {
     HBasicBlock* block = blocks.Get(i);
-    Bind(GetLabelOf(block));
+    Bind(block);
     for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
       HInstruction* current = it.Current();
       current->Accept(location_builder);
@@ -76,13 +76,13 @@
   const GrowableArray<HBasicBlock*>& blocks = GetGraph()->GetBlocks();
   DCHECK(blocks.Get(0) == GetGraph()->GetEntryBlock());
   DCHECK(GoesToNextBlock(GetGraph()->GetEntryBlock(), blocks.Get(1)));
-  block_labels_.SetSize(blocks.Size());
+  Initialize();
 
   GenerateFrameEntry();
   HGraphVisitor* instruction_visitor = GetInstructionVisitor();
   for (size_t i = 0, e = blocks.Size(); i < e; ++i) {
     HBasicBlock* block = blocks.Get(i);
-    Bind(GetLabelOf(block));
+    Bind(block);
     for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
       HInstruction* current = it.Current();
       current->Accept(instruction_visitor);
@@ -273,10 +273,6 @@
   return current->GetBlockId() + 1 == next->GetBlockId();
 }
 
-Label* CodeGenerator::GetLabelOf(HBasicBlock* block) const {
-  return block_labels_.GetRawStorage() + block->GetBlockId();
-}
-
 CodeGenerator* CodeGenerator::Create(ArenaAllocator* allocator,
                                      HGraph* graph,
                                      InstructionSet instruction_set) {
diff --git a/compiler/optimizing/code_generator.h b/compiler/optimizing/code_generator.h
index 4eba791..7aaf991 100644
--- a/compiler/optimizing/code_generator.h
+++ b/compiler/optimizing/code_generator.h
@@ -24,13 +24,13 @@
 #include "memory_region.h"
 #include "nodes.h"
 #include "stack_map_stream.h"
-#include "utils/assembler.h"
 
 namespace art {
 
 static size_t constexpr kVRegSize = 4;
 static size_t constexpr kUninitializedFrameSize = 0;
 
+class Assembler;
 class CodeGenerator;
 class DexCompilationUnit;
 class SrcMap;
@@ -53,18 +53,12 @@
 
 class SlowPathCode : public ArenaObject {
  public:
-  SlowPathCode() : entry_label_(), exit_label_() {}
+  SlowPathCode() {}
   virtual ~SlowPathCode() {}
 
-  Label* GetEntryLabel() { return &entry_label_; }
-  Label* GetExitLabel() { return &exit_label_; }
-
   virtual void EmitNativeCode(CodeGenerator* codegen) = 0;
 
  private:
-  Label entry_label_;
-  Label exit_label_;
-
   DISALLOW_COPY_AND_ASSIGN(SlowPathCode);
 };
 
@@ -80,7 +74,6 @@
 
   HGraph* GetGraph() const { return graph_; }
 
-  Label* GetLabelOf(HBasicBlock* block) const;
   bool GoesToNextBlock(HBasicBlock* current, HBasicBlock* next) const;
 
   size_t GetStackSlotOfParameter(HParameterValue* parameter) const {
@@ -90,9 +83,10 @@
         + parameter->GetIndex() * kVRegSize;
   }
 
+  virtual void Initialize() = 0;
   virtual void GenerateFrameEntry() = 0;
   virtual void GenerateFrameExit() = 0;
-  virtual void Bind(Label* label) = 0;
+  virtual void Bind(HBasicBlock* block) = 0;
   virtual void Move(HInstruction* instruction, Location location, HInstruction* move_for) = 0;
   virtual HGraphVisitor* GetLocationBuilder() = 0;
   virtual HGraphVisitor* GetInstructionVisitor() = 0;
@@ -167,7 +161,6 @@
         number_of_fpu_registers_(number_of_fpu_registers),
         number_of_register_pairs_(number_of_register_pairs),
         graph_(graph),
-        block_labels_(graph->GetArena(), 0),
         pc_infos_(graph->GetArena(), 32),
         slow_paths_(graph->GetArena(), 8),
         is_leaf_(true),
@@ -205,8 +198,6 @@
 
   HGraph* const graph_;
 
-  // Labels for each block that will be compiled.
-  GrowableArray<Label> block_labels_;
   GrowableArray<PcInfo> pc_infos_;
   GrowableArray<SlowPathCode*> slow_paths_;
 
diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc
index 9be7802..cdee845 100644
--- a/compiler/optimizing/code_generator_arm.cc
+++ b/compiler/optimizing/code_generator_arm.cc
@@ -60,7 +60,21 @@
 
 #define __ reinterpret_cast<ArmAssembler*>(codegen->GetAssembler())->
 
-class NullCheckSlowPathARM : public SlowPathCode {
+class SlowPathCodeARM : public SlowPathCode {
+ public:
+  SlowPathCodeARM() : entry_label_(), exit_label_() {}
+
+  Label* GetEntryLabel() { return &entry_label_; }
+  Label* GetExitLabel() { return &exit_label_; }
+
+ private:
+  Label entry_label_;
+  Label exit_label_;
+
+  DISALLOW_COPY_AND_ASSIGN(SlowPathCodeARM);
+};
+
+class NullCheckSlowPathARM : public SlowPathCodeARM {
  public:
   explicit NullCheckSlowPathARM(HNullCheck* instruction) : instruction_(instruction) {}
 
@@ -77,7 +91,7 @@
   DISALLOW_COPY_AND_ASSIGN(NullCheckSlowPathARM);
 };
 
-class StackOverflowCheckSlowPathARM : public SlowPathCode {
+class StackOverflowCheckSlowPathARM : public SlowPathCodeARM {
  public:
   StackOverflowCheckSlowPathARM() {}
 
@@ -91,12 +105,13 @@
   DISALLOW_COPY_AND_ASSIGN(StackOverflowCheckSlowPathARM);
 };
 
-class SuspendCheckSlowPathARM : public SlowPathCode {
+class SuspendCheckSlowPathARM : public SlowPathCodeARM {
  public:
   explicit SuspendCheckSlowPathARM(HSuspendCheck* instruction, HBasicBlock* successor)
       : instruction_(instruction), successor_(successor) {}
 
   virtual void EmitNativeCode(CodeGenerator* codegen) OVERRIDE {
+    CodeGeneratorARM* arm_codegen = down_cast<CodeGeneratorARM*>(codegen);
     __ Bind(GetEntryLabel());
     codegen->SaveLiveRegisters(instruction_->GetLocations());
     int32_t offset = QUICK_ENTRYPOINT_OFFSET(kArmWordSize, pTestSuspend).Int32Value();
@@ -107,7 +122,7 @@
     if (successor_ == nullptr) {
       __ b(GetReturnLabel());
     } else {
-      __ b(codegen->GetLabelOf(successor_));
+      __ b(arm_codegen->GetLabelOf(successor_));
     }
   }
 
@@ -127,7 +142,7 @@
   DISALLOW_COPY_AND_ASSIGN(SuspendCheckSlowPathARM);
 };
 
-class BoundsCheckSlowPathARM : public SlowPathCode {
+class BoundsCheckSlowPathARM : public SlowPathCodeARM {
  public:
   BoundsCheckSlowPathARM(HBoundsCheck* instruction,
                          Location index_location,
@@ -137,7 +152,7 @@
         length_location_(length_location) {}
 
   virtual void EmitNativeCode(CodeGenerator* codegen) OVERRIDE {
-    CodeGeneratorARM* arm_codegen = reinterpret_cast<CodeGeneratorARM*>(codegen);
+    CodeGeneratorARM* arm_codegen = down_cast<CodeGeneratorARM*>(codegen);
     __ Bind(GetEntryLabel());
     InvokeRuntimeCallingConvention calling_convention;
     arm_codegen->Move32(Location::RegisterLocation(calling_convention.GetRegisterAt(0)), index_location_);
@@ -205,6 +220,7 @@
 
 CodeGeneratorARM::CodeGeneratorARM(HGraph* graph)
     : CodeGenerator(graph, kNumberOfCoreRegisters, kNumberOfDRegisters, kNumberOfRegisterPairs),
+      block_labels_(graph->GetArena(), 0),
       location_builder_(graph, this),
       instruction_visitor_(graph, this),
       move_resolver_(graph->GetArena(), this),
@@ -313,7 +329,7 @@
   bool skip_overflow_check = IsLeafMethod() && !FrameNeedsStackCheck(GetFrameSize(), InstructionSet::kArm);
   if (!skip_overflow_check) {
     if (kExplicitStackOverflowCheck) {
-      SlowPathCode* slow_path = new (GetGraph()->GetArena()) StackOverflowCheckSlowPathARM();
+      SlowPathCodeARM* slow_path = new (GetGraph()->GetArena()) StackOverflowCheckSlowPathARM();
       AddSlowPath(slow_path);
 
       __ LoadFromOffset(kLoadWord, IP, TR, Thread::StackEndOffset<kArmWordSize>().Int32Value());
@@ -339,8 +355,8 @@
   __ PopList(1 << PC | 1 << R6 | 1 << R7);
 }
 
-void CodeGeneratorARM::Bind(Label* label) {
-  __ Bind(label);
+void CodeGeneratorARM::Bind(HBasicBlock* block) {
+  __ Bind(GetLabelOf(block));
 }
 
 Location CodeGeneratorARM::GetStackLocation(HLoadLocal* load) const {
@@ -641,36 +657,51 @@
 
 void InstructionCodeGeneratorARM::VisitIf(HIf* if_instr) {
   HInstruction* cond = if_instr->InputAt(0);
-  if (!cond->IsCondition() || cond->AsCondition()->NeedsMaterialization()) {
-    // Condition has been materialized, compare the output to 0
-    DCHECK(if_instr->GetLocations()->InAt(0).IsRegister());
-    __ cmp(if_instr->GetLocations()->InAt(0).As<Register>(),
-           ShifterOperand(0));
-    __ b(codegen_->GetLabelOf(if_instr->IfTrueSuccessor()), NE);
-  } else {
-    // Condition has not been materialized, use its inputs as the comparison and its
-    // condition as the branch condition.
-    LocationSummary* locations = cond->GetLocations();
-    if (locations->InAt(1).IsRegister()) {
-      __ cmp(locations->InAt(0).As<Register>(),
-             ShifterOperand(locations->InAt(1).As<Register>()));
-    } else {
-      DCHECK(locations->InAt(1).IsConstant());
-      int32_t value = locations->InAt(1).GetConstant()->AsIntConstant()->GetValue();
-      ShifterOperand operand;
-      if (ShifterOperand::CanHoldArm(value, &operand)) {
-        __ cmp(locations->InAt(0).As<Register>(), ShifterOperand(value));
-      } else {
-        Register temp = IP;
-        __ LoadImmediate(temp, value);
-        __ cmp(locations->InAt(0).As<Register>(), ShifterOperand(temp));
+  if (cond->IsIntConstant()) {
+    // Constant condition, statically compared against 1.
+    int32_t cond_value = cond->AsIntConstant()->GetValue();
+    if (cond_value == 1) {
+      if (!codegen_->GoesToNextBlock(if_instr->GetBlock(),
+                                     if_instr->IfTrueSuccessor())) {
+        __ b(codegen_->GetLabelOf(if_instr->IfTrueSuccessor()));
       }
+      return;
+    } else {
+      DCHECK_EQ(cond_value, 0);
     }
-    __ b(codegen_->GetLabelOf(if_instr->IfTrueSuccessor()),
-         ARMCondition(cond->AsCondition()->GetCondition()));
+  } else {
+    if (!cond->IsCondition() || cond->AsCondition()->NeedsMaterialization()) {
+      // Condition has been materialized, compare the output to 0
+      DCHECK(if_instr->GetLocations()->InAt(0).IsRegister());
+      __ cmp(if_instr->GetLocations()->InAt(0).As<Register>(),
+             ShifterOperand(0));
+      __ b(codegen_->GetLabelOf(if_instr->IfTrueSuccessor()), NE);
+    } else {
+      // Condition has not been materialized, use its inputs as the
+      // comparison and its condition as the branch condition.
+      LocationSummary* locations = cond->GetLocations();
+      if (locations->InAt(1).IsRegister()) {
+        __ cmp(locations->InAt(0).As<Register>(),
+               ShifterOperand(locations->InAt(1).As<Register>()));
+      } else {
+        DCHECK(locations->InAt(1).IsConstant());
+        int32_t value =
+            locations->InAt(1).GetConstant()->AsIntConstant()->GetValue();
+        ShifterOperand operand;
+        if (ShifterOperand::CanHoldArm(value, &operand)) {
+          __ cmp(locations->InAt(0).As<Register>(), ShifterOperand(value));
+        } else {
+          Register temp = IP;
+          __ LoadImmediate(temp, value);
+          __ cmp(locations->InAt(0).As<Register>(), ShifterOperand(temp));
+        }
+      }
+      __ b(codegen_->GetLabelOf(if_instr->IfTrueSuccessor()),
+           ARMCondition(cond->AsCondition()->GetCondition()));
+    }
   }
-
-  if (!codegen_->GoesToNextBlock(if_instr->GetBlock(), if_instr->IfFalseSuccessor())) {
+  if (!codegen_->GoesToNextBlock(if_instr->GetBlock(),
+                                 if_instr->IfFalseSuccessor())) {
     __ b(codegen_->GetLabelOf(if_instr->IfFalseSuccessor()));
   }
 }
@@ -810,6 +841,7 @@
 }
 
 void InstructionCodeGeneratorARM::VisitIntConstant(HIntConstant* constant) {
+  // Will be generated at use site.
 }
 
 void LocationsBuilderARM::VisitLongConstant(HLongConstant* constant) {
@@ -1349,7 +1381,7 @@
 }
 
 void InstructionCodeGeneratorARM::VisitNullCheck(HNullCheck* instruction) {
-  SlowPathCode* slow_path = new (GetGraph()->GetArena()) NullCheckSlowPathARM(instruction);
+  SlowPathCodeARM* slow_path = new (GetGraph()->GetArena()) NullCheckSlowPathARM(instruction);
   codegen_->AddSlowPath(slow_path);
 
   LocationSummary* locations = instruction->GetLocations();
@@ -1595,7 +1627,7 @@
 
 void InstructionCodeGeneratorARM::VisitBoundsCheck(HBoundsCheck* instruction) {
   LocationSummary* locations = instruction->GetLocations();
-  SlowPathCode* slow_path = new (GetGraph()->GetArena()) BoundsCheckSlowPathARM(
+  SlowPathCodeARM* slow_path = new (GetGraph()->GetArena()) BoundsCheckSlowPathARM(
       instruction, locations->InAt(0), locations->InAt(1));
   codegen_->AddSlowPath(slow_path);
 
diff --git a/compiler/optimizing/code_generator_arm.h b/compiler/optimizing/code_generator_arm.h
index 874db0f..7c063f1 100644
--- a/compiler/optimizing/code_generator_arm.h
+++ b/compiler/optimizing/code_generator_arm.h
@@ -140,7 +140,7 @@
 
   virtual void GenerateFrameEntry() OVERRIDE;
   virtual void GenerateFrameExit() OVERRIDE;
-  virtual void Bind(Label* label) OVERRIDE;
+  virtual void Bind(HBasicBlock* block) OVERRIDE;
   virtual void Move(HInstruction* instruction, Location location, HInstruction* move_for) OVERRIDE;
   virtual void SaveCoreRegister(Location stack_location, uint32_t reg_id) OVERRIDE;
   virtual void RestoreCoreRegister(Location stack_location, uint32_t reg_id) OVERRIDE;
@@ -187,7 +187,17 @@
   // Emit a write barrier.
   void MarkGCCard(Register temp, Register card, Register object, Register value);
 
+  Label* GetLabelOf(HBasicBlock* block) const {
+    return block_labels_.GetRawStorage() + block->GetBlockId();
+  }
+
+  virtual void Initialize() OVERRIDE {
+    block_labels_.SetSize(GetGraph()->GetBlocks().Size());
+  }
+
  private:
+  // Labels for each block that will be compiled.
+  GrowableArray<Label> block_labels_;
   LocationsBuilderARM location_builder_;
   InstructionCodeGeneratorARM instruction_visitor_;
   ParallelMoveResolverARM move_resolver_;
diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc
index 34fa46e..98d3ad4 100644
--- a/compiler/optimizing/code_generator_x86.cc
+++ b/compiler/optimizing/code_generator_x86.cc
@@ -56,7 +56,21 @@
 
 #define __ reinterpret_cast<X86Assembler*>(codegen->GetAssembler())->
 
-class NullCheckSlowPathX86 : public SlowPathCode {
+class SlowPathCodeX86 : public SlowPathCode {
+ public:
+  SlowPathCodeX86() : entry_label_(), exit_label_() {}
+
+  Label* GetEntryLabel() { return &entry_label_; }
+  Label* GetExitLabel() { return &exit_label_; }
+
+ private:
+  Label entry_label_;
+  Label exit_label_;
+
+  DISALLOW_COPY_AND_ASSIGN(SlowPathCodeX86);
+};
+
+class NullCheckSlowPathX86 : public SlowPathCodeX86 {
  public:
   explicit NullCheckSlowPathX86(HNullCheck* instruction) : instruction_(instruction) {}
 
@@ -71,7 +85,7 @@
   DISALLOW_COPY_AND_ASSIGN(NullCheckSlowPathX86);
 };
 
-class StackOverflowCheckSlowPathX86 : public SlowPathCode {
+class StackOverflowCheckSlowPathX86 : public SlowPathCodeX86 {
  public:
   StackOverflowCheckSlowPathX86() {}
 
@@ -86,7 +100,7 @@
   DISALLOW_COPY_AND_ASSIGN(StackOverflowCheckSlowPathX86);
 };
 
-class BoundsCheckSlowPathX86 : public SlowPathCode {
+class BoundsCheckSlowPathX86 : public SlowPathCodeX86 {
  public:
   BoundsCheckSlowPathX86(HBoundsCheck* instruction,
                          Location index_location,
@@ -94,7 +108,7 @@
       : instruction_(instruction), index_location_(index_location), length_location_(length_location) {}
 
   virtual void EmitNativeCode(CodeGenerator* codegen) OVERRIDE {
-    CodeGeneratorX86* x86_codegen = reinterpret_cast<CodeGeneratorX86*>(codegen);
+    CodeGeneratorX86* x86_codegen = down_cast<CodeGeneratorX86*>(codegen);
     __ Bind(GetEntryLabel());
     InvokeRuntimeCallingConvention calling_convention;
     x86_codegen->Move32(Location::RegisterLocation(calling_convention.GetRegisterAt(0)), index_location_);
@@ -111,12 +125,13 @@
   DISALLOW_COPY_AND_ASSIGN(BoundsCheckSlowPathX86);
 };
 
-class SuspendCheckSlowPathX86 : public SlowPathCode {
+class SuspendCheckSlowPathX86 : public SlowPathCodeX86 {
  public:
   explicit SuspendCheckSlowPathX86(HSuspendCheck* instruction, HBasicBlock* successor)
       : instruction_(instruction), successor_(successor) {}
 
   virtual void EmitNativeCode(CodeGenerator* codegen) OVERRIDE {
+    CodeGeneratorX86* x86_codegen = down_cast<CodeGeneratorX86*>(codegen);
     __ Bind(GetEntryLabel());
     codegen->SaveLiveRegisters(instruction_->GetLocations());
     __ fs()->call(Address::Absolute(QUICK_ENTRYPOINT_OFFSET(kX86WordSize, pTestSuspend)));
@@ -125,7 +140,7 @@
     if (successor_ == nullptr) {
       __ jmp(GetReturnLabel());
     } else {
-      __ jmp(codegen->GetLabelOf(successor_));
+      __ jmp(x86_codegen->GetLabelOf(successor_));
     }
   }
 
@@ -177,6 +192,7 @@
 
 CodeGeneratorX86::CodeGeneratorX86(HGraph* graph)
     : CodeGenerator(graph, kNumberOfCpuRegisters, kNumberOfXmmRegisters, kNumberOfRegisterPairs),
+      block_labels_(graph->GetArena(), 0),
       location_builder_(graph, this),
       instruction_visitor_(graph, this),
       move_resolver_(graph->GetArena(), this) {}
@@ -276,7 +292,7 @@
   __ subl(ESP, Immediate(GetFrameSize() - kNumberOfPushedRegistersAtEntry * kX86WordSize));
 
   if (!skip_overflow_check && kExplicitStackOverflowCheck) {
-    SlowPathCode* slow_path = new (GetGraph()->GetArena()) StackOverflowCheckSlowPathX86();
+    SlowPathCodeX86* slow_path = new (GetGraph()->GetArena()) StackOverflowCheckSlowPathX86();
     AddSlowPath(slow_path);
 
     __ fs()->cmpl(ESP, Address::Absolute(Thread::StackEndOffset<kX86WordSize>()));
@@ -290,8 +306,8 @@
   __ addl(ESP, Immediate(GetFrameSize() - kNumberOfPushedRegistersAtEntry * kX86WordSize));
 }
 
-void CodeGeneratorX86::Bind(Label* label) {
-  __ Bind(label);
+void CodeGeneratorX86::Bind(HBasicBlock* block) {
+  __ Bind(GetLabelOf(block));
 }
 
 void InstructionCodeGeneratorX86::LoadCurrentMethod(Register reg) {
@@ -577,42 +593,60 @@
 
 void InstructionCodeGeneratorX86::VisitIf(HIf* if_instr) {
   HInstruction* cond = if_instr->InputAt(0);
-  bool materialized = !cond->IsCondition() || cond->AsCondition()->NeedsMaterialization();
-  // Moves do not affect the eflags register, so if the condition is evaluated
-  // just before the if, we don't need to evaluate it again.
-  bool eflags_set = cond->IsCondition()
-      && cond->AsCondition()->IsBeforeWhenDisregardMoves(if_instr);
-  if (materialized) {
-    if (!eflags_set) {
-      // Materialized condition, compare against 0.
-      Location lhs = if_instr->GetLocations()->InAt(0);
-      if (lhs.IsRegister()) {
-        __ cmpl(lhs.As<Register>(), Immediate(0));
-      } else {
-        __ cmpl(Address(ESP, lhs.GetStackIndex()), Immediate(0));
+  if (cond->IsIntConstant()) {
+    // Constant condition, statically compared against 1.
+    int32_t cond_value = cond->AsIntConstant()->GetValue();
+    if (cond_value == 1) {
+      if (!codegen_->GoesToNextBlock(if_instr->GetBlock(),
+                                     if_instr->IfTrueSuccessor())) {
+        __ jmp(codegen_->GetLabelOf(if_instr->IfTrueSuccessor()));
       }
-      __ j(kNotEqual,  codegen_->GetLabelOf(if_instr->IfTrueSuccessor()));
+      return;
     } else {
+      DCHECK_EQ(cond_value, 0);
+    }
+  } else {
+    bool materialized =
+        !cond->IsCondition() || cond->AsCondition()->NeedsMaterialization();
+    // Moves do not affect the eflags register, so if the condition is
+    // evaluated just before the if, we don't need to evaluate it
+    // again.
+    bool eflags_set = cond->IsCondition()
+        && cond->AsCondition()->IsBeforeWhenDisregardMoves(if_instr);
+    if (materialized) {
+      if (!eflags_set) {
+        // Materialized condition, compare against 0.
+        Location lhs = if_instr->GetLocations()->InAt(0);
+        if (lhs.IsRegister()) {
+          __ cmpl(lhs.As<Register>(), Immediate(0));
+        } else {
+          __ cmpl(Address(ESP, lhs.GetStackIndex()), Immediate(0));
+        }
+        __ j(kNotEqual,  codegen_->GetLabelOf(if_instr->IfTrueSuccessor()));
+      } else {
+        __ j(X86Condition(cond->AsCondition()->GetCondition()),
+             codegen_->GetLabelOf(if_instr->IfTrueSuccessor()));
+      }
+    } else {
+      Location lhs = cond->GetLocations()->InAt(0);
+      Location rhs = cond->GetLocations()->InAt(1);
+      // LHS is guaranteed to be in a register (see
+      // LocationsBuilderX86::VisitCondition).
+      if (rhs.IsRegister()) {
+        __ cmpl(lhs.As<Register>(), rhs.As<Register>());
+      } else if (rhs.IsConstant()) {
+        HIntConstant* instruction = rhs.GetConstant()->AsIntConstant();
+        Immediate imm(instruction->AsIntConstant()->GetValue());
+        __ cmpl(lhs.As<Register>(), imm);
+      } else {
+        __ cmpl(lhs.As<Register>(), Address(ESP, rhs.GetStackIndex()));
+      }
       __ j(X86Condition(cond->AsCondition()->GetCondition()),
            codegen_->GetLabelOf(if_instr->IfTrueSuccessor()));
     }
-  } else {
-    Location lhs = cond->GetLocations()->InAt(0);
-    Location rhs = cond->GetLocations()->InAt(1);
-    // LHS is guaranteed to be in a register (see LocationsBuilderX86::VisitCondition).
-    if (rhs.IsRegister()) {
-      __ cmpl(lhs.As<Register>(), rhs.As<Register>());
-    } else if (rhs.IsConstant()) {
-      HIntConstant* instruction = rhs.GetConstant()->AsIntConstant();
-      Immediate imm(instruction->AsIntConstant()->GetValue());
-      __ cmpl(lhs.As<Register>(), imm);
-    } else {
-      __ cmpl(lhs.As<Register>(), Address(ESP, rhs.GetStackIndex()));
-    }
-    __ j(X86Condition(cond->AsCondition()->GetCondition()),
-         codegen_->GetLabelOf(if_instr->IfTrueSuccessor()));
   }
-  if (!codegen_->GoesToNextBlock(if_instr->GetBlock(), if_instr->IfFalseSuccessor())) {
+  if (!codegen_->GoesToNextBlock(if_instr->GetBlock(),
+                                 if_instr->IfFalseSuccessor())) {
     __ jmp(codegen_->GetLabelOf(if_instr->IfFalseSuccessor()));
   }
 }
@@ -747,6 +781,7 @@
 }
 
 void InstructionCodeGeneratorX86::VisitIntConstant(HIntConstant* constant) {
+  // Will be generated at use site.
 }
 
 void LocationsBuilderX86::VisitLongConstant(HLongConstant* constant) {
@@ -1356,7 +1391,7 @@
 }
 
 void InstructionCodeGeneratorX86::VisitNullCheck(HNullCheck* instruction) {
-  SlowPathCode* slow_path = new (GetGraph()->GetArena()) NullCheckSlowPathX86(instruction);
+  SlowPathCodeX86* slow_path = new (GetGraph()->GetArena()) NullCheckSlowPathX86(instruction);
   codegen_->AddSlowPath(slow_path);
 
   LocationSummary* locations = instruction->GetLocations();
@@ -1658,7 +1693,7 @@
 
 void InstructionCodeGeneratorX86::VisitBoundsCheck(HBoundsCheck* instruction) {
   LocationSummary* locations = instruction->GetLocations();
-  SlowPathCode* slow_path = new (GetGraph()->GetArena()) BoundsCheckSlowPathX86(
+  SlowPathCodeX86* slow_path = new (GetGraph()->GetArena()) BoundsCheckSlowPathX86(
       instruction, locations->InAt(0), locations->InAt(1));
   codegen_->AddSlowPath(slow_path);
 
diff --git a/compiler/optimizing/code_generator_x86.h b/compiler/optimizing/code_generator_x86.h
index a1a72a2..aa5fee0 100644
--- a/compiler/optimizing/code_generator_x86.h
+++ b/compiler/optimizing/code_generator_x86.h
@@ -142,7 +142,7 @@
 
   virtual void GenerateFrameEntry() OVERRIDE;
   virtual void GenerateFrameExit() OVERRIDE;
-  virtual void Bind(Label* label) OVERRIDE;
+  virtual void Bind(HBasicBlock* block) OVERRIDE;
   virtual void Move(HInstruction* instruction, Location location, HInstruction* move_for) OVERRIDE;
   virtual void SaveCoreRegister(Location stack_location, uint32_t reg_id) OVERRIDE;
   virtual void RestoreCoreRegister(Location stack_location, uint32_t reg_id) OVERRIDE;
@@ -189,7 +189,17 @@
   // Emit a write barrier.
   void MarkGCCard(Register temp, Register card, Register object, Register value);
 
+  Label* GetLabelOf(HBasicBlock* block) const {
+    return block_labels_.GetRawStorage() + block->GetBlockId();
+  }
+
+  virtual void Initialize() OVERRIDE {
+    block_labels_.SetSize(GetGraph()->GetBlocks().Size());
+  }
+
  private:
+  // Labels for each block that will be compiled.
+  GrowableArray<Label> block_labels_;
   LocationsBuilderX86 location_builder_;
   InstructionCodeGeneratorX86 instruction_visitor_;
   ParallelMoveResolverX86 move_resolver_;
diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc
index 059140d..059ff3f 100644
--- a/compiler/optimizing/code_generator_x86_64.cc
+++ b/compiler/optimizing/code_generator_x86_64.cc
@@ -60,7 +60,21 @@
 
 #define __ reinterpret_cast<X86_64Assembler*>(codegen->GetAssembler())->
 
-class NullCheckSlowPathX86_64 : public SlowPathCode {
+class SlowPathCodeX86_64 : public SlowPathCode {
+ public:
+  SlowPathCodeX86_64() : entry_label_(), exit_label_() {}
+
+  Label* GetEntryLabel() { return &entry_label_; }
+  Label* GetExitLabel() { return &exit_label_; }
+
+ private:
+  Label entry_label_;
+  Label exit_label_;
+
+  DISALLOW_COPY_AND_ASSIGN(SlowPathCodeX86_64);
+};
+
+class NullCheckSlowPathX86_64 : public SlowPathCodeX86_64 {
  public:
   explicit NullCheckSlowPathX86_64(HNullCheck* instruction) : instruction_(instruction) {}
 
@@ -76,7 +90,7 @@
   DISALLOW_COPY_AND_ASSIGN(NullCheckSlowPathX86_64);
 };
 
-class StackOverflowCheckSlowPathX86_64 : public SlowPathCode {
+class StackOverflowCheckSlowPathX86_64 : public SlowPathCodeX86_64 {
  public:
   StackOverflowCheckSlowPathX86_64() {}
 
@@ -92,12 +106,13 @@
   DISALLOW_COPY_AND_ASSIGN(StackOverflowCheckSlowPathX86_64);
 };
 
-class SuspendCheckSlowPathX86_64 : public SlowPathCode {
+class SuspendCheckSlowPathX86_64 : public SlowPathCodeX86_64 {
  public:
   explicit SuspendCheckSlowPathX86_64(HSuspendCheck* instruction, HBasicBlock* successor)
       : instruction_(instruction), successor_(successor) {}
 
   virtual void EmitNativeCode(CodeGenerator* codegen) OVERRIDE {
+    CodeGeneratorX86_64* x64_codegen = down_cast<CodeGeneratorX86_64*>(codegen);
     __ Bind(GetEntryLabel());
     codegen->SaveLiveRegisters(instruction_->GetLocations());
     __ gs()->call(Address::Absolute(QUICK_ENTRYPOINT_OFFSET(kX86_64WordSize, pTestSuspend), true));
@@ -106,7 +121,7 @@
     if (successor_ == nullptr) {
       __ jmp(GetReturnLabel());
     } else {
-      __ jmp(codegen->GetLabelOf(successor_));
+      __ jmp(x64_codegen->GetLabelOf(successor_));
     }
   }
 
@@ -123,7 +138,7 @@
   DISALLOW_COPY_AND_ASSIGN(SuspendCheckSlowPathX86_64);
 };
 
-class BoundsCheckSlowPathX86_64 : public SlowPathCode {
+class BoundsCheckSlowPathX86_64 : public SlowPathCodeX86_64 {
  public:
   BoundsCheckSlowPathX86_64(HBoundsCheck* instruction,
                             Location index_location,
@@ -133,7 +148,7 @@
         length_location_(length_location) {}
 
   virtual void EmitNativeCode(CodeGenerator* codegen) OVERRIDE {
-    CodeGeneratorX86_64* x64_codegen = reinterpret_cast<CodeGeneratorX86_64*>(codegen);
+    CodeGeneratorX86_64* x64_codegen = down_cast<CodeGeneratorX86_64*>(codegen);
     __ Bind(GetEntryLabel());
     InvokeRuntimeCallingConvention calling_convention;
     x64_codegen->Move(Location::RegisterLocation(calling_convention.GetRegisterAt(0)), index_location_);
@@ -186,6 +201,7 @@
 
 CodeGeneratorX86_64::CodeGeneratorX86_64(HGraph* graph)
       : CodeGenerator(graph, kNumberOfCpuRegisters, kNumberOfFloatRegisters, 0),
+        block_labels_(graph->GetArena(), 0),
         location_builder_(graph, this),
         instruction_visitor_(graph, this),
         move_resolver_(graph->GetArena(), this) {}
@@ -266,7 +282,7 @@
           Immediate(GetFrameSize() - kNumberOfPushedRegistersAtEntry * kX86_64WordSize));
 
   if (!skip_overflow_check && kExplicitStackOverflowCheck) {
-    SlowPathCode* slow_path = new (GetGraph()->GetArena()) StackOverflowCheckSlowPathX86_64();
+    SlowPathCodeX86_64* slow_path = new (GetGraph()->GetArena()) StackOverflowCheckSlowPathX86_64();
     AddSlowPath(slow_path);
 
     __ gs()->cmpq(CpuRegister(RSP),
@@ -282,8 +298,8 @@
           Immediate(GetFrameSize() - kNumberOfPushedRegistersAtEntry * kX86_64WordSize));
 }
 
-void CodeGeneratorX86_64::Bind(Label* label) {
-  __ Bind(label);
+void CodeGeneratorX86_64::Bind(HBasicBlock* block) {
+  __ Bind(GetLabelOf(block));
 }
 
 void InstructionCodeGeneratorX86_64::LoadCurrentMethod(CpuRegister reg) {
@@ -479,40 +495,59 @@
 
 void InstructionCodeGeneratorX86_64::VisitIf(HIf* if_instr) {
   HInstruction* cond = if_instr->InputAt(0);
-  bool materialized = !cond->IsCondition() || cond->AsCondition()->NeedsMaterialization();
-  // Moves do not affect the eflags register, so if the condition is evaluated
-  // just before the if, we don't need to evaluate it again.
-  bool eflags_set = cond->IsCondition()
-      && cond->AsCondition()->IsBeforeWhenDisregardMoves(if_instr);
-  if (materialized) {
-    if (!eflags_set) {
-      // Materialized condition, compare against 0.
-      Location lhs = if_instr->GetLocations()->InAt(0);
-      if (lhs.IsRegister()) {
-        __ cmpl(lhs.As<CpuRegister>(), Immediate(0));
-      } else {
-        __ cmpl(Address(CpuRegister(RSP), lhs.GetStackIndex()), Immediate(0));
+  if (cond->IsIntConstant()) {
+    // Constant condition, statically compared against 1.
+    int32_t cond_value = cond->AsIntConstant()->GetValue();
+    if (cond_value == 1) {
+      if (!codegen_->GoesToNextBlock(if_instr->GetBlock(),
+                                     if_instr->IfTrueSuccessor())) {
+        __ jmp(codegen_->GetLabelOf(if_instr->IfTrueSuccessor()));
       }
-      __ j(kNotEqual, codegen_->GetLabelOf(if_instr->IfTrueSuccessor()));
+      return;
     } else {
+      DCHECK_EQ(cond_value, 0);
+    }
+  } else {
+    bool materialized =
+        !cond->IsCondition() || cond->AsCondition()->NeedsMaterialization();
+    // Moves do not affect the eflags register, so if the condition is
+    // evaluated just before the if, we don't need to evaluate it
+    // again.
+    bool eflags_set = cond->IsCondition()
+        && cond->AsCondition()->IsBeforeWhenDisregardMoves(if_instr);
+    if (materialized) {
+      if (!eflags_set) {
+        // Materialized condition, compare against 0.
+        Location lhs = if_instr->GetLocations()->InAt(0);
+        if (lhs.IsRegister()) {
+          __ cmpl(lhs.As<CpuRegister>(), Immediate(0));
+        } else {
+          __ cmpl(Address(CpuRegister(RSP), lhs.GetStackIndex()),
+                  Immediate(0));
+        }
+        __ j(kNotEqual, codegen_->GetLabelOf(if_instr->IfTrueSuccessor()));
+      } else {
+        __ j(X86_64Condition(cond->AsCondition()->GetCondition()),
+             codegen_->GetLabelOf(if_instr->IfTrueSuccessor()));
+      }
+    } else {
+      Location lhs = cond->GetLocations()->InAt(0);
+      Location rhs = cond->GetLocations()->InAt(1);
+      if (rhs.IsRegister()) {
+        __ cmpl(lhs.As<CpuRegister>(), rhs.As<CpuRegister>());
+      } else if (rhs.IsConstant()) {
+        __ cmpl(lhs.As<CpuRegister>(),
+                Immediate(rhs.GetConstant()->AsIntConstant()->GetValue()));
+      } else {
+        __ cmpl(lhs.As<CpuRegister>(),
+                Address(CpuRegister(RSP), rhs.GetStackIndex()));
+      }
       __ j(X86_64Condition(cond->AsCondition()->GetCondition()),
            codegen_->GetLabelOf(if_instr->IfTrueSuccessor()));
     }
-  } else {
-    Location lhs = cond->GetLocations()->InAt(0);
-    Location rhs = cond->GetLocations()->InAt(1);
-    if (rhs.IsRegister()) {
-      __ cmpl(lhs.As<CpuRegister>(), rhs.As<CpuRegister>());
-    } else if (rhs.IsConstant()) {
-      __ cmpl(lhs.As<CpuRegister>(),
-              Immediate(rhs.GetConstant()->AsIntConstant()->GetValue()));
-    } else {
-      __ cmpl(lhs.As<CpuRegister>(), Address(CpuRegister(RSP), rhs.GetStackIndex()));
-    }
-    __ j(X86_64Condition(cond->AsCondition()->GetCondition()),
-         codegen_->GetLabelOf(if_instr->IfTrueSuccessor()));
   }
-  if (!codegen_->GoesToNextBlock(if_instr->GetBlock(), if_instr->IfFalseSuccessor())) {
+  if (!codegen_->GoesToNextBlock(if_instr->GetBlock(),
+                                 if_instr->IfFalseSuccessor())) {
     __ jmp(codegen_->GetLabelOf(if_instr->IfFalseSuccessor()));
   }
 }
@@ -679,6 +714,7 @@
 }
 
 void InstructionCodeGeneratorX86_64::VisitIntConstant(HIntConstant* constant) {
+  // Will be generated at use site.
 }
 
 void LocationsBuilderX86_64::VisitLongConstant(HLongConstant* constant) {
@@ -688,6 +724,7 @@
 }
 
 void InstructionCodeGeneratorX86_64::VisitLongConstant(HLongConstant* constant) {
+  // Will be generated at use site.
 }
 
 void LocationsBuilderX86_64::VisitReturnVoid(HReturnVoid* ret) {
@@ -1233,7 +1270,7 @@
 }
 
 void InstructionCodeGeneratorX86_64::VisitNullCheck(HNullCheck* instruction) {
-  SlowPathCode* slow_path = new (GetGraph()->GetArena()) NullCheckSlowPathX86_64(instruction);
+  SlowPathCodeX86_64* slow_path = new (GetGraph()->GetArena()) NullCheckSlowPathX86_64(instruction);
   codegen_->AddSlowPath(slow_path);
 
   LocationSummary* locations = instruction->GetLocations();
@@ -1505,7 +1542,7 @@
 
 void InstructionCodeGeneratorX86_64::VisitBoundsCheck(HBoundsCheck* instruction) {
   LocationSummary* locations = instruction->GetLocations();
-  SlowPathCode* slow_path = new (GetGraph()->GetArena()) BoundsCheckSlowPathX86_64(
+  SlowPathCodeX86_64* slow_path = new (GetGraph()->GetArena()) BoundsCheckSlowPathX86_64(
       instruction, locations->InAt(0), locations->InAt(1));
   codegen_->AddSlowPath(slow_path);
 
diff --git a/compiler/optimizing/code_generator_x86_64.h b/compiler/optimizing/code_generator_x86_64.h
index 288f3f6..5ac0189 100644
--- a/compiler/optimizing/code_generator_x86_64.h
+++ b/compiler/optimizing/code_generator_x86_64.h
@@ -144,7 +144,7 @@
 
   virtual void GenerateFrameEntry() OVERRIDE;
   virtual void GenerateFrameExit() OVERRIDE;
-  virtual void Bind(Label* label) OVERRIDE;
+  virtual void Bind(HBasicBlock* block) OVERRIDE;
   virtual void Move(HInstruction* instruction, Location location, HInstruction* move_for) OVERRIDE;
   virtual void SaveCoreRegister(Location stack_location, uint32_t reg_id) OVERRIDE;
   virtual void RestoreCoreRegister(Location stack_location, uint32_t reg_id) OVERRIDE;
@@ -188,7 +188,17 @@
   // Helper method to move a value between two locations.
   void Move(Location destination, Location source);
 
+  Label* GetLabelOf(HBasicBlock* block) const {
+    return block_labels_.GetRawStorage() + block->GetBlockId();
+  }
+
+  virtual void Initialize() OVERRIDE {
+    block_labels_.SetSize(GetGraph()->GetBlocks().Size());
+  }
+
  private:
+  // Labels for each block that will be compiled.
+  GrowableArray<Label> block_labels_;
   LocationsBuilderX86_64 location_builder_;
   InstructionCodeGeneratorX86_64 instruction_visitor_;
   ParallelMoveResolverX86_64 move_resolver_;
diff --git a/compiler/optimizing/constant_propagation_test.cc b/compiler/optimizing/constant_propagation_test.cc
index 342777a..ff44805 100644
--- a/compiler/optimizing/constant_propagation_test.cc
+++ b/compiler/optimizing/constant_propagation_test.cc
@@ -62,7 +62,7 @@
   ASSERT_EQ(expected_after_dce, actual_after_dce);
 
   SSAChecker ssa_checker(&allocator, graph);
-  ssa_checker.VisitInsertionOrder();
+  ssa_checker.Run();
   ASSERT_TRUE(ssa_checker.IsValid());
 }
 
diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc
index fe2adc7..5655544 100644
--- a/compiler/optimizing/dead_code_elimination.cc
+++ b/compiler/optimizing/dead_code_elimination.cc
@@ -35,7 +35,10 @@
     for (i.Advance(); !i.Done(); i.Advance()) {
       HInstruction* inst = i.Current();
       DCHECK(!inst->IsControlFlow());
-      if (!inst->HasSideEffects() && !inst->HasUses() && !inst->IsSuspendCheck()) {
+      if (!inst->HasSideEffects()
+          && !inst->CanThrow()
+          && !inst->IsSuspendCheck()
+          && !inst->HasUses()) {
         block->RemoveInstruction(inst);
       }
     }
diff --git a/compiler/optimizing/dead_code_elimination_test.cc b/compiler/optimizing/dead_code_elimination_test.cc
index 245bcb2..3e0ba3a 100644
--- a/compiler/optimizing/dead_code_elimination_test.cc
+++ b/compiler/optimizing/dead_code_elimination_test.cc
@@ -47,7 +47,7 @@
   ASSERT_EQ(actual_after, expected_after);
 
   SSAChecker ssa_checker(&allocator, graph);
-  ssa_checker.VisitInsertionOrder();
+  ssa_checker.Run();
   ASSERT_TRUE(ssa_checker.IsValid());
 }
 
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index 589b44a..9f40297 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -264,21 +264,38 @@
 void SSAChecker::VisitInstruction(HInstruction* instruction) {
   super_type::VisitInstruction(instruction);
 
-  // Ensure an instruction dominates all its uses (or in the present
-  // case, that all uses of an instruction (used as input) are
-  // dominated by its definition).
-  for (HInputIterator input_it(instruction); !input_it.Done();
-       input_it.Advance()) {
-    HInstruction* input = input_it.Current();
-    if (!input->Dominates(instruction)) {
+  // Ensure an instruction dominates all its uses.
+  for (HUseIterator<HInstruction> use_it(instruction->GetUses());
+       !use_it.Done(); use_it.Advance()) {
+    HInstruction* use = use_it.Current()->GetUser();
+    if (!use->IsPhi() && !instruction->Dominates(use)) {
       std::stringstream error;
-      error << "Instruction " << input->GetId()
-            << " in block " << input->GetBlock()->GetBlockId()
-            << " does not dominate use " << instruction->GetId()
-            << " in block " << current_block_->GetBlockId() << ".";
+      error << "Instruction " << instruction->GetId()
+            << " in block " << current_block_->GetBlockId()
+            << " does not dominate use " << use->GetId()
+            << " in block " << use->GetBlock()->GetBlockId() << ".";
       errors_.Insert(error.str());
     }
   }
+
+  // Ensure an instruction having an environment is dominated by the
+  // instructions contained in the environment.
+  HEnvironment* environment = instruction->GetEnvironment();
+  if (environment != nullptr) {
+    for (size_t i = 0, e = environment->Size(); i < e; ++i) {
+      HInstruction* env_instruction = environment->GetInstructionAt(i);
+      if (env_instruction != nullptr
+          && !env_instruction->Dominates(instruction)) {
+        std::stringstream error;
+        error << "Instruction " << env_instruction->GetId()
+              << " in environment of instruction " << instruction->GetId()
+              << " from block " << current_block_->GetBlockId()
+              << " does not dominate instruction " << instruction->GetId()
+              << ".";
+        errors_.Insert(error.str());
+      }
+    }
+  }
 }
 
 void SSAChecker::VisitPhi(HPhi* phi) {
diff --git a/compiler/optimizing/graph_checker.h b/compiler/optimizing/graph_checker.h
index 34a770b..862f1b6 100644
--- a/compiler/optimizing/graph_checker.h
+++ b/compiler/optimizing/graph_checker.h
@@ -29,6 +29,9 @@
       allocator_(allocator),
       errors_(allocator, 0) {}
 
+  // Check the whole graph (in insertion order).
+  virtual void Run() { VisitInsertionOrder(); }
+
   // Check `block`.
   virtual void VisitBasicBlock(HBasicBlock* block) OVERRIDE;
 
@@ -65,6 +68,14 @@
   SSAChecker(ArenaAllocator* allocator, HGraph* graph)
     : GraphChecker(allocator, graph) {}
 
+  // Check the whole graph (in reverse post-order).
+  virtual void Run() {
+    // VisitReversePostOrder is used instead of VisitInsertionOrder,
+    // as the latter might visit dead blocks removed by the dominator
+    // computation.
+    VisitReversePostOrder();
+  }
+
   // Perform SSA form checks on `block`.
   virtual void VisitBasicBlock(HBasicBlock* block) OVERRIDE;
   // Loop-related checks from block `loop_header`.
diff --git a/compiler/optimizing/graph_checker_test.cc b/compiler/optimizing/graph_checker_test.cc
index ea06920..39def82 100644
--- a/compiler/optimizing/graph_checker_test.cc
+++ b/compiler/optimizing/graph_checker_test.cc
@@ -51,7 +51,7 @@
   ASSERT_NE(graph, nullptr);
 
   GraphChecker graph_checker(&allocator, graph);
-  graph_checker.VisitInsertionOrder();
+  graph_checker.Run();
   ASSERT_TRUE(graph_checker.IsValid());
 }
 
@@ -65,7 +65,7 @@
   graph->TransformToSSA();
 
   SSAChecker ssa_checker(&allocator, graph);
-  ssa_checker.VisitInsertionOrder();
+  ssa_checker.Run();
   ASSERT_TRUE(ssa_checker.IsValid());
 }
 
@@ -113,13 +113,13 @@
 
   HGraph* graph = CreateSimpleCFG(&allocator);
   GraphChecker graph_checker(&allocator, graph);
-  graph_checker.VisitInsertionOrder();
+  graph_checker.Run();
   ASSERT_TRUE(graph_checker.IsValid());
 
   // Remove the entry block from the exit block's predecessors, to create an
   // inconsistent successor/predecessor relation.
   graph->GetExitBlock()->RemovePredecessor(graph->GetEntryBlock());
-  graph_checker.VisitInsertionOrder();
+  graph_checker.Run();
   ASSERT_FALSE(graph_checker.IsValid());
 }
 
@@ -131,7 +131,7 @@
 
   HGraph* graph = CreateSimpleCFG(&allocator);
   GraphChecker graph_checker(&allocator, graph);
-  graph_checker.VisitInsertionOrder();
+  graph_checker.Run();
   ASSERT_TRUE(graph_checker.IsValid());
 
   // Remove the sole instruction of the exit block (composed of a
@@ -141,7 +141,7 @@
   HInstruction* last_inst = exit_block->GetLastInstruction();
   exit_block->RemoveInstruction(last_inst);
 
-  graph_checker.VisitInsertionOrder();
+  graph_checker.Run();
   ASSERT_FALSE(graph_checker.IsValid());
 }
 
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index a058dea..aee2177 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -553,6 +553,12 @@
   }
 }
 
+void HGraphVisitor::VisitReversePostOrder() {
+  for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
+    VisitBasicBlock(it.Current());
+  }
+}
+
 void HGraphVisitor::VisitBasicBlock(HBasicBlock* block) {
   for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
     it.Current()->Accept(this);
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 677a4f8..e60a7e6 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -650,6 +650,7 @@
 
   virtual bool NeedsEnvironment() const { return false; }
   virtual bool IsControlFlow() const { return false; }
+  virtual bool CanThrow() const { return false; }
   bool HasSideEffects() const { return side_effects_.HasSideEffects(); }
 
   void AddUseAt(HInstruction* user, size_t index) {
@@ -1642,6 +1643,8 @@
 
   virtual bool NeedsEnvironment() const { return true; }
 
+  virtual bool CanThrow() const { return true; }
+
   uint32_t GetDexPc() const { return dex_pc_; }
 
   DECLARE_INSTRUCTION(NullCheck);
@@ -1802,6 +1805,8 @@
 
   virtual bool NeedsEnvironment() const { return true; }
 
+  virtual bool CanThrow() const { return true; }
+
   uint32_t GetDexPc() const { return dex_pc_; }
 
   DECLARE_INSTRUCTION(BoundsCheck);
@@ -1956,8 +1961,12 @@
   virtual void VisitInstruction(HInstruction* instruction) {}
   virtual void VisitBasicBlock(HBasicBlock* block);
 
+  // Visit the graph following basic block insertion order.
   void VisitInsertionOrder();
 
+  // Visit the graph following dominator tree reverse post-order.
+  void VisitReversePostOrder();
+
   HGraph* GetGraph() const { return graph_; }
 
   // Visit functions for instruction classes.
diff --git a/oatdump/oatdump.cc b/oatdump/oatdump.cc
index 2e64198..14accac 100644
--- a/oatdump/oatdump.cc
+++ b/oatdump/oatdump.cc
@@ -2230,6 +2230,8 @@
     runtime.reset(StartRuntime(args.boot_image_location_,
                                args.image_location_,
                                args.instruction_set_));
+  } else {
+    MemMap::Init();
   }
 
   if (args.oat_filename_ != nullptr) {
diff --git a/runtime/fault_handler.cc b/runtime/fault_handler.cc
index fede2f8..62e0609 100644
--- a/runtime/fault_handler.cc
+++ b/runtime/fault_handler.cc
@@ -95,16 +95,29 @@
 FaultManager::~FaultManager() {
 }
 
+static void SetUpArtAction(struct sigaction* action) {
+  action->sa_sigaction = art_fault_handler;
+  sigemptyset(&action->sa_mask);
+  action->sa_flags = SA_SIGINFO | SA_ONSTACK;
+#if !defined(__APPLE__) && !defined(__mips__)
+  action->sa_restorer = nullptr;
+#endif
+}
+
+void FaultManager::EnsureArtActionInFrontOfSignalChain() {
+  if (initialized_) {
+    struct sigaction action;
+    SetUpArtAction(&action);
+    EnsureFrontOfChain(SIGSEGV, &action);
+  } else {
+    LOG(WARNING) << "Can't call " << __FUNCTION__ << " due to unitialized fault manager";
+  }
+}
 
 void FaultManager::Init() {
   CHECK(!initialized_);
   struct sigaction action;
-  action.sa_sigaction = art_fault_handler;
-  sigemptyset(&action.sa_mask);
-  action.sa_flags = SA_SIGINFO | SA_ONSTACK;
-#if !defined(__APPLE__) && !defined(__mips__)
-  action.sa_restorer = nullptr;
-#endif
+  SetUpArtAction(&action);
 
   // Set our signal handler now.
   int e = sigaction(SIGSEGV, &action, &oldaction_);
@@ -138,7 +151,6 @@
   //
   // If malloc calls abort, it will be holding its lock.
   // If the handler tries to call malloc, it will deadlock.
-
   VLOG(signals) << "Handling fault";
   if (IsInGeneratedCode(info, context, true)) {
     VLOG(signals) << "in generated code, looking for handler";
diff --git a/runtime/fault_handler.h b/runtime/fault_handler.h
index 8b66a6f..adac4c2 100644
--- a/runtime/fault_handler.h
+++ b/runtime/fault_handler.h
@@ -45,6 +45,7 @@
 
   // Unclaim signals and delete registered handlers.
   void Shutdown();
+  void EnsureArtActionInFrontOfSignalChain();
 
   void HandleFault(int sig, siginfo_t* info, void* context);
   void HandleNestedSignal(int sig, siginfo_t* info, void* context);
@@ -128,7 +129,6 @@
   DISALLOW_COPY_AND_ASSIGN(JavaStackTraceHandler);
 };
 
-
 // Statically allocated so the the signal handler can Get access to it.
 extern FaultManager fault_manager;
 
diff --git a/runtime/java_vm_ext.cc b/runtime/java_vm_ext.cc
index 1444d97..fed8bf0 100644
--- a/runtime/java_vm_ext.cc
+++ b/runtime/java_vm_ext.cc
@@ -21,6 +21,7 @@
 #include "base/mutex.h"
 #include "base/stl_util.h"
 #include "check_jni.h"
+#include "fault_handler.h"
 #include "indirect_reference_table-inl.h"
 #include "mirror/art_method.h"
 #include "mirror/class-inl.h"
@@ -688,6 +689,10 @@
     JNI_OnLoadFn jni_on_load = reinterpret_cast<JNI_OnLoadFn>(sym);
     int version = (*jni_on_load)(this, nullptr);
 
+    if (runtime_->GetTargetSdkVersion() != 0 && runtime_->GetTargetSdkVersion() <= 21) {
+      fault_manager.EnsureArtActionInFrontOfSignalChain();
+    }
+
     self->SetClassLoaderOverride(old_class_loader.get());
 
     if (version == JNI_ERR) {
diff --git a/runtime/jni_internal.cc b/runtime/jni_internal.cc
index e098e11..70754f2 100644
--- a/runtime/jni_internal.cc
+++ b/runtime/jni_internal.cc
@@ -30,6 +30,7 @@
 #include "base/stl_util.h"
 #include "class_linker-inl.h"
 #include "dex_file-inl.h"
+#include "fault_handler.h"
 #include "gc_root.h"
 #include "gc/accounting/card_table-inl.h"
 #include "indirect_reference_table-inl.h"
diff --git a/runtime/thread_list.cc b/runtime/thread_list.cc
index 35411e2..646830a 100644
--- a/runtime/thread_list.cc
+++ b/runtime/thread_list.cc
@@ -34,6 +34,7 @@
 #include "monitor.h"
 #include "scoped_thread_state_change.h"
 #include "thread.h"
+#include "trace.h"
 #include "utils.h"
 #include "well_known_classes.h"
 
@@ -877,6 +878,9 @@
   // suspend and so on, must happen at this point, and not in ~Thread.
   self->Destroy();
 
+  // If tracing, remember thread id and name before thread exits.
+  Trace::StoreExitingThreadInfo(self);
+
   uint32_t thin_lock_id = self->GetThreadId();
   while (self != nullptr) {
     // Remove and delete the Thread* while holding the thread_list_lock_ and
diff --git a/runtime/trace.cc b/runtime/trace.cc
index 027f62d..91a37fd 100644
--- a/runtime/trace.cc
+++ b/runtime/trace.cc
@@ -706,9 +706,21 @@
 
 void Trace::DumpThreadList(std::ostream& os) {
   Thread* self = Thread::Current();
+  for (auto it : exited_threads_) {
+    os << it.first << "\t" << it.second << "\n";
+  }
   Locks::thread_list_lock_->AssertNotHeld(self);
   MutexLock mu(self, *Locks::thread_list_lock_);
   Runtime::Current()->GetThreadList()->ForEach(DumpThread, &os);
 }
 
+void Trace::StoreExitingThreadInfo(Thread* thread) {
+  MutexLock mu(thread, *Locks::trace_lock_);
+  if (the_trace_ != nullptr) {
+    std::string name;
+    thread->GetThreadName(name);
+    the_trace_->exited_threads_.Put(thread->GetTid(), name);
+  }
+}
+
 }  // namespace art
diff --git a/runtime/trace.h b/runtime/trace.h
index 45a02da..ead1c29 100644
--- a/runtime/trace.h
+++ b/runtime/trace.h
@@ -104,6 +104,8 @@
   static std::vector<mirror::ArtMethod*>* AllocStackTrace();
   // Clear and store an old stack trace for later use.
   static void FreeStackTrace(std::vector<mirror::ArtMethod*>* stack_trace);
+  // Save id and name of a thread before it exits.
+  static void StoreExitingThreadInfo(Thread* thread);
 
  private:
   explicit Trace(File* trace_file, int buffer_size, int flags, bool sampling_enabled);
@@ -166,6 +168,9 @@
   // Did we overflow the buffer recording traces?
   bool overflow_;
 
+  // Map of thread ids and names that have already exited.
+  SafeMap<pid_t, std::string> exited_threads_;
+
   DISALLOW_COPY_AND_ASSIGN(Trace);
 };
 
diff --git a/sigchainlib/sigchain.cc b/sigchainlib/sigchain.cc
index c5015e8..601e321 100644
--- a/sigchainlib/sigchain.cc
+++ b/sigchainlib/sigchain.cc
@@ -35,6 +35,8 @@
 
 namespace art {
 
+typedef int (*SigActionFnPtr)(int, const struct sigaction*, struct sigaction*);
+
 class SignalAction {
  public:
   SignalAction() : claimed_(false), uses_old_style_(false) {
@@ -147,7 +149,20 @@
   }
 }
 
-// These functions are C linkage since they replace the functions in libc.
+extern "C" void EnsureFrontOfChain(int signal, struct sigaction* expected_action) {
+  CheckSignalValid(signal);
+  // Read the current action without looking at the chain, it should be the expected action.
+  SigActionFnPtr linked_sigaction = reinterpret_cast<SigActionFnPtr>(linked_sigaction_sym);
+  struct sigaction current_action;
+  linked_sigaction(signal, nullptr, &current_action);
+  // If the sigactions don't match then we put the current action on the chain and make ourself as
+  // the main action.
+  if (current_action.sa_sigaction != expected_action->sa_sigaction) {
+    log("Warning: Unexpected sigaction action found %p\n", current_action.sa_sigaction);
+    user_sigactions[signal].Claim(current_action);
+    linked_sigaction(signal, expected_action, nullptr);
+  }
+}
 
 extern "C" int sigaction(int signal, const struct sigaction* new_action, struct sigaction* old_action) {
   // If this signal has been claimed as a signal chain, record the user's
@@ -179,9 +194,7 @@
     log("Unable to find next sigaction in signal chain");
     abort();
   }
-
-  typedef int (*SigAction)(int, const struct sigaction*, struct sigaction*);
-  SigAction linked_sigaction = reinterpret_cast<SigAction>(linked_sigaction_sym);
+  SigActionFnPtr linked_sigaction = reinterpret_cast<SigActionFnPtr>(linked_sigaction_sym);
   return linked_sigaction(signal, new_action, old_action);
 }
 
@@ -287,5 +300,6 @@
   }
   initialized = true;
 }
+
 }   // namespace art
 
diff --git a/sigchainlib/sigchain.h b/sigchainlib/sigchain.h
index 0de0d08..79b76a7 100644
--- a/sigchainlib/sigchain.h
+++ b/sigchainlib/sigchain.h
@@ -19,6 +19,8 @@
 
 #include <signal.h>
 
+namespace art {
+
 extern "C" void InitializeSignalChain();
 
 extern "C" void ClaimSignalChain(int signal, struct sigaction* oldaction);
@@ -27,4 +29,8 @@
 
 extern "C" void InvokeUserSignalHandler(int sig, siginfo_t* info, void* context);
 
+extern "C" void EnsureFrontOfChain(int signal, struct sigaction* expected_action);
+
+}  // namespace art
+
 #endif  // ART_SIGCHAINLIB_SIGCHAIN_H_
diff --git a/sigchainlib/sigchain_dummy.cc b/sigchainlib/sigchain_dummy.cc
index 7176f05..fbc8c3f 100644
--- a/sigchainlib/sigchain_dummy.cc
+++ b/sigchainlib/sigchain_dummy.cc
@@ -57,3 +57,8 @@
   log("InitializeSignalChain is not exported by the main executable.");
   abort();
 }
+
+extern "C" void EnsureFrontOfChain(int signal, struct sigaction* expected_action) {
+  log("EnsureFrontOfChain is not exported by the main executable.");
+  abort();
+}
diff --git a/sigchainlib/version-script.txt b/sigchainlib/version-script.txt
index 8030da4..ce15054 100644
--- a/sigchainlib/version-script.txt
+++ b/sigchainlib/version-script.txt
@@ -4,6 +4,7 @@
   UnclaimSignalChain;
   InvokeUserSignalHandler;
   InitializeSignalChain;
+  EnsureFrontOfChain;
   sigaction;
   signal;
   sigprocmask;
diff --git a/test/036-finalizer/src/Main.java b/test/036-finalizer/src/Main.java
index 4ebbdc5..e3cf4ee 100644
--- a/test/036-finalizer/src/Main.java
+++ b/test/036-finalizer/src/Main.java
@@ -125,18 +125,28 @@
     }
 
     static class FinalizeCounter {
+      public static final int maxCount = 1024;
+      public static boolean finalized[] = new boolean[maxCount];
       private static Object finalizeLock = new Object();
       private static volatile int finalizeCount = 0;
       private int index;
       static int getCount() {
         return finalizeCount;
       }
+      static void printNonFinalized() {
+        for (int i = 0; i < maxCount; ++i) {
+          if (!FinalizeCounter.finalized[i]) {
+            System.err.println("Element " + i + " was not finalized");
+          }
+        }
+      }
       FinalizeCounter(int index) {
         this.index = index;
       }
       protected void finalize() {
         synchronized(finalizeLock) {
           ++finalizeCount;
+          finalized[index] = true;
         }
       }
     }
@@ -149,11 +159,21 @@
     }
 
     private static void runFinalizationTest() {
-      int count = 1024;
-      allocFinalizableObjects(count);
+      allocFinalizableObjects(FinalizeCounter.maxCount);
       Runtime.getRuntime().gc();
       System.runFinalization();
-      System.out.println("Finalized " + FinalizeCounter.getCount() + " / "  + count);
+      System.out.println("Finalized " + FinalizeCounter.getCount() + " / "  + FinalizeCounter.maxCount);
+      if (FinalizeCounter.getCount() != FinalizeCounter.maxCount) {
+        // Print out all the finalized elements.
+        FinalizeCounter.printNonFinalized();
+        // Try to sleep for a couple seconds to see if the objects became finalized after.
+        try {
+          java.lang.Thread.sleep(2000);
+        } catch (InterruptedException e) {
+        }
+        System.out.println("After sleep finalized " + FinalizeCounter.getCount() + " / "  + FinalizeCounter.maxCount);
+        FinalizeCounter.printNonFinalized();
+      }
     }
 
     public static class FinalizerTest {
diff --git a/test/074-gc-thrash/src/Main.java b/test/074-gc-thrash/src/Main.java
index 6ee7dce..32fbf2d 100644
--- a/test/074-gc-thrash/src/Main.java
+++ b/test/074-gc-thrash/src/Main.java
@@ -255,54 +255,55 @@
      * valid and invalid references on the stack.
      */
     private String dive(int depth, int iteration) {
-        String str0;
-        String str1;
-        String str2;
-        String str3;
-        String str4;
-        String str5;
-        String str6;
-        String str7;
-        String funStr;
+        try {
+            String str0;
+            String str1;
+            String str2;
+            String str3;
+            String str4;
+            String str5;
+            String str6;
+            String str7;
+            String funStr = "";
+            switch (iteration % 8) {
+                case 0:
+                    funStr = str0 = makeString(iteration);
+                    break;
+                case 1:
+                    funStr = str1 = makeString(iteration);
+                    break;
+                case 2:
+                    funStr = str2 = makeString(iteration);
+                    break;
+                case 3:
+                    funStr = str3 = makeString(iteration);
+                    break;
+                case 4:
+                    funStr = str4 = makeString(iteration);
+                    break;
+                case 5:
+                    funStr = str5 = makeString(iteration);
+                    break;
+                case 6:
+                    funStr = str6 = makeString(iteration);
+                    break;
+                case 7:
+                    funStr = str7 = makeString(iteration);
+                    break;
+            }
 
-        funStr = "";
-
-        switch (iteration % 8) {
-            case 0:
-                funStr = str0 = makeString(iteration);
-                break;
-            case 1:
-                funStr = str1 = makeString(iteration);
-                break;
-            case 2:
-                funStr = str2 = makeString(iteration);
-                break;
-            case 3:
-                funStr = str3 = makeString(iteration);
-                break;
-            case 4:
-                funStr = str4 = makeString(iteration);
-                break;
-            case 5:
-                funStr = str5 = makeString(iteration);
-                break;
-            case 6:
-                funStr = str6 = makeString(iteration);
-                break;
-            case 7:
-                funStr = str7 = makeString(iteration);
-                break;
+            strong[depth] = funStr;
+            weak[depth] = new WeakReference(funStr);
+            if (depth+1 < MAX_DEPTH)
+                dive(depth+1, iteration+1);
+            else
+                Main.sleep(100);
+            return funStr;
+        } catch (OutOfMemoryError e) {
+            // Silently ignore OOME since gc stress mode causes them to occur but shouldn't be a
+            // test failure.
         }
-
-        strong[depth] = funStr;
-        weak[depth] = new WeakReference(funStr);
-
-        if (depth+1 < MAX_DEPTH)
-            dive(depth+1, iteration+1);
-        else
-            Main.sleep(100);
-
-        return funStr;
+        return "";
     }
 
     private String makeString(int val) {