Dead code elimination based on GVN results.

Change-Id: I5b77411a8f088f0b561da14b123cf6b0501c9db5

21 files changed, 3693 insertions, 93 deletions

diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index 24d96bab8..5966951a8 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -154,6 +154,7 @@ COMPILER_GTEST_COMMON_SRC_FILES := \
   runtime/jni_internal_test.cc \
   runtime/proxy_test.cc \
   runtime/reflection_test.cc \
+  compiler/dex/gvn_dead_code_elimination_test.cc \
   compiler/dex/global_value_numbering_test.cc \
   compiler/dex/local_value_numbering_test.cc \
   compiler/dex/mir_graph_test.cc \
diff --git a/compiler/Android.mk b/compiler/Android.mk
index 61379fbf1..69b429553 100644
--- a/compiler/Android.mk
+++ b/compiler/Android.mk
@@ -21,6 +21,7 @@ include art/build/Android.common_build.mk
 LIBART_COMPILER_SRC_FILES := \
 	compiled_method.cc \
 	dex/global_value_numbering.cc \
+	dex/gvn_dead_code_elimination.cc \
 	dex/local_value_numbering.cc \
 	dex/quick/arm/assemble_arm.cc \
 	dex/quick/arm/call_arm.cc \
diff --git a/compiler/dex/bb_optimizations.h b/compiler/dex/bb_optimizations.h
index 768520026..93d83c6fd 100644
--- a/compiler/dex/bb_optimizations.h
+++ b/compiler/dex/bb_optimizations.h
@@ -240,6 +240,41 @@ class GlobalValueNumberingPass : public PassME {
 };
 
 /**
+ * @class DeadCodeEliminationPass
+ * @brief Performs the GVN-based dead code elimination pass.
+ */
+class DeadCodeEliminationPass : public PassME {
+ public:
+  DeadCodeEliminationPass() : PassME("DCE", kPreOrderDFSTraversal, "4_post_dce_cfg") {
+  }
+
+  bool Gate(const PassDataHolder* data) const OVERRIDE {
+    DCHECK(data != nullptr);
+    CompilationUnit* c_unit = down_cast<const PassMEDataHolder*>(data)->c_unit;
+    DCHECK(c_unit != nullptr);
+    return c_unit->mir_graph->EliminateDeadCodeGate();
+  }
+
+  bool Worker(PassDataHolder* data) const {
+    DCHECK(data != nullptr);
+    PassMEDataHolder* pass_me_data_holder = down_cast<PassMEDataHolder*>(data);
+    CompilationUnit* c_unit = pass_me_data_holder->c_unit;
+    DCHECK(c_unit != nullptr);
+    BasicBlock* bb = pass_me_data_holder->bb;
+    DCHECK(bb != nullptr);
+    return c_unit->mir_graph->EliminateDeadCode(bb);
+  }
+
+  void End(PassDataHolder* data) const OVERRIDE {
+    DCHECK(data != nullptr);
+    CompilationUnit* c_unit = down_cast<PassMEDataHolder*>(data)->c_unit;
+    DCHECK(c_unit != nullptr);
+    c_unit->mir_graph->EliminateDeadCodeEnd();
+    down_cast<PassMEDataHolder*>(data)->dirty = !c_unit->mir_graph->MirSsaRepUpToDate();
+  }
+};
+
+/**
  * @class BBCombine
  * @brief Perform the basic block combination pass.
  */
diff --git a/compiler/dex/dex_flags.h b/compiler/dex/dex_flags.h
index eaf272bb5..e8eb40ccd 100644
--- a/compiler/dex/dex_flags.h
+++ b/compiler/dex/dex_flags.h
@@ -27,6 +27,7 @@ enum OptControlVector {
   kNullCheckElimination,
   kClassInitCheckElimination,
   kGlobalValueNumbering,
+  kGvnDeadCodeElimination,
   kLocalValueNumbering,
   kPromoteRegs,
   kTrackLiveTemps,
diff --git a/compiler/dex/global_value_numbering.cc b/compiler/dex/global_value_numbering.cc
index a8fd8122f..ab3c94689 100644
--- a/compiler/dex/global_value_numbering.cc
+++ b/compiler/dex/global_value_numbering.cc
@@ -28,7 +28,7 @@ GlobalValueNumbering::GlobalValueNumbering(CompilationUnit* cu, ScopedArenaAlloc
       allocator_(allocator),
       bbs_processed_(0u),
       max_bbs_to_process_(kMaxBbsToProcessMultiplyFactor * mir_graph_->GetNumReachableBlocks()),
-      last_value_(0u),
+      last_value_(kNullValue),
       modifications_allowed_(true),
       mode_(mode),
       global_value_map_(std::less<uint64_t>(), allocator->Adapter()),
@@ -128,7 +128,11 @@ bool GlobalValueNumbering::FinishBasicBlock(BasicBlock* bb) {
   merge_lvns_.clear();
 
   bool change = (lvns_[bb->id] == nullptr) || !lvns_[bb->id]->Equals(*work_lvn_);
-  if (change) {
+  if (mode_ == kModeGvn) {
+    // In GVN mode, keep the latest LVN even if Equals() indicates no change. This is
+    // to keep the correct values of fields that do not contribute to Equals() as long
+    // as they depend only on predecessor LVNs' fields that do contribute to Equals().
+    // Currently, that's LVN::merge_map_ used by LVN::GetStartingVregValueNumberImpl().
     std::unique_ptr<const LocalValueNumbering> old_lvn(lvns_[bb->id]);
     lvns_[bb->id] = work_lvn_.release();
   } else {
@@ -178,7 +182,7 @@ bool GlobalValueNumbering::NullCheckedInAllPredecessors(
       }
       // IF_EQZ/IF_NEZ checks some sreg, see if that sreg contains the value_name.
       int s_reg = pred_bb->last_mir_insn->ssa_rep->uses[0];
-      if (!pred_lvn->IsSregValue(s_reg, value_name)) {
+      if (pred_lvn->GetSregValue(s_reg) != value_name) {
         return false;
       }
     }
diff --git a/compiler/dex/global_value_numbering.h b/compiler/dex/global_value_numbering.h
index 023dbdb58..c7bca85de 100644
--- a/compiler/dex/global_value_numbering.h
+++ b/compiler/dex/global_value_numbering.h
@@ -31,6 +31,9 @@ class MirFieldInfo;
 
 class GlobalValueNumbering : public DeletableArenaObject<kArenaAllocMisc> {
  public:
+  static constexpr uint16_t kNoValue = 0xffffu;
+  static constexpr uint16_t kNullValue = 1u;
+
   enum Mode {
     kModeGvn,
     kModeGvnPostProcessing,
@@ -51,6 +54,14 @@ class GlobalValueNumbering : public DeletableArenaObject<kArenaAllocMisc> {
   GlobalValueNumbering(CompilationUnit* cu, ScopedArenaAllocator* allocator, Mode mode);
   ~GlobalValueNumbering();
 
+  CompilationUnit* GetCompilationUnit() const {
+    return cu_;
+  }
+
+  MIRGraph* GetMirGraph() const {
+    return mir_graph_;
+  }
+
   // Prepare LVN for the basic block.
   LocalValueNumbering* PrepareBasicBlock(BasicBlock* bb,
                                          ScopedArenaAllocator* allocator = nullptr);
@@ -70,9 +81,10 @@ class GlobalValueNumbering : public DeletableArenaObject<kArenaAllocMisc> {
     return modifications_allowed_ && Good();
   }
 
- private:
-  static constexpr uint16_t kNoValue = 0xffffu;
+  // Retrieve the LVN with GVN results for a given BasicBlock.
+  const LocalValueNumbering* GetLvn(BasicBlockId bb_id) const;
 
+ private:
   // Allocate a new value name.
   uint16_t NewValueName();
 
@@ -88,7 +100,7 @@ class GlobalValueNumbering : public DeletableArenaObject<kArenaAllocMisc> {
   uint16_t LookupValue(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier) {
     uint16_t res;
     uint64_t key = BuildKey(op, operand1, operand2, modifier);
-    ValueMap::iterator lb = global_value_map_.lower_bound(key);
+    auto lb = global_value_map_.lower_bound(key);
     if (lb != global_value_map_.end() && lb->first == key) {
       res = lb->second;
     } else {
@@ -99,10 +111,10 @@ class GlobalValueNumbering : public DeletableArenaObject<kArenaAllocMisc> {
   }
 
   // Look up a value in the global value map, don't add a new entry if there was none before.
-  uint16_t FindValue(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier) {
+  uint16_t FindValue(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier) const {
     uint16_t res;
     uint64_t key = BuildKey(op, operand1, operand2, modifier);
-    ValueMap::iterator lb = global_value_map_.lower_bound(key);
+    auto lb = global_value_map_.lower_bound(key);
     if (lb != global_value_map_.end() && lb->first == key) {
       res = lb->second;
     } else {
@@ -111,18 +123,6 @@ class GlobalValueNumbering : public DeletableArenaObject<kArenaAllocMisc> {
     return res;
   }
 
-  // Check if the exact value is stored in the global value map.
-  bool HasValue(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier,
-                uint16_t value) const {
-    DCHECK(value != 0u || !Good());
-    DCHECK_LE(value, last_value_);
-    // This is equivalent to value == LookupValue(op, operand1, operand2, modifier)
-    // except that it doesn't add an entry to the global value map if it's not there.
-    uint64_t key = BuildKey(op, operand1, operand2, modifier);
-    ValueMap::const_iterator it = global_value_map_.find(key);
-    return (it != global_value_map_.end() && it->second == value);
-  }
-
   // Get an instance field id.
   uint16_t GetIFieldId(MIR* mir) {
     return GetMirGraph()->GetGvnIFieldId(mir);
@@ -200,14 +200,6 @@ class GlobalValueNumbering : public DeletableArenaObject<kArenaAllocMisc> {
 
   bool DivZeroCheckedInAllPredecessors(const ScopedArenaVector<uint16_t>& merge_names) const;
 
-  CompilationUnit* GetCompilationUnit() const {
-    return cu_;
-  }
-
-  MIRGraph* GetMirGraph() const {
-    return mir_graph_;
-  }
-
   ScopedArenaAllocator* Allocator() const {
     return allocator_;
   }
@@ -255,6 +247,13 @@ class GlobalValueNumbering : public DeletableArenaObject<kArenaAllocMisc> {
 };
 std::ostream& operator<<(std::ostream& os, const GlobalValueNumbering::Mode& rhs);
 
+inline const LocalValueNumbering* GlobalValueNumbering::GetLvn(BasicBlockId bb_id) const {
+  DCHECK_EQ(mode_, kModeGvnPostProcessing);
+  DCHECK_LT(bb_id, lvns_.size());
+  DCHECK(lvns_[bb_id] != nullptr);
+  return lvns_[bb_id];
+}
+
 inline void GlobalValueNumbering::StartPostProcessing() {
   DCHECK(Good());
   DCHECK_EQ(mode_, kModeGvn);
diff --git a/compiler/dex/global_value_numbering_test.cc b/compiler/dex/global_value_numbering_test.cc
index cfa638890..54e34eaa8 100644
--- a/compiler/dex/global_value_numbering_test.cc
+++ b/compiler/dex/global_value_numbering_test.cc
@@ -134,8 +134,8 @@ class GlobalValueNumberingTest : public testing::Test {
     { bb, opcode, 0u, 0u, 2, { src, src + 1 }, 2, { reg, reg + 1 } }
 #define DEF_PHI2(bb, reg, src1, src2) \
     { bb, static_cast<Instruction::Code>(kMirOpPhi), 0, 0u, 2u, { src1, src2 }, 1, { reg } }
-#define DEF_DIV_REM(bb, opcode, result, dividend, divisor) \
-    { bb, opcode, 0u, 0u, 2, { dividend, divisor }, 1, { result } }
+#define DEF_BINOP(bb, opcode, result, src1, src2) \
+    { bb, opcode, 0u, 0u, 2, { src1, src2 }, 1, { result } }
 
   void DoPrepareIFields(const IFieldDef* defs, size_t count) {
     cu_.mir_graph->ifield_lowering_infos_.clear();
@@ -267,7 +267,6 @@ class GlobalValueNumberingTest : public testing::Test {
       mir->offset = i;  // LVN uses offset only for debug output
       mir->optimization_flags = 0u;
     }
-    mirs_[count - 1u].next = nullptr;
     DexFile::CodeItem* code_item = static_cast<DexFile::CodeItem*>(
         cu_.arena.Alloc(sizeof(DexFile::CodeItem), kArenaAllocMisc));
     code_item->insns_size_in_code_units_ = 2u * count;
@@ -279,6 +278,20 @@ class GlobalValueNumberingTest : public testing::Test {
     DoPrepareMIRs(defs, count);
   }
 
+  void DoPrepareVregToSsaMapExit(BasicBlockId bb_id, const int32_t* map, size_t count) {
+    BasicBlock* bb = cu_.mir_graph->GetBasicBlock(bb_id);
+    ASSERT_TRUE(bb != nullptr);
+    ASSERT_TRUE(bb->data_flow_info != nullptr);
+    bb->data_flow_info->vreg_to_ssa_map_exit =
+        cu_.arena.AllocArray<int32_t>(count, kArenaAllocDFInfo);
+    std::copy_n(map, count, bb->data_flow_info->vreg_to_ssa_map_exit);
+  }
+
+  template <size_t count>
+  void PrepareVregToSsaMapExit(BasicBlockId bb_id, const int32_t (&map)[count]) {
+    DoPrepareVregToSsaMapExit(bb_id, map, count);
+  }
+
   void PerformGVN() {
     DoPerformGVN<LoopRepeatingTopologicalSortIterator>();
   }
@@ -294,9 +307,9 @@ class GlobalValueNumberingTest : public testing::Test {
     cu_.mir_graph->ComputeDominators();
     cu_.mir_graph->ComputeTopologicalSortOrder();
     cu_.mir_graph->SSATransformationEnd();
-    cu_.mir_graph->temp_.gvn.ifield_ids_ =  GlobalValueNumbering::PrepareGvnFieldIds(
+    cu_.mir_graph->temp_.gvn.ifield_ids =  GlobalValueNumbering::PrepareGvnFieldIds(
         allocator_.get(), cu_.mir_graph->ifield_lowering_infos_);
-    cu_.mir_graph->temp_.gvn.sfield_ids_ =  GlobalValueNumbering::PrepareGvnFieldIds(
+    cu_.mir_graph->temp_.gvn.sfield_ids =  GlobalValueNumbering::PrepareGvnFieldIds(
         allocator_.get(), cu_.mir_graph->sfield_lowering_infos_);
     ASSERT_TRUE(gvn_ == nullptr);
     gvn_.reset(new (allocator_.get()) GlobalValueNumbering(&cu_, allocator_.get(),
@@ -348,6 +361,10 @@ class GlobalValueNumberingTest : public testing::Test {
     cu_.mir_graph.reset(new MIRGraph(&cu_, &cu_.arena));
     cu_.access_flags = kAccStatic;  // Don't let "this" interfere with this test.
     allocator_.reset(ScopedArenaAllocator::Create(&cu_.arena_stack));
+    // By default, the zero-initialized reg_location_[.] with ref == false tells LVN that
+    // 0 constants are integral, not references. Nothing else is used by LVN/GVN.
+    cu_.mir_graph->reg_location_ =
+        cu_.arena.AllocArray<RegLocation>(kMaxSsaRegs, kArenaAllocRegAlloc);
     // Bind all possible sregs to live vregs for test purposes.
     live_in_v_->SetInitialBits(kMaxSsaRegs);
     cu_.mir_graph->ssa_base_vregs_.reserve(kMaxSsaRegs);
@@ -1570,6 +1587,40 @@ TEST_F(GlobalValueNumberingTestLoop, Phi) {
   EXPECT_NE(value_names_[4], value_names_[3]);
 }
 
+TEST_F(GlobalValueNumberingTestLoop, IFieldLoopVariable) {
+  static const IFieldDef ifields[] = {
+      { 0u, 1u, 0u, false, kDexMemAccessWord },
+  };
+  static const MIRDef mirs[] = {
+      DEF_CONST(3, Instruction::CONST, 0u, 0),
+      DEF_IPUT(3, Instruction::IPUT, 0u, 100u, 0u),
+      DEF_IGET(4, Instruction::IGET, 2u, 100u, 0u),
+      DEF_BINOP(4, Instruction::ADD_INT, 3u, 2u, 101u),
+      DEF_IPUT(4, Instruction::IPUT, 3u, 100u, 0u),
+  };
+
+  PrepareIFields(ifields);
+  PrepareMIRs(mirs);
+  PerformGVN();
+  ASSERT_EQ(arraysize(mirs), value_names_.size());
+  EXPECT_NE(value_names_[2], value_names_[0]);
+  EXPECT_NE(value_names_[3], value_names_[0]);
+  EXPECT_NE(value_names_[3], value_names_[2]);
+
+
+  // Set up vreg_to_ssa_map_exit for prologue and loop and set post-processing mode
+  // as needed for GetStartingVregValueNumber().
+  const int32_t prologue_vreg_to_ssa_map_exit[] = { 0 };
+  const int32_t loop_vreg_to_ssa_map_exit[] = { 3 };
+  PrepareVregToSsaMapExit(3, prologue_vreg_to_ssa_map_exit);
+  PrepareVregToSsaMapExit(4, loop_vreg_to_ssa_map_exit);
+  gvn_->StartPostProcessing();
+
+  // Check that vreg 0 has the same value number as the result of IGET 2u.
+  const LocalValueNumbering* loop = gvn_->GetLvn(4);
+  EXPECT_EQ(value_names_[2], loop->GetStartingVregValueNumber(0));
+}
+
 TEST_F(GlobalValueNumberingTestCatch, IFields) {
   static const IFieldDef ifields[] = {
       { 0u, 1u, 0u, false, kDexMemAccessWord },
@@ -2225,18 +2276,18 @@ TEST_F(GlobalValueNumberingTest, NormalPathToCatchEntry) {
 
 TEST_F(GlobalValueNumberingTestDiamond, DivZeroCheckDiamond) {
   static const MIRDef mirs[] = {
-      DEF_DIV_REM(3u, Instruction::DIV_INT, 1u, 20u, 21u),
-      DEF_DIV_REM(3u, Instruction::DIV_INT, 2u, 24u, 21u),
-      DEF_DIV_REM(3u, Instruction::DIV_INT, 3u, 20u, 23u),
-      DEF_DIV_REM(4u, Instruction::DIV_INT, 4u, 24u, 22u),
-      DEF_DIV_REM(4u, Instruction::DIV_INT, 9u, 24u, 25u),
-      DEF_DIV_REM(5u, Instruction::DIV_INT, 5u, 24u, 21u),
-      DEF_DIV_REM(5u, Instruction::DIV_INT, 10u, 24u, 26u),
+      DEF_BINOP(3u, Instruction::DIV_INT, 1u, 20u, 21u),
+      DEF_BINOP(3u, Instruction::DIV_INT, 2u, 24u, 21u),
+      DEF_BINOP(3u, Instruction::DIV_INT, 3u, 20u, 23u),
+      DEF_BINOP(4u, Instruction::DIV_INT, 4u, 24u, 22u),
+      DEF_BINOP(4u, Instruction::DIV_INT, 9u, 24u, 25u),
+      DEF_BINOP(5u, Instruction::DIV_INT, 5u, 24u, 21u),
+      DEF_BINOP(5u, Instruction::DIV_INT, 10u, 24u, 26u),
       DEF_PHI2(6u, 27u, 25u, 26u),
-      DEF_DIV_REM(6u, Instruction::DIV_INT, 12u, 20u, 27u),
-      DEF_DIV_REM(6u, Instruction::DIV_INT, 6u, 24u, 21u),
-      DEF_DIV_REM(6u, Instruction::DIV_INT, 7u, 20u, 23u),
-      DEF_DIV_REM(6u, Instruction::DIV_INT, 8u, 20u, 22u),
+      DEF_BINOP(6u, Instruction::DIV_INT, 12u, 20u, 27u),
+      DEF_BINOP(6u, Instruction::DIV_INT, 6u, 24u, 21u),
+      DEF_BINOP(6u, Instruction::DIV_INT, 7u, 20u, 23u),
+      DEF_BINOP(6u, Instruction::DIV_INT, 8u, 20u, 22u),
   };
 
   static const bool expected_ignore_div_zero_check[] = {
diff --git a/compiler/dex/gvn_dead_code_elimination.cc b/compiler/dex/gvn_dead_code_elimination.cc
new file mode 100644
index 000000000..2e7f0328d
--- /dev/null
+++ b/compiler/dex/gvn_dead_code_elimination.cc
@@ -0,0 +1,1391 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <sstream>
+
+#include "gvn_dead_code_elimination.h"
+
+#include "base/bit_vector-inl.h"
+#include "base/macros.h"
+#include "compiler_enums.h"
+#include "dataflow_iterator-inl.h"
+#include "dex_instruction.h"
+#include "dex/mir_graph.h"
+#include "local_value_numbering.h"
+#include "utils/arena_bit_vector.h"
+
+namespace art {
+
+constexpr uint16_t GvnDeadCodeElimination::kNoValue;
+constexpr uint16_t GvnDeadCodeElimination::kNPos;
+
+inline uint16_t GvnDeadCodeElimination::MIRData::PrevChange(int v_reg) const {
+  DCHECK(has_def);
+  DCHECK(v_reg == vreg_def || v_reg == vreg_def + 1);
+  return (v_reg == vreg_def) ? prev_value.change : prev_value_high.change;
+}
+
+inline void GvnDeadCodeElimination::MIRData::SetPrevChange(int v_reg, uint16_t change) {
+  DCHECK(has_def);
+  DCHECK(v_reg == vreg_def || v_reg == vreg_def + 1);
+  if (v_reg == vreg_def) {
+    prev_value.change = change;
+  } else {
+    prev_value_high.change = change;
+  }
+}
+
+inline void GvnDeadCodeElimination::MIRData::RemovePrevChange(int v_reg, MIRData* prev_data) {
+  DCHECK_NE(PrevChange(v_reg), kNPos);
+  DCHECK(v_reg == prev_data->vreg_def || v_reg == prev_data->vreg_def + 1);
+  if (vreg_def == v_reg) {
+    if (prev_data->vreg_def == v_reg) {
+      prev_value = prev_data->prev_value;
+      low_def_over_high_word = prev_data->low_def_over_high_word;
+    } else {
+      prev_value = prev_data->prev_value_high;
+      low_def_over_high_word =
+          prev_data->prev_value_high.value != kNPos && !prev_data->high_def_over_low_word;
+    }
+  } else {
+    if (prev_data->vreg_def == v_reg) {
+      prev_value_high = prev_data->prev_value;
+      high_def_over_low_word =
+          prev_data->prev_value.value != kNPos && !prev_data->low_def_over_high_word;
+    } else {
+      prev_value_high = prev_data->prev_value_high;
+      high_def_over_low_word = prev_data->high_def_over_low_word;
+    }
+  }
+}
+
+GvnDeadCodeElimination::VRegChains::VRegChains(uint32_t num_vregs, ScopedArenaAllocator* alloc)
+    : num_vregs_(num_vregs),
+      vreg_data_(alloc->AllocArray<VRegValue>(num_vregs, kArenaAllocMisc)),
+      mir_data_(alloc->Adapter()) {
+  mir_data_.reserve(100);
+}
+
+inline void GvnDeadCodeElimination::VRegChains::Reset() {
+  DCHECK(mir_data_.empty());
+  std::fill_n(vreg_data_, num_vregs_, VRegValue());
+}
+
+void GvnDeadCodeElimination::VRegChains::AddMIRWithDef(MIR* mir, int v_reg, bool wide,
+                                                       uint16_t new_value) {
+  uint16_t pos = mir_data_.size();
+  mir_data_.emplace_back(mir);
+  MIRData* data = &mir_data_.back();
+  data->has_def = true;
+  data->wide_def = wide;
+  data->vreg_def = v_reg;
+
+  if (vreg_data_[v_reg].change != kNPos &&
+      mir_data_[vreg_data_[v_reg].change].vreg_def + 1 == v_reg) {
+    data->low_def_over_high_word = true;
+  }
+  data->prev_value = vreg_data_[v_reg];
+  DCHECK_LT(static_cast<size_t>(v_reg), num_vregs_);
+  vreg_data_[v_reg].value = new_value;
+  vreg_data_[v_reg].change = pos;
+
+  if (wide) {
+    if (vreg_data_[v_reg + 1].change != kNPos &&
+        mir_data_[vreg_data_[v_reg + 1].change].vreg_def == v_reg + 1) {
+      data->high_def_over_low_word = true;
+    }
+    data->prev_value_high = vreg_data_[v_reg + 1];
+    DCHECK_LT(static_cast<size_t>(v_reg + 1), num_vregs_);
+    vreg_data_[v_reg + 1].value = new_value;
+    vreg_data_[v_reg + 1].change = pos;
+  }
+}
+
+inline void GvnDeadCodeElimination::VRegChains::AddMIRWithoutDef(MIR* mir) {
+  mir_data_.emplace_back(mir);
+}
+
+void GvnDeadCodeElimination::VRegChains::RemoveLastMIRData() {
+  MIRData* data = LastMIRData();
+  if (data->has_def) {
+    DCHECK_EQ(vreg_data_[data->vreg_def].change, NumMIRs() - 1u);
+    vreg_data_[data->vreg_def] = data->prev_value;
+    if (data->wide_def) {
+      DCHECK_EQ(vreg_data_[data->vreg_def + 1].change, NumMIRs() - 1u);
+      vreg_data_[data->vreg_def + 1] = data->prev_value_high;
+    }
+  }
+  mir_data_.pop_back();
+}
+
+void GvnDeadCodeElimination::VRegChains::RemoveTrailingNops() {
+  // There's at least one NOP to drop. There may be more.
+  MIRData* last_data = LastMIRData();
+  DCHECK(!last_data->must_keep && !last_data->has_def);
+  do {
+    DCHECK_EQ(static_cast<int>(last_data->mir->dalvikInsn.opcode), static_cast<int>(kMirOpNop));
+    mir_data_.pop_back();
+    if (mir_data_.empty()) {
+      break;
+    }
+    last_data = LastMIRData();
+  } while (!last_data->must_keep && !last_data->has_def);
+}
+
+inline size_t GvnDeadCodeElimination::VRegChains::NumMIRs() const {
+  return mir_data_.size();
+}
+
+inline GvnDeadCodeElimination::MIRData* GvnDeadCodeElimination::VRegChains::GetMIRData(size_t pos) {
+  DCHECK_LT(pos, mir_data_.size());
+  return &mir_data_[pos];
+}
+
+inline GvnDeadCodeElimination::MIRData* GvnDeadCodeElimination::VRegChains::LastMIRData() {
+  DCHECK(!mir_data_.empty());
+  return &mir_data_.back();
+}
+
+uint32_t GvnDeadCodeElimination::VRegChains::NumVRegs() const {
+  return num_vregs_;
+}
+
+void GvnDeadCodeElimination::VRegChains::InsertInitialValueHigh(int v_reg, uint16_t value) {
+  DCHECK_NE(value, kNoValue);
+  DCHECK_LT(static_cast<size_t>(v_reg), num_vregs_);
+  uint16_t change = vreg_data_[v_reg].change;
+  if (change == kNPos) {
+    vreg_data_[v_reg].value = value;
+  } else {
+    while (true) {
+      MIRData* data = &mir_data_[change];
+      DCHECK(data->vreg_def == v_reg || data->vreg_def + 1 == v_reg);
+      if (data->vreg_def == v_reg) {  // Low word, use prev_value.
+        if (data->prev_value.change == kNPos) {
+          DCHECK_EQ(data->prev_value.value, kNoValue);
+          data->prev_value.value = value;
+          data->low_def_over_high_word = true;
+          break;
+        }
+        change = data->prev_value.change;
+      } else {  // High word, use prev_value_high.
+        if (data->prev_value_high.change == kNPos) {
+          DCHECK_EQ(data->prev_value_high.value, kNoValue);
+          data->prev_value_high.value = value;
+          break;
+        }
+        change = data->prev_value_high.change;
+      }
+    }
+  }
+}
+
+void GvnDeadCodeElimination::VRegChains::UpdateInitialVRegValue(int v_reg, bool wide,
+                                                                const LocalValueNumbering* lvn) {
+  DCHECK_LT(static_cast<size_t>(v_reg), num_vregs_);
+  if (!wide) {
+    if (vreg_data_[v_reg].value == kNoValue) {
+      uint16_t old_value = lvn->GetStartingVregValueNumber(v_reg);
+      if (old_value == kNoValue) {
+        // Maybe there was a wide value in v_reg before. Do not check for wide value in v_reg-1,
+        // that will be done only if we see a definition of v_reg-1, otherwise it's unnecessary.
+        old_value = lvn->GetStartingVregValueNumberWide(v_reg);
+        if (old_value != kNoValue) {
+          InsertInitialValueHigh(v_reg + 1, old_value);
+        }
+      }
+      vreg_data_[v_reg].value = old_value;
+    }
+  } else {
+    DCHECK_LT(static_cast<size_t>(v_reg + 1), num_vregs_);
+    bool check_high = true;
+    if (vreg_data_[v_reg].value == kNoValue) {
+      uint16_t old_value = lvn->GetStartingVregValueNumberWide(v_reg);
+      if (old_value != kNoValue) {
+        InsertInitialValueHigh(v_reg + 1, old_value);
+        check_high = false;  // High word has been processed.
+      } else {
+        // Maybe there was a narrow value before. Do not check for wide value in v_reg-1,
+        // that will be done only if we see a definition of v_reg-1, otherwise it's unnecessary.
+        old_value = lvn->GetStartingVregValueNumber(v_reg);
+      }
+      vreg_data_[v_reg].value = old_value;
+    }
+    if (check_high && vreg_data_[v_reg + 1].value == kNoValue) {
+      uint16_t old_value = lvn->GetStartingVregValueNumber(v_reg + 1);
+      if (old_value == kNoValue && static_cast<size_t>(v_reg + 2) < num_vregs_) {
+        // Maybe there was a wide value before.
+        old_value = lvn->GetStartingVregValueNumberWide(v_reg + 1);
+        if (old_value != kNoValue) {
+          InsertInitialValueHigh(v_reg + 2, old_value);
+        }
+      }
+      vreg_data_[v_reg + 1].value = old_value;
+    }
+  }
+}
+
+inline uint16_t GvnDeadCodeElimination::VRegChains::LastChange(int v_reg) {
+  DCHECK_LT(static_cast<size_t>(v_reg), num_vregs_);
+  return vreg_data_[v_reg].change;
+}
+
+inline uint16_t GvnDeadCodeElimination::VRegChains::CurrentValue(int v_reg) {
+  DCHECK_LT(static_cast<size_t>(v_reg), num_vregs_);
+  return vreg_data_[v_reg].value;
+}
+
+uint16_t GvnDeadCodeElimination::VRegChains::FindKillHead(int v_reg, uint16_t cutoff) {
+  uint16_t current_value = this->CurrentValue(v_reg);
+  DCHECK_NE(current_value, kNoValue);
+  uint16_t change = LastChange(v_reg);
+  DCHECK_LT(change, mir_data_.size());
+  DCHECK_GE(change, cutoff);
+  bool match_high_word = (mir_data_[change].vreg_def != v_reg);
+  do {
+    MIRData* data = &mir_data_[change];
+    DCHECK(data->vreg_def == v_reg || data->vreg_def + 1 == v_reg);
+    if (data->vreg_def == v_reg) {  // Low word, use prev_value.
+      if (data->prev_value.value == current_value &&
+          match_high_word == data->low_def_over_high_word) {
+        break;
+      }
+      change = data->prev_value.change;
+    } else {  // High word, use prev_value_high.
+      if (data->prev_value_high.value == current_value &&
+          match_high_word != data->high_def_over_low_word) {
+        break;
+      }
+      change = data->prev_value_high.change;
+    }
+    if (change < cutoff) {
+      change = kNPos;
+    }
+  } while (change != kNPos);
+  return change;
+}
+
+uint16_t GvnDeadCodeElimination::VRegChains::FindFirstChangeAfter(int v_reg,
+                                                                  uint16_t change) const {
+  DCHECK_LT(static_cast<size_t>(v_reg), num_vregs_);
+  DCHECK_LT(change, mir_data_.size());
+  uint16_t result = kNPos;
+  uint16_t search_change = vreg_data_[v_reg].change;
+  while (search_change != kNPos && search_change > change) {
+    result = search_change;
+    search_change = mir_data_[search_change].PrevChange(v_reg);
+  }
+  return result;
+}
+
+void GvnDeadCodeElimination::VRegChains::ReplaceChange(uint16_t old_change, uint16_t new_change) {
+  const MIRData* old_data = GetMIRData(old_change);
+  DCHECK(old_data->has_def);
+  int count = old_data->wide_def ? 2 : 1;
+  for (int v_reg = old_data->vreg_def, end = old_data->vreg_def + count; v_reg != end; ++v_reg) {
+    uint16_t next_change = FindFirstChangeAfter(v_reg, old_change);
+    if (next_change == kNPos) {
+      DCHECK_EQ(vreg_data_[v_reg].change, old_change);
+      vreg_data_[v_reg].change = new_change;
+    } else {
+      DCHECK_EQ(mir_data_[next_change].PrevChange(v_reg), old_change);
+      mir_data_[next_change].SetPrevChange(v_reg, new_change);
+    }
+  }
+}
+
+void GvnDeadCodeElimination::VRegChains::RemoveChange(uint16_t change) {
+  MIRData* data = &mir_data_[change];
+  DCHECK(data->has_def);
+  int count = data->wide_def ? 2 : 1;
+  for (int v_reg = data->vreg_def, end = data->vreg_def + count; v_reg != end; ++v_reg) {
+    uint16_t next_change = FindFirstChangeAfter(v_reg, change);
+    if (next_change == kNPos) {
+      DCHECK_EQ(vreg_data_[v_reg].change, change);
+      vreg_data_[v_reg] = (data->vreg_def == v_reg) ? data->prev_value : data->prev_value_high;
+    } else {
+      DCHECK_EQ(mir_data_[next_change].PrevChange(v_reg), change);
+      mir_data_[next_change].RemovePrevChange(v_reg, data);
+    }
+  }
+}
+
+inline bool GvnDeadCodeElimination::VRegChains::IsTopChange(uint16_t change) const {
+  DCHECK_LT(change, mir_data_.size());
+  const MIRData* data = &mir_data_[change];
+  DCHECK(data->has_def);
+  DCHECK_LT(data->wide_def ? data->vreg_def + 1u : data->vreg_def, num_vregs_);
+  return vreg_data_[data->vreg_def].change == change &&
+      (!data->wide_def || vreg_data_[data->vreg_def + 1u].change == change);
+}
+
+bool GvnDeadCodeElimination::VRegChains::IsSRegUsed(uint16_t first_change, uint16_t last_change,
+                                                    int s_reg) const {
+  DCHECK_LE(first_change, last_change);
+  DCHECK_LE(last_change, mir_data_.size());
+  for (size_t c = first_change; c != last_change; ++c) {
+    SSARepresentation* ssa_rep = mir_data_[c].mir->ssa_rep;
+    for (int i = 0; i != ssa_rep->num_uses; ++i) {
+      if (ssa_rep->uses[i] == s_reg) {
+        return true;
+      }
+    }
+  }
+  return false;
+}
+
+void GvnDeadCodeElimination::VRegChains::RenameSRegUses(uint16_t first_change, uint16_t last_change,
+                                                        int old_s_reg, int new_s_reg, bool wide) {
+  for (size_t c = first_change; c != last_change; ++c) {
+    SSARepresentation* ssa_rep = mir_data_[c].mir->ssa_rep;
+    for (int i = 0; i != ssa_rep->num_uses; ++i) {
+      if (ssa_rep->uses[i] == old_s_reg) {
+        ssa_rep->uses[i] = new_s_reg;
+        if (wide) {
+          ++i;
+          DCHECK_LT(i, ssa_rep->num_uses);
+          ssa_rep->uses[i] = new_s_reg + 1;
+        }
+      }
+    }
+  }
+}
+
+void GvnDeadCodeElimination::VRegChains::RenameVRegUses(uint16_t first_change, uint16_t last_change,
+                                                    int old_s_reg, int old_v_reg,
+                                                    int new_s_reg, int new_v_reg) {
+  for (size_t c = first_change; c != last_change; ++c) {
+    MIR* mir = mir_data_[c].mir;
+    if (IsInstructionBinOp2Addr(mir->dalvikInsn.opcode) &&
+        mir->ssa_rep->uses[0] == old_s_reg && old_v_reg != new_v_reg) {
+      // Rewrite binop_2ADDR with plain binop before doing the register rename.
+      ChangeBinOp2AddrToPlainBinOp(mir);
+    }
+    uint64_t df_attr = MIRGraph::GetDataFlowAttributes(mir);
+    size_t use = 0u;
+#define REPLACE_VREG(REG) \
+    if ((df_attr & DF_U##REG) != 0) {                                         \
+      if (mir->ssa_rep->uses[use] == old_s_reg) {                             \
+        DCHECK_EQ(mir->dalvikInsn.v##REG, static_cast<uint32_t>(old_v_reg));  \
+        mir->dalvikInsn.v##REG = new_v_reg;                                   \
+        mir->ssa_rep->uses[use] = new_s_reg;                                  \
+        if ((df_attr & DF_##REG##_WIDE) != 0) {                               \
+          DCHECK_EQ(mir->ssa_rep->uses[use + 1], old_s_reg + 1);              \
+          mir->ssa_rep->uses[use + 1] = new_s_reg + 1;                        \
+        }                                                                     \
+      }                                                                       \
+      use += ((df_attr & DF_##REG##_WIDE) != 0) ? 2 : 1;                      \
+    }
+    REPLACE_VREG(A)
+    REPLACE_VREG(B)
+    REPLACE_VREG(C)
+#undef REPLACE_VREG
+    // We may encounter an out-of-order Phi which we need to ignore, otherwise we should
+    // only be asked to rename registers specified by DF_UA, DF_UB and DF_UC.
+    DCHECK_EQ(use,
+              static_cast<int>(mir->dalvikInsn.opcode) == kMirOpPhi
+              ? 0u
+              : static_cast<size_t>(mir->ssa_rep->num_uses));
+  }
+}
+
+GvnDeadCodeElimination::GvnDeadCodeElimination(const GlobalValueNumbering* gvn,
+                                         ScopedArenaAllocator* alloc)
+    : gvn_(gvn),
+      mir_graph_(gvn_->GetMirGraph()),
+      vreg_chains_(mir_graph_->GetNumOfCodeAndTempVRs(), alloc),
+      bb_(nullptr),
+      lvn_(nullptr),
+      no_uses_all_since_(0u),
+      unused_vregs_(new (alloc) ArenaBitVector(alloc, vreg_chains_.NumVRegs(), false)),
+      vregs_to_kill_(new (alloc) ArenaBitVector(alloc, vreg_chains_.NumVRegs(), false)),
+      kill_heads_(alloc->AllocArray<uint16_t>(vreg_chains_.NumVRegs(), kArenaAllocMisc)),
+      changes_to_kill_(alloc->Adapter()),
+      dependent_vregs_(new (alloc) ArenaBitVector(alloc, vreg_chains_.NumVRegs(), false)) {
+  changes_to_kill_.reserve(16u);
+}
+
+void GvnDeadCodeElimination::Apply(BasicBlock* bb) {
+  bb_ = bb;
+  lvn_ = gvn_->GetLvn(bb->id);
+
+  RecordPass();
+  BackwardPass();
+
+  DCHECK_EQ(no_uses_all_since_, 0u);
+  lvn_ = nullptr;
+  bb_ = nullptr;
+}
+
+void GvnDeadCodeElimination::RecordPass() {
+  // Record MIRs with vreg definition data, eliminate single instructions.
+  vreg_chains_.Reset();
+  DCHECK_EQ(no_uses_all_since_, 0u);
+  for (MIR* mir = bb_->first_mir_insn; mir != nullptr; mir = mir->next) {
+    if (RecordMIR(mir)) {
+      RecordPassTryToKillOverwrittenMoveOrMoveSrc();
+      RecordPassTryToKillLastMIR();
+    }
+  }
+}
+
+void GvnDeadCodeElimination::BackwardPass() {
+  // Now process MIRs in reverse order, trying to eliminate them.
+  unused_vregs_->ClearAllBits();  // Implicitly depend on all vregs at the end of BB.
+  while (vreg_chains_.NumMIRs() != 0u) {
+    if (BackwardPassTryToKillLastMIR()) {
+      continue;
+    }
+    BackwardPassProcessLastMIR();
+  }
+}
+
+void GvnDeadCodeElimination::KillMIR(MIRData* data) {
+  DCHECK(!data->must_keep);
+  DCHECK(!data->uses_all_vregs);
+  DCHECK(data->has_def);
+  DCHECK(data->mir->ssa_rep->num_defs == 1 || data->mir->ssa_rep->num_defs == 2);
+
+  KillMIR(data->mir);
+  data->has_def = false;
+  data->is_move = false;
+  data->is_move_src = false;
+}
+
+void GvnDeadCodeElimination::KillMIR(MIR* mir) {
+  mir->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpNop);
+  mir->ssa_rep->num_uses = 0;
+  mir->ssa_rep->num_defs = 0;
+}
+
+void GvnDeadCodeElimination::ChangeBinOp2AddrToPlainBinOp(MIR* mir) {
+  mir->dalvikInsn.vC = mir->dalvikInsn.vB;
+  mir->dalvikInsn.vB = mir->dalvikInsn.vA;
+  mir->dalvikInsn.opcode = static_cast<Instruction::Code>(
+      mir->dalvikInsn.opcode - Instruction::ADD_INT_2ADDR +  Instruction::ADD_INT);
+}
+
+MIR* GvnDeadCodeElimination::CreatePhi(int s_reg, bool fp) {
+  int v_reg = mir_graph_->SRegToVReg(s_reg);
+  MIR* phi = mir_graph_->NewMIR();
+  phi->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpPhi);
+  phi->dalvikInsn.vA = v_reg;
+  phi->offset = bb_->start_offset;
+  phi->m_unit_index = 0;  // Arbitrarily assign all Phi nodes to outermost method.
+
+  phi->ssa_rep = static_cast<struct SSARepresentation *>(mir_graph_->GetArena()->Alloc(
+      sizeof(SSARepresentation), kArenaAllocDFInfo));
+
+  mir_graph_->AllocateSSADefData(phi, 1);
+  phi->ssa_rep->defs[0] = s_reg;
+  phi->ssa_rep->fp_def[0] = fp;
+
+  size_t num_uses = bb_->predecessors.size();
+  mir_graph_->AllocateSSAUseData(phi, num_uses);
+  std::fill_n(phi->ssa_rep->fp_use, num_uses, fp);
+  size_t idx = 0u;
+  for (BasicBlockId pred_id : bb_->predecessors) {
+    BasicBlock* pred_bb = mir_graph_->GetBasicBlock(pred_id);
+    DCHECK(pred_bb != nullptr);
+    phi->ssa_rep->uses[idx] = pred_bb->data_flow_info->vreg_to_ssa_map_exit[v_reg];
+    DCHECK_NE(phi->ssa_rep->uses[idx], INVALID_SREG);
+    idx++;
+  }
+
+  phi->meta.phi_incoming = static_cast<BasicBlockId*>(mir_graph_->GetArena()->Alloc(
+      sizeof(BasicBlockId) * num_uses, kArenaAllocDFInfo));
+  std::copy(bb_->predecessors.begin(), bb_->predecessors.end(), phi->meta.phi_incoming);
+  bb_->PrependMIR(phi);
+  return phi;
+}
+
+MIR* GvnDeadCodeElimination::RenameSRegDefOrCreatePhi(uint16_t def_change, uint16_t last_change,
+                                                      MIR* mir_to_kill) {
+  DCHECK(mir_to_kill->ssa_rep->num_defs == 1 || mir_to_kill->ssa_rep->num_defs == 2);
+  bool wide = (mir_to_kill->ssa_rep->num_defs != 1);
+  int new_s_reg = mir_to_kill->ssa_rep->defs[0];
+
+  // Just before we kill mir_to_kill, we need to replace the previous SSA reg assigned to the
+  // same dalvik reg to keep consistency with subsequent instructions. However, if there's no
+  // defining MIR for that dalvik reg, the preserved valus must come from its predecessors
+  // and we need to create a new Phi (a degenerate Phi if there's only a single predecessor).
+  if (def_change == kNPos) {
+    bool fp = mir_to_kill->ssa_rep->fp_def[0];
+    if (wide) {
+      DCHECK_EQ(new_s_reg + 1, mir_to_kill->ssa_rep->defs[1]);
+      DCHECK_EQ(fp, mir_to_kill->ssa_rep->fp_def[1]);
+      DCHECK_EQ(mir_graph_->SRegToVReg(new_s_reg) + 1, mir_graph_->SRegToVReg(new_s_reg + 1));
+      CreatePhi(new_s_reg + 1, fp);  // High word Phi.
+    }
+    return CreatePhi(new_s_reg, fp);
+  } else {
+    DCHECK_LT(def_change, last_change);
+    DCHECK_LE(last_change, vreg_chains_.NumMIRs());
+    MIRData* def_data = vreg_chains_.GetMIRData(def_change);
+    DCHECK(def_data->has_def);
+    int old_s_reg = def_data->mir->ssa_rep->defs[0];
+    DCHECK_NE(old_s_reg, new_s_reg);
+    DCHECK_EQ(mir_graph_->SRegToVReg(old_s_reg), mir_graph_->SRegToVReg(new_s_reg));
+    def_data->mir->ssa_rep->defs[0] = new_s_reg;
+    if (wide) {
+      if (static_cast<int>(def_data->mir->dalvikInsn.opcode) == kMirOpPhi) {
+        // Currently the high word Phi is always located after the low word Phi.
+        MIR* phi_high = def_data->mir->next;
+        DCHECK(phi_high != nullptr && static_cast<int>(phi_high->dalvikInsn.opcode) == kMirOpPhi);
+        DCHECK_EQ(phi_high->ssa_rep->defs[0], old_s_reg + 1);
+        phi_high->ssa_rep->defs[0] = new_s_reg + 1;
+      } else {
+        DCHECK_EQ(def_data->mir->ssa_rep->defs[1], old_s_reg + 1);
+        def_data->mir->ssa_rep->defs[1] = new_s_reg + 1;
+      }
+    }
+    vreg_chains_.RenameSRegUses(def_change + 1u, last_change, old_s_reg, new_s_reg, wide);
+    return nullptr;
+  }
+}
+
+
+void GvnDeadCodeElimination::BackwardPassProcessLastMIR() {
+  MIRData* data = vreg_chains_.LastMIRData();
+  if (data->uses_all_vregs) {
+    DCHECK(data->must_keep);
+    unused_vregs_->ClearAllBits();
+    DCHECK_EQ(no_uses_all_since_, vreg_chains_.NumMIRs());
+    --no_uses_all_since_;
+    while (no_uses_all_since_ != 0u &&
+        !vreg_chains_.GetMIRData(no_uses_all_since_ - 1u)->uses_all_vregs) {
+      --no_uses_all_since_;
+    }
+  } else {
+    if (data->has_def) {
+      unused_vregs_->SetBit(data->vreg_def);
+      if (data->wide_def) {
+        unused_vregs_->SetBit(data->vreg_def + 1);
+      }
+    }
+    for (int i = 0, num_uses = data->mir->ssa_rep->num_uses; i != num_uses; ++i) {
+      int v_reg = mir_graph_->SRegToVReg(data->mir->ssa_rep->uses[i]);
+      unused_vregs_->ClearBit(v_reg);
+    }
+  }
+  vreg_chains_.RemoveLastMIRData();
+}
+
+void GvnDeadCodeElimination::RecordPassKillMoveByRenamingSrcDef(uint16_t src_change,
+                                                                uint16_t move_change) {
+  DCHECK_LT(src_change, move_change);
+  MIRData* src_data = vreg_chains_.GetMIRData(src_change);
+  MIRData* move_data = vreg_chains_.GetMIRData(move_change);
+  DCHECK(src_data->is_move_src);
+  DCHECK_EQ(src_data->wide_def, move_data->wide_def);
+  DCHECK(move_data->prev_value.change == kNPos || move_data->prev_value.change <= src_change);
+  DCHECK(!move_data->wide_def || move_data->prev_value_high.change == kNPos ||
+         move_data->prev_value_high.change <= src_change);
+
+  int old_s_reg = src_data->mir->ssa_rep->defs[0];
+  // NOTE: old_s_reg may differ from move_data->mir->ssa_rep->uses[0]; value names must match.
+  int new_s_reg = move_data->mir->ssa_rep->defs[0];
+  DCHECK_NE(old_s_reg, new_s_reg);
+
+  if (IsInstructionBinOp2Addr(src_data->mir->dalvikInsn.opcode) &&
+      src_data->vreg_def != move_data->vreg_def) {
+    // Rewrite binop_2ADDR with plain binop before doing the register rename.
+    ChangeBinOp2AddrToPlainBinOp(src_data->mir);
+  }
+  // Remove src_change from the vreg chain(s).
+  vreg_chains_.RemoveChange(src_change);
+  // Replace the move_change with the src_change, copying all necessary data.
+  src_data->is_move_src = move_data->is_move_src;
+  src_data->low_def_over_high_word = move_data->low_def_over_high_word;
+  src_data->high_def_over_low_word = move_data->high_def_over_low_word;
+  src_data->vreg_def = move_data->vreg_def;
+  src_data->prev_value = move_data->prev_value;
+  src_data->prev_value_high = move_data->prev_value_high;
+  src_data->mir->dalvikInsn.vA = move_data->vreg_def;
+  src_data->mir->ssa_rep->defs[0] = new_s_reg;
+  if (move_data->wide_def) {
+    DCHECK_EQ(src_data->mir->ssa_rep->defs[1], old_s_reg + 1);
+    src_data->mir->ssa_rep->defs[1] = new_s_reg + 1;
+  }
+  vreg_chains_.ReplaceChange(move_change, src_change);
+
+  // Rename uses and kill the move.
+  vreg_chains_.RenameVRegUses(src_change + 1u, vreg_chains_.NumMIRs(),
+                              old_s_reg, mir_graph_->SRegToVReg(old_s_reg),
+                              new_s_reg, mir_graph_->SRegToVReg(new_s_reg));
+  KillMIR(move_data);
+}
+
+void GvnDeadCodeElimination::RecordPassTryToKillOverwrittenMoveOrMoveSrc(uint16_t check_change) {
+  MIRData* data = vreg_chains_.GetMIRData(check_change);
+  DCHECK(data->is_move || data->is_move_src);
+  int32_t dest_s_reg = data->mir->ssa_rep->defs[0];
+
+  if (data->is_move) {
+    // Check if source vreg has changed since the MOVE.
+    int32_t src_s_reg = data->mir->ssa_rep->uses[0];
+    uint32_t src_v_reg = mir_graph_->SRegToVReg(src_s_reg);
+    uint16_t src_change = vreg_chains_.FindFirstChangeAfter(src_v_reg, check_change);
+    bool wide = data->wide_def;
+    if (wide) {
+      uint16_t src_change_high = vreg_chains_.FindFirstChangeAfter(src_v_reg + 1, check_change);
+      if (src_change_high != kNPos && (src_change == kNPos || src_change_high < src_change)) {
+        src_change = src_change_high;
+      }
+    }
+    if (src_change == kNPos ||
+        !vreg_chains_.IsSRegUsed(src_change + 1u, vreg_chains_.NumMIRs(), dest_s_reg)) {
+      // We can simply change all uses of dest to src.
+      size_t rename_end = (src_change != kNPos) ? src_change + 1u : vreg_chains_.NumMIRs();
+      vreg_chains_.RenameVRegUses(check_change + 1u, rename_end,
+                                  dest_s_reg, mir_graph_->SRegToVReg(dest_s_reg),
+                                  src_s_reg,  mir_graph_->SRegToVReg(src_s_reg));
+
+      // Now, remove the MOVE from the vreg chain(s) and kill it.
+      vreg_chains_.RemoveChange(check_change);
+      KillMIR(data);
+      return;
+    }
+  }
+
+  if (data->is_move_src) {
+    // Try to find a MOVE to a vreg that wasn't changed since check_change.
+    uint16_t value_name =
+        data->wide_def ? lvn_->GetSregValueWide(dest_s_reg) : lvn_->GetSregValue(dest_s_reg);
+    for (size_t c = check_change + 1u, size = vreg_chains_.NumMIRs(); c != size; ++c) {
+      MIRData* d = vreg_chains_.GetMIRData(c);
+      if (d->is_move && d->wide_def == data->wide_def &&
+          (d->prev_value.change == kNPos || d->prev_value.change <= check_change) &&
+          (!d->wide_def ||
+           d->prev_value_high.change == kNPos || d->prev_value_high.change <= check_change)) {
+        // Compare value names to find move to move.
+        int32_t src_s_reg = d->mir->ssa_rep->uses[0];
+        uint16_t src_name =
+            (d->wide_def ? lvn_->GetSregValueWide(src_s_reg) : lvn_->GetSregValue(src_s_reg));
+        if (value_name == src_name) {
+          RecordPassKillMoveByRenamingSrcDef(check_change, c);
+          return;
+        }
+      }
+    }
+  }
+}
+
+void GvnDeadCodeElimination::RecordPassTryToKillOverwrittenMoveOrMoveSrc() {
+  // Check if we're overwriting a the result of a move or the definition of a source of a move.
+  // For MOVE_WIDE, we may be overwriting partially; if that's the case, check that the other
+  // word wasn't previously overwritten - we would have tried to rename back then.
+  MIRData* data = vreg_chains_.LastMIRData();
+  if (!data->has_def) {
+    return;
+  }
+  // NOTE: Instructions such as new-array implicitly use all vregs (if they throw) but they can
+  // define a move source which can be renamed. Therefore we allow the checked change to be the
+  // change before no_uses_all_since_. This has no effect on moves as they never use all vregs.
+  if (data->prev_value.change != kNPos && data->prev_value.change + 1u >= no_uses_all_since_) {
+    MIRData* check_data = vreg_chains_.GetMIRData(data->prev_value.change);
+    bool try_to_kill = false;
+    if (!check_data->is_move && !check_data->is_move_src) {
+      DCHECK(!try_to_kill);
+    } else if (!check_data->wide_def) {
+      // Narrow move; always fully overwritten by the last MIR.
+      try_to_kill = true;
+    } else if (data->low_def_over_high_word) {
+      // Overwriting only the high word; is the low word still valid?
+      DCHECK_EQ(check_data->vreg_def + 1u, data->vreg_def);
+      if (vreg_chains_.LastChange(check_data->vreg_def) == data->prev_value.change) {
+        try_to_kill = true;
+      }
+    } else if (!data->wide_def) {
+      // Overwriting only the low word, is the high word still valid?
+      if (vreg_chains_.LastChange(data->vreg_def + 1) == data->prev_value.change) {
+        try_to_kill = true;
+      }
+    } else {
+      // Overwriting both words; was the high word still from the same move?
+      if (data->prev_value_high.change == data->prev_value.change) {
+        try_to_kill = true;
+      }
+    }
+    if (try_to_kill) {
+      RecordPassTryToKillOverwrittenMoveOrMoveSrc(data->prev_value.change);
+    }
+  }
+  if (data->wide_def && data->high_def_over_low_word &&
+      data->prev_value_high.change != kNPos &&
+      data->prev_value_high.change + 1u >= no_uses_all_since_) {
+    MIRData* check_data = vreg_chains_.GetMIRData(data->prev_value_high.change);
+    bool try_to_kill = false;
+    if (!check_data->is_move && !check_data->is_move_src) {
+      DCHECK(!try_to_kill);
+    } else if (!check_data->wide_def) {
+      // Narrow move; always fully overwritten by the last MIR.
+      try_to_kill = true;
+    } else if (vreg_chains_.LastChange(check_data->vreg_def + 1) ==
+        data->prev_value_high.change) {
+      // High word is still valid.
+      try_to_kill = true;
+    }
+    if (try_to_kill) {
+      RecordPassTryToKillOverwrittenMoveOrMoveSrc(data->prev_value_high.change);
+    }
+  }
+}
+
+void GvnDeadCodeElimination::RecordPassTryToKillLastMIR() {
+  MIRData* last_data = vreg_chains_.LastMIRData();
+  if (last_data->must_keep) {
+    return;
+  }
+  if (UNLIKELY(!last_data->has_def)) {
+    // Must be an eliminated MOVE. Drop its data and data of all eliminated MIRs before it.
+    vreg_chains_.RemoveTrailingNops();
+    return;
+  }
+
+  // Try to kill a sequence of consecutive definitions of the same vreg. Allow mixing
+  // wide and non-wide defs; consider high word dead if low word has been overwritten.
+  uint16_t current_value = vreg_chains_.CurrentValue(last_data->vreg_def);
+  uint16_t change = vreg_chains_.NumMIRs() - 1u;
+  MIRData* data = last_data;
+  while (data->prev_value.value != current_value) {
+    --change;
+    if (data->prev_value.change == kNPos || data->prev_value.change != change) {
+      return;
+    }
+    data = vreg_chains_.GetMIRData(data->prev_value.change);
+    if (data->must_keep || !data->has_def || data->vreg_def != last_data->vreg_def) {
+      return;
+    }
+  }
+
+  bool wide = last_data->wide_def;
+  if (wide) {
+    // Check that the low word is valid.
+    if (data->low_def_over_high_word) {
+      return;
+    }
+    // Check that the high word is valid.
+    MIRData* high_data = data;
+    if (!high_data->wide_def) {
+      uint16_t high_change = vreg_chains_.FindFirstChangeAfter(data->vreg_def + 1, change);
+      DCHECK_NE(high_change, kNPos);
+      high_data = vreg_chains_.GetMIRData(high_change);
+      DCHECK_EQ(high_data->vreg_def, data->vreg_def);
+    }
+    if (high_data->prev_value_high.value != current_value || high_data->high_def_over_low_word) {
+      return;
+    }
+  }
+
+  MIR* phi = RenameSRegDefOrCreatePhi(data->prev_value.change, change, last_data->mir);
+  for (size_t i = 0, count = vreg_chains_.NumMIRs() - change; i != count; ++i) {
+    KillMIR(vreg_chains_.LastMIRData()->mir);
+    vreg_chains_.RemoveLastMIRData();
+  }
+  if (phi != nullptr) {
+    // Though the Phi has been added to the beginning, we can put the MIRData at the end.
+    vreg_chains_.AddMIRWithDef(phi, phi->dalvikInsn.vA, wide, current_value);
+    // Reset the previous value to avoid eventually eliminating the Phi itself (unless unused).
+    last_data = vreg_chains_.LastMIRData();
+    last_data->prev_value.value = kNoValue;
+    last_data->prev_value_high.value = kNoValue;
+  }
+}
+
+uint16_t GvnDeadCodeElimination::FindChangesToKill(uint16_t first_change, uint16_t last_change) {
+  // Process dependencies for changes in range [first_change, last_change) and record all
+  // changes that we need to kill. Return kNPos if there's a dependent change that must be
+  // kept unconditionally; otherwise the end of the range processed before encountering
+  // a change that defines a dalvik reg that we need to keep (last_change on full success).
+  changes_to_kill_.clear();
+  dependent_vregs_->ClearAllBits();
+  for (size_t change = first_change; change != last_change; ++change) {
+    MIRData* data = vreg_chains_.GetMIRData(change);
+    DCHECK(!data->uses_all_vregs);
+    bool must_not_depend = data->must_keep;
+    bool depends = false;
+    // Check if the MIR defines a vreg we're trying to eliminate.
+    if (data->has_def && vregs_to_kill_->IsBitSet(data->vreg_def)) {
+      if (change < kill_heads_[data->vreg_def]) {
+        must_not_depend = true;
+      } else {
+        depends = true;
+      }
+    }
+    if (data->has_def && data->wide_def && vregs_to_kill_->IsBitSet(data->vreg_def + 1)) {
+      if (change < kill_heads_[data->vreg_def + 1]) {
+        must_not_depend = true;
+      } else {
+        depends = true;
+      }
+    }
+    if (!depends) {
+      // Check for dependency through SSA reg uses.
+      SSARepresentation* ssa_rep = data->mir->ssa_rep;
+      for (int i = 0; i != ssa_rep->num_uses; ++i) {
+        if (dependent_vregs_->IsBitSet(mir_graph_->SRegToVReg(ssa_rep->uses[i]))) {
+          depends = true;
+          break;
+        }
+      }
+    }
+    // Now check if we can eliminate the insn if we need to.
+    if (depends && must_not_depend) {
+      return kNPos;
+    }
+    if (depends && data->has_def &&
+        vreg_chains_.IsTopChange(change) && !vregs_to_kill_->IsBitSet(data->vreg_def) &&
+        !unused_vregs_->IsBitSet(data->vreg_def) &&
+        (!data->wide_def || !unused_vregs_->IsBitSet(data->vreg_def + 1))) {
+      // This is a top change but neither unnecessary nor one of the top kill changes.
+      return change;
+    }
+    // Finally, update the data.
+    if (depends) {
+      changes_to_kill_.push_back(change);
+      if (data->has_def) {
+        dependent_vregs_->SetBit(data->vreg_def);
+        if (data->wide_def) {
+          dependent_vregs_->SetBit(data->vreg_def + 1);
+        }
+      }
+    } else {
+      if (data->has_def) {
+        dependent_vregs_->ClearBit(data->vreg_def);
+        if (data->wide_def) {
+          dependent_vregs_->ClearBit(data->vreg_def + 1);
+        }
+      }
+    }
+  }
+  return last_change;
+}
+
+void GvnDeadCodeElimination::BackwardPassTryToKillRevertVRegs() {
+}
+
+bool GvnDeadCodeElimination::BackwardPassTryToKillLastMIR() {
+  MIRData* last_data = vreg_chains_.LastMIRData();
+  if (last_data->must_keep) {
+    return false;
+  }
+  DCHECK(!last_data->uses_all_vregs);
+  if (!last_data->has_def) {
+    // Previously eliminated.
+    DCHECK_EQ(static_cast<int>(last_data->mir->dalvikInsn.opcode), static_cast<int>(kMirOpNop));
+    vreg_chains_.RemoveTrailingNops();
+    return true;
+  }
+  if (unused_vregs_->IsBitSet(last_data->vreg_def) ||
+      (last_data->wide_def && unused_vregs_->IsBitSet(last_data->vreg_def + 1))) {
+    if (last_data->wide_def) {
+      // For wide defs, one of the vregs may still be considered needed, fix that.
+      unused_vregs_->SetBit(last_data->vreg_def);
+      unused_vregs_->SetBit(last_data->vreg_def + 1);
+    }
+    KillMIR(last_data->mir);
+    vreg_chains_.RemoveLastMIRData();
+    return true;
+  }
+
+  vregs_to_kill_->ClearAllBits();
+  size_t num_mirs = vreg_chains_.NumMIRs();
+  DCHECK_NE(num_mirs, 0u);
+  uint16_t kill_change = num_mirs - 1u;
+  uint16_t start = num_mirs;
+  size_t num_killed_top_changes = 0u;
+  while (num_killed_top_changes != kMaxNumTopChangesToKill &&
+      kill_change != kNPos && kill_change != num_mirs) {
+    ++num_killed_top_changes;
+
+    DCHECK(vreg_chains_.IsTopChange(kill_change));
+    MIRData* data = vreg_chains_.GetMIRData(kill_change);
+    int count = data->wide_def ? 2 : 1;
+    for (int v_reg = data->vreg_def, end = data->vreg_def + count; v_reg != end; ++v_reg) {
+      uint16_t kill_head = vreg_chains_.FindKillHead(v_reg, no_uses_all_since_);
+      if (kill_head == kNPos) {
+        return false;
+      }
+      kill_heads_[v_reg] = kill_head;
+      vregs_to_kill_->SetBit(v_reg);
+      start = std::min(start, kill_head);
+    }
+    DCHECK_LT(start, vreg_chains_.NumMIRs());
+
+    kill_change = FindChangesToKill(start, num_mirs);
+  }
+
+  if (kill_change != num_mirs) {
+    return false;
+  }
+
+  // Kill all MIRs marked as dependent.
+  for (uint32_t v_reg : vregs_to_kill_->Indexes()) {
+    // Rename s_regs or create Phi only once for each MIR (only for low word).
+    MIRData* data = vreg_chains_.GetMIRData(vreg_chains_.LastChange(v_reg));
+    DCHECK(data->has_def);
+    if (data->vreg_def == v_reg) {
+      MIRData* kill_head_data = vreg_chains_.GetMIRData(kill_heads_[v_reg]);
+      RenameSRegDefOrCreatePhi(kill_head_data->PrevChange(v_reg), num_mirs, data->mir);
+    } else {
+      DCHECK_EQ(data->vreg_def + 1u, v_reg);
+      DCHECK_EQ(vreg_chains_.GetMIRData(kill_heads_[v_reg - 1u])->PrevChange(v_reg - 1u),
+                vreg_chains_.GetMIRData(kill_heads_[v_reg])->PrevChange(v_reg));
+    }
+  }
+  unused_vregs_->Union(vregs_to_kill_);
+  for (auto it = changes_to_kill_.rbegin(), end = changes_to_kill_.rend(); it != end; ++it) {
+    MIRData* data = vreg_chains_.GetMIRData(*it);
+    DCHECK(!data->must_keep);
+    DCHECK(data->has_def);
+    vreg_chains_.RemoveChange(*it);
+    KillMIR(data);
+  }
+
+  vreg_chains_.RemoveTrailingNops();
+  return true;
+}
+
+bool GvnDeadCodeElimination::RecordMIR(MIR* mir) {
+  bool must_keep = false;
+  bool uses_all_vregs = false;
+  bool is_move = false;
+  uint16_t opcode = mir->dalvikInsn.opcode;
+  switch (opcode) {
+    case kMirOpPhi: {
+      // We can't recognize wide variables in Phi from num_defs == 2 as we've got two Phis instead.
+      DCHECK_EQ(mir->ssa_rep->num_defs, 1);
+      int s_reg = mir->ssa_rep->defs[0];
+      bool wide = false;
+      uint16_t new_value = lvn_->GetSregValue(s_reg);
+      if (new_value == kNoValue) {
+        wide = true;
+        new_value = lvn_->GetSregValueWide(s_reg);
+        if (new_value == kNoValue) {
+          return false;  // Ignore the high word Phi.
+        }
+      }
+
+      int v_reg = mir_graph_->SRegToVReg(s_reg);
+      DCHECK_EQ(vreg_chains_.CurrentValue(v_reg), kNoValue);  // No previous def for v_reg.
+      if (wide) {
+        DCHECK_EQ(vreg_chains_.CurrentValue(v_reg + 1), kNoValue);
+      }
+      vreg_chains_.AddMIRWithDef(mir, v_reg, wide, new_value);
+      return true;  // Avoid the common processing.
+    }
+
+    case kMirOpNop:
+    case Instruction::NOP:
+      // Don't record NOPs.
+      return false;
+
+    case kMirOpCheck:
+      must_keep = true;
+      uses_all_vregs = true;
+      break;
+
+    case Instruction::RETURN_VOID:
+    case Instruction::RETURN:
+    case Instruction::RETURN_OBJECT:
+    case Instruction::RETURN_WIDE:
+    case Instruction::GOTO:
+    case Instruction::GOTO_16:
+    case Instruction::GOTO_32:
+    case Instruction::PACKED_SWITCH:
+    case Instruction::SPARSE_SWITCH:
+    case Instruction::IF_EQ:
+    case Instruction::IF_NE:
+    case Instruction::IF_LT:
+    case Instruction::IF_GE:
+    case Instruction::IF_GT:
+    case Instruction::IF_LE:
+    case Instruction::IF_EQZ:
+    case Instruction::IF_NEZ:
+    case Instruction::IF_LTZ:
+    case Instruction::IF_GEZ:
+    case Instruction::IF_GTZ:
+    case Instruction::IF_LEZ:
+    case kMirOpFusedCmplFloat:
+    case kMirOpFusedCmpgFloat:
+    case kMirOpFusedCmplDouble:
+    case kMirOpFusedCmpgDouble:
+    case kMirOpFusedCmpLong:
+      must_keep = true;
+      uses_all_vregs = true;  // Keep the implicit dependencies on all vregs.
+      break;
+
+    case Instruction::CONST_CLASS:
+    case Instruction::CONST_STRING:
+    case Instruction::CONST_STRING_JUMBO:
+      // NOTE: While we're currently treating CONST_CLASS, CONST_STRING and CONST_STRING_JUMBO
+      // as throwing but we could conceivably try and eliminate those exceptions if we're
+      // retrieving the class/string repeatedly.
+      must_keep = true;
+      uses_all_vregs = true;
+      break;
+
+    case Instruction::MONITOR_ENTER:
+    case Instruction::MONITOR_EXIT:
+      // We can actually try and optimize across the acquire operation of MONITOR_ENTER,
+      // the value names provided by GVN reflect the possible changes to memory visibility.
+      // NOTE: In ART, MONITOR_ENTER and MONITOR_EXIT can throw only NPE.
+      must_keep = true;
+      uses_all_vregs = (mir->optimization_flags & MIR_IGNORE_NULL_CHECK) == 0;
+      break;
+
+    case Instruction::INVOKE_DIRECT:
+    case Instruction::INVOKE_DIRECT_RANGE:
+    case Instruction::INVOKE_VIRTUAL:
+    case Instruction::INVOKE_VIRTUAL_RANGE:
+    case Instruction::INVOKE_SUPER:
+    case Instruction::INVOKE_SUPER_RANGE:
+    case Instruction::INVOKE_INTERFACE:
+    case Instruction::INVOKE_INTERFACE_RANGE:
+    case Instruction::INVOKE_STATIC:
+    case Instruction::INVOKE_STATIC_RANGE:
+    case Instruction::CHECK_CAST:
+    case Instruction::THROW:
+    case Instruction::FILLED_NEW_ARRAY:
+    case Instruction::FILLED_NEW_ARRAY_RANGE:
+    case Instruction::FILL_ARRAY_DATA:
+      must_keep = true;
+      uses_all_vregs = true;
+      break;
+
+    case Instruction::NEW_INSTANCE:
+    case Instruction::NEW_ARRAY:
+      must_keep = true;
+      uses_all_vregs = true;
+      break;
+
+    case kMirOpNullCheck:
+      DCHECK_EQ(mir->ssa_rep->num_uses, 1);
+      if ((mir->optimization_flags & MIR_IGNORE_NULL_CHECK) != 0) {
+        mir->ssa_rep->num_uses = 0;
+        mir->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpNop);
+        return false;
+      }
+      must_keep = true;
+      uses_all_vregs = true;
+      break;
+
+    case Instruction::MOVE_RESULT:
+    case Instruction::MOVE_RESULT_OBJECT:
+    case Instruction::MOVE_RESULT_WIDE:
+      break;
+
+    case Instruction::INSTANCE_OF:
+      break;
+
+    case Instruction::MOVE_EXCEPTION:
+      must_keep = true;
+      break;
+
+    case kMirOpCopy:
+    case Instruction::MOVE:
+    case Instruction::MOVE_FROM16:
+    case Instruction::MOVE_16:
+    case Instruction::MOVE_WIDE:
+    case Instruction::MOVE_WIDE_FROM16:
+    case Instruction::MOVE_WIDE_16:
+    case Instruction::MOVE_OBJECT:
+    case Instruction::MOVE_OBJECT_FROM16:
+    case Instruction::MOVE_OBJECT_16: {
+      is_move = true;
+      // If the MIR defining src vreg is known, allow renaming all uses of src vreg to dest vreg
+      // while updating the defining MIR to directly define dest vreg. However, changing Phi's
+      // def this way doesn't work without changing MIRs in other BBs.
+      int src_v_reg = mir_graph_->SRegToVReg(mir->ssa_rep->uses[0]);
+      int src_change = vreg_chains_.LastChange(src_v_reg);
+      if (src_change != kNPos) {
+        MIRData* src_data = vreg_chains_.GetMIRData(src_change);
+        if (static_cast<int>(src_data->mir->dalvikInsn.opcode) != kMirOpPhi) {
+          src_data->is_move_src = true;
+        }
+      }
+      break;
+    }
+
+    case Instruction::CONST_4:
+    case Instruction::CONST_16:
+    case Instruction::CONST:
+    case Instruction::CONST_HIGH16:
+    case Instruction::CONST_WIDE_16:
+    case Instruction::CONST_WIDE_32:
+    case Instruction::CONST_WIDE:
+    case Instruction::CONST_WIDE_HIGH16:
+    case Instruction::ARRAY_LENGTH:
+    case Instruction::CMPL_FLOAT:
+    case Instruction::CMPG_FLOAT:
+    case Instruction::CMPL_DOUBLE:
+    case Instruction::CMPG_DOUBLE:
+    case Instruction::CMP_LONG:
+    case Instruction::NEG_INT:
+    case Instruction::NOT_INT:
+    case Instruction::NEG_LONG:
+    case Instruction::NOT_LONG:
+    case Instruction::NEG_FLOAT:
+    case Instruction::NEG_DOUBLE:
+    case Instruction::INT_TO_LONG:
+    case Instruction::INT_TO_FLOAT:
+    case Instruction::INT_TO_DOUBLE:
+    case Instruction::LONG_TO_INT:
+    case Instruction::LONG_TO_FLOAT:
+    case Instruction::LONG_TO_DOUBLE:
+    case Instruction::FLOAT_TO_INT:
+    case Instruction::FLOAT_TO_LONG:
+    case Instruction::FLOAT_TO_DOUBLE:
+    case Instruction::DOUBLE_TO_INT:
+    case Instruction::DOUBLE_TO_LONG:
+    case Instruction::DOUBLE_TO_FLOAT:
+    case Instruction::INT_TO_BYTE:
+    case Instruction::INT_TO_CHAR:
+    case Instruction::INT_TO_SHORT:
+    case Instruction::ADD_INT:
+    case Instruction::SUB_INT:
+    case Instruction::MUL_INT:
+    case Instruction::AND_INT:
+    case Instruction::OR_INT:
+    case Instruction::XOR_INT:
+    case Instruction::SHL_INT:
+    case Instruction::SHR_INT:
+    case Instruction::USHR_INT:
+    case Instruction::ADD_LONG:
+    case Instruction::SUB_LONG:
+    case Instruction::MUL_LONG:
+    case Instruction::AND_LONG:
+    case Instruction::OR_LONG:
+    case Instruction::XOR_LONG:
+    case Instruction::SHL_LONG:
+    case Instruction::SHR_LONG:
+    case Instruction::USHR_LONG:
+    case Instruction::ADD_FLOAT:
+    case Instruction::SUB_FLOAT:
+    case Instruction::MUL_FLOAT:
+    case Instruction::DIV_FLOAT:
+    case Instruction::REM_FLOAT:
+    case Instruction::ADD_DOUBLE:
+    case Instruction::SUB_DOUBLE:
+    case Instruction::MUL_DOUBLE:
+    case Instruction::DIV_DOUBLE:
+    case Instruction::REM_DOUBLE:
+    case Instruction::ADD_INT_2ADDR:
+    case Instruction::SUB_INT_2ADDR:
+    case Instruction::MUL_INT_2ADDR:
+    case Instruction::AND_INT_2ADDR:
+    case Instruction::OR_INT_2ADDR:
+    case Instruction::XOR_INT_2ADDR:
+    case Instruction::SHL_INT_2ADDR:
+    case Instruction::SHR_INT_2ADDR:
+    case Instruction::USHR_INT_2ADDR:
+    case Instruction::ADD_LONG_2ADDR:
+    case Instruction::SUB_LONG_2ADDR:
+    case Instruction::MUL_LONG_2ADDR:
+    case Instruction::AND_LONG_2ADDR:
+    case Instruction::OR_LONG_2ADDR:
+    case Instruction::XOR_LONG_2ADDR:
+    case Instruction::SHL_LONG_2ADDR:
+    case Instruction::SHR_LONG_2ADDR:
+    case Instruction::USHR_LONG_2ADDR:
+    case Instruction::ADD_FLOAT_2ADDR:
+    case Instruction::SUB_FLOAT_2ADDR:
+    case Instruction::MUL_FLOAT_2ADDR:
+    case Instruction::DIV_FLOAT_2ADDR:
+    case Instruction::REM_FLOAT_2ADDR:
+    case Instruction::ADD_DOUBLE_2ADDR:
+    case Instruction::SUB_DOUBLE_2ADDR:
+    case Instruction::MUL_DOUBLE_2ADDR:
+    case Instruction::DIV_DOUBLE_2ADDR:
+    case Instruction::REM_DOUBLE_2ADDR:
+    case Instruction::ADD_INT_LIT16:
+    case Instruction::RSUB_INT:
+    case Instruction::MUL_INT_LIT16:
+    case Instruction::AND_INT_LIT16:
+    case Instruction::OR_INT_LIT16:
+    case Instruction::XOR_INT_LIT16:
+    case Instruction::ADD_INT_LIT8:
+    case Instruction::RSUB_INT_LIT8:
+    case Instruction::MUL_INT_LIT8:
+    case Instruction::AND_INT_LIT8:
+    case Instruction::OR_INT_LIT8:
+    case Instruction::XOR_INT_LIT8:
+    case Instruction::SHL_INT_LIT8:
+    case Instruction::SHR_INT_LIT8:
+    case Instruction::USHR_INT_LIT8:
+      break;
+
+    case Instruction::DIV_INT:
+    case Instruction::REM_INT:
+    case Instruction::DIV_LONG:
+    case Instruction::REM_LONG:
+    case Instruction::DIV_INT_2ADDR:
+    case Instruction::REM_INT_2ADDR:
+    case Instruction::DIV_LONG_2ADDR:
+    case Instruction::REM_LONG_2ADDR:
+      if ((mir->optimization_flags & MIR_IGNORE_DIV_ZERO_CHECK) == 0) {
+        must_keep = true;
+        uses_all_vregs = true;
+      }
+      break;
+
+    case Instruction::DIV_INT_LIT16:
+    case Instruction::REM_INT_LIT16:
+    case Instruction::DIV_INT_LIT8:
+    case Instruction::REM_INT_LIT8:
+      if (mir->dalvikInsn.vC == 0) {  // Explicit division by 0?
+        must_keep = true;
+        uses_all_vregs = true;
+      }
+      break;
+
+    case Instruction::AGET_OBJECT:
+    case Instruction::AGET:
+    case Instruction::AGET_WIDE:
+    case Instruction::AGET_BOOLEAN:
+    case Instruction::AGET_BYTE:
+    case Instruction::AGET_CHAR:
+    case Instruction::AGET_SHORT:
+      if ((mir->optimization_flags & MIR_IGNORE_NULL_CHECK) == 0 ||
+          (mir->optimization_flags & MIR_IGNORE_RANGE_CHECK) == 0) {
+        must_keep = true;
+        uses_all_vregs = true;
+      }
+      break;
+
+    case Instruction::APUT_OBJECT:
+    case Instruction::APUT:
+    case Instruction::APUT_WIDE:
+    case Instruction::APUT_BYTE:
+    case Instruction::APUT_BOOLEAN:
+    case Instruction::APUT_SHORT:
+    case Instruction::APUT_CHAR:
+      must_keep = true;
+      if ((mir->optimization_flags & MIR_IGNORE_NULL_CHECK) == 0 ||
+          (mir->optimization_flags & MIR_IGNORE_RANGE_CHECK) == 0) {
+        uses_all_vregs = true;
+      }
+      break;
+
+    case Instruction::IGET_OBJECT:
+    case Instruction::IGET:
+    case Instruction::IGET_WIDE:
+    case Instruction::IGET_BOOLEAN:
+    case Instruction::IGET_BYTE:
+    case Instruction::IGET_CHAR:
+    case Instruction::IGET_SHORT: {
+      const MirIFieldLoweringInfo& info = mir_graph_->GetIFieldLoweringInfo(mir);
+      if ((mir->optimization_flags & MIR_IGNORE_NULL_CHECK) == 0 ||
+          !info.IsResolved() || !info.FastGet()) {
+        must_keep = true;
+        uses_all_vregs = true;
+      } else if (info.IsVolatile()) {
+        must_keep = true;
+      }
+      break;
+    }
+
+    case Instruction::IPUT_OBJECT:
+    case Instruction::IPUT:
+    case Instruction::IPUT_WIDE:
+    case Instruction::IPUT_BOOLEAN:
+    case Instruction::IPUT_BYTE:
+    case Instruction::IPUT_CHAR:
+    case Instruction::IPUT_SHORT: {
+      must_keep = true;
+      const MirIFieldLoweringInfo& info = mir_graph_->GetIFieldLoweringInfo(mir);
+      if ((mir->optimization_flags & MIR_IGNORE_NULL_CHECK) == 0 ||
+          !info.IsResolved() || !info.FastPut()) {
+        uses_all_vregs = true;
+      }
+      break;
+    }
+
+    case Instruction::SGET_OBJECT:
+    case Instruction::SGET:
+    case Instruction::SGET_WIDE:
+    case Instruction::SGET_BOOLEAN:
+    case Instruction::SGET_BYTE:
+    case Instruction::SGET_CHAR:
+    case Instruction::SGET_SHORT: {
+      const MirSFieldLoweringInfo& info = mir_graph_->GetSFieldLoweringInfo(mir);
+      if ((mir->optimization_flags & MIR_CLASS_IS_INITIALIZED) == 0 ||
+          !info.IsResolved() || !info.FastGet()) {
+        must_keep = true;
+        uses_all_vregs = true;
+      } else if (info.IsVolatile()) {
+        must_keep = true;
+      }
+      break;
+    }
+
+    case Instruction::SPUT_OBJECT:
+    case Instruction::SPUT:
+    case Instruction::SPUT_WIDE:
+    case Instruction::SPUT_BOOLEAN:
+    case Instruction::SPUT_BYTE:
+    case Instruction::SPUT_CHAR:
+    case Instruction::SPUT_SHORT: {
+      must_keep = true;
+      const MirSFieldLoweringInfo& info = mir_graph_->GetSFieldLoweringInfo(mir);
+      if ((mir->optimization_flags & MIR_CLASS_IS_INITIALIZED) == 0 ||
+          !info.IsResolved() || !info.FastPut()) {
+        uses_all_vregs = true;
+      }
+      break;
+    }
+
+    default:
+      LOG(FATAL) << "Unexpected opcode: " << opcode;
+      UNREACHABLE();
+      break;
+  }
+
+  if (mir->ssa_rep->num_defs != 0) {
+    DCHECK(mir->ssa_rep->num_defs == 1 || mir->ssa_rep->num_defs == 2);
+    bool wide = (mir->ssa_rep->num_defs == 2);
+    int s_reg = mir->ssa_rep->defs[0];
+    int v_reg = mir_graph_->SRegToVReg(s_reg);
+    uint16_t new_value = wide ? lvn_->GetSregValueWide(s_reg) : lvn_->GetSregValue(s_reg);
+    DCHECK_NE(new_value, kNoValue);
+
+    vreg_chains_.UpdateInitialVRegValue(v_reg, wide, lvn_);
+    vreg_chains_.AddMIRWithDef(mir, v_reg, wide, new_value);
+    if (is_move) {
+      // Allow renaming all uses of dest vreg to src vreg.
+      vreg_chains_.LastMIRData()->is_move = true;
+    }
+  } else {
+    vreg_chains_.AddMIRWithoutDef(mir);
+    DCHECK(!is_move) << opcode;
+  }
+
+  if (must_keep) {
+    MIRData* last_data = vreg_chains_.LastMIRData();
+    last_data->must_keep = true;
+    if (uses_all_vregs) {
+      last_data->uses_all_vregs = true;
+      no_uses_all_since_ = vreg_chains_.NumMIRs();
+    }
+  } else {
+    DCHECK_NE(mir->ssa_rep->num_defs, 0) << opcode;
+    DCHECK(!uses_all_vregs) << opcode;
+  }
+  return true;
+}
+
+}  // namespace art
diff --git a/compiler/dex/gvn_dead_code_elimination.h b/compiler/dex/gvn_dead_code_elimination.h
new file mode 100644
index 000000000..ea28039e4
--- /dev/null
+++ b/compiler/dex/gvn_dead_code_elimination.h
@@ -0,0 +1,166 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_COMPILER_DEX_GVN_DEAD_CODE_ELIMINATION_H_
+#define ART_COMPILER_DEX_GVN_DEAD_CODE_ELIMINATION_H_
+
+#include "global_value_numbering.h"
+#include "utils/arena_object.h"
+#include "utils/scoped_arena_containers.h"
+
+namespace art {
+
+class ArenaBitVector;
+class BasicBlock;
+class LocalValueNumbering;
+class MIR;
+class MIRGraph;
+
+/**
+ * @class DeadCodeElimination
+ * @details Eliminate dead code based on the results of global value numbering.
+ * Also get rid of MOVE insns when we can use the source instead of destination
+ * without affecting the vreg values at safepoints; this is useful in methods
+ * with a large number of vregs that frequently move values to and from low vregs
+ * to accommodate insns that can work only with the low 16 or 256 vregs.
+ */
+class GvnDeadCodeElimination : public DeletableArenaObject<kArenaAllocMisc> {
+ public:
+  GvnDeadCodeElimination(const GlobalValueNumbering* gvn, ScopedArenaAllocator* alloc);
+
+  // Apply the DCE to a basic block.
+  void Apply(BasicBlock* bb);
+
+ private:
+  static constexpr uint16_t kNoValue = GlobalValueNumbering::kNoValue;
+  static constexpr uint16_t kNPos = 0xffffu;
+  static constexpr size_t kMaxNumTopChangesToKill = 2;
+
+  struct VRegValue {
+    VRegValue() : value(kNoValue), change(kNPos) { }
+
+    // Value name as reported by GVN, kNoValue if not available.
+    uint16_t value;
+    // Index of the change in mir_data_ that defined the value, kNPos if initial value for the BB.
+    uint16_t change;
+  };
+
+  struct MIRData {
+    explicit MIRData(MIR* m)
+        : mir(m), uses_all_vregs(false), must_keep(false), is_move(false), is_move_src(false),
+          has_def(false), wide_def(false),
+          low_def_over_high_word(false), high_def_over_low_word(false), vreg_def(0u),
+          prev_value(), prev_value_high() {
+    }
+
+    uint16_t PrevChange(int v_reg) const;
+    void SetPrevChange(int v_reg, uint16_t change);
+    void RemovePrevChange(int v_reg, MIRData* prev_data);
+
+    MIR* mir;
+    bool uses_all_vregs : 1;  // If mir uses all vregs, uses in mir->ssa_rep are irrelevant.
+    bool must_keep : 1;
+    bool is_move : 1;
+    bool is_move_src : 1;
+    bool has_def : 1;
+    bool wide_def : 1;
+    bool low_def_over_high_word : 1;
+    bool high_def_over_low_word : 1;
+    uint16_t vreg_def;
+    VRegValue prev_value;
+    VRegValue prev_value_high;   // For wide defs.
+  };
+
+  class VRegChains {
+   public:
+    VRegChains(uint32_t num_vregs, ScopedArenaAllocator* alloc);
+
+    void Reset();
+
+    void AddMIRWithDef(MIR* mir, int v_reg, bool wide, uint16_t new_value);
+    void AddMIRWithoutDef(MIR* mir);
+    void RemoveLastMIRData();
+    void RemoveTrailingNops();
+
+    size_t NumMIRs() const;
+    MIRData* GetMIRData(size_t pos);
+    MIRData* LastMIRData();
+
+    uint32_t NumVRegs() const;
+    void InsertInitialValueHigh(int v_reg, uint16_t value);
+    void UpdateInitialVRegValue(int v_reg, bool wide, const LocalValueNumbering* lvn);
+    uint16_t LastChange(int v_reg);
+    uint16_t CurrentValue(int v_reg);
+
+    uint16_t FindKillHead(int v_reg, uint16_t cutoff);
+    uint16_t FindFirstChangeAfter(int v_reg, uint16_t change) const;
+    void ReplaceChange(uint16_t old_change, uint16_t new_change);
+    void RemoveChange(uint16_t change);
+    bool IsTopChange(uint16_t change) const;
+    bool IsSRegUsed(uint16_t first_change, uint16_t last_change, int s_reg) const;
+    void RenameSRegUses(uint16_t first_change, uint16_t last_change,
+                        int old_s_reg, int new_s_reg, bool wide);
+    void RenameVRegUses(uint16_t first_change, uint16_t last_change,
+                        int old_s_reg, int old_v_reg, int new_s_reg, int new_v_reg);
+
+   private:
+    const uint32_t num_vregs_;
+    VRegValue* const vreg_data_;
+    ScopedArenaVector<MIRData> mir_data_;
+  };
+
+  void RecordPass();
+  void BackwardPass();
+
+  void KillMIR(MIRData* data);
+  static void KillMIR(MIR* mir);
+  static void ChangeBinOp2AddrToPlainBinOp(MIR* mir);
+  MIR* CreatePhi(int s_reg, bool fp);
+  MIR* RenameSRegDefOrCreatePhi(uint16_t def_change, uint16_t last_change, MIR* mir_to_kill);
+
+  // Update state variables going backwards through a MIR.
+  void BackwardPassProcessLastMIR();
+
+  uint16_t FindChangesToKill(uint16_t first_change, uint16_t last_change);
+  void BackwardPassTryToKillRevertVRegs();
+  bool BackwardPassTryToKillLastMIR();
+
+  void RecordPassKillMoveByRenamingSrcDef(uint16_t src_change, uint16_t move_change);
+  void RecordPassTryToKillOverwrittenMoveOrMoveSrc(uint16_t check_change);
+  void RecordPassTryToKillOverwrittenMoveOrMoveSrc();
+  void RecordPassTryToKillLastMIR();
+
+  bool RecordMIR(MIR* mir);
+
+  const GlobalValueNumbering* const gvn_;
+  MIRGraph* const mir_graph_;
+
+  VRegChains vreg_chains_;
+  BasicBlock* bb_;
+  const LocalValueNumbering* lvn_;
+  size_t no_uses_all_since_;  // The change index after the last change with uses_all_vregs set.
+
+  // Data used when processing MIRs in reverse order.
+  ArenaBitVector* unused_vregs_;              // vregs that are not needed later.
+  ArenaBitVector* vregs_to_kill_;             // vregs that revert to a previous value.
+  uint16_t* kill_heads_;  // For each vreg in vregs_to_kill_, the first change to kill.
+  ScopedArenaVector<uint16_t> changes_to_kill_;
+  ArenaBitVector* dependent_vregs_;
+};
+
+}  // namespace art
+
+#endif  // ART_COMPILER_DEX_GVN_DEAD_CODE_ELIMINATION_H_
diff --git a/compiler/dex/gvn_dead_code_elimination_test.cc b/compiler/dex/gvn_dead_code_elimination_test.cc
new file mode 100644
index 000000000..954e9f1d3
--- /dev/null
+++ b/compiler/dex/gvn_dead_code_elimination_test.cc
@@ -0,0 +1,1800 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "dataflow_iterator-inl.h"
+#include "dex/mir_field_info.h"
+#include "global_value_numbering.h"
+#include "gvn_dead_code_elimination.h"
+#include "local_value_numbering.h"
+#include "gtest/gtest.h"
+
+namespace art {
+
+class GvnDeadCodeEliminationTest : public testing::Test {
+ protected:
+  static constexpr uint16_t kNoValue = GlobalValueNumbering::kNoValue;
+
+  struct IFieldDef {
+    uint16_t field_idx;
+    uintptr_t declaring_dex_file;
+    uint16_t declaring_field_idx;
+    bool is_volatile;
+    DexMemAccessType type;
+  };
+
+  struct SFieldDef {
+    uint16_t field_idx;
+    uintptr_t declaring_dex_file;
+    uint16_t declaring_field_idx;
+    bool is_volatile;
+    DexMemAccessType type;
+  };
+
+  struct BBDef {
+    static constexpr size_t kMaxSuccessors = 4;
+    static constexpr size_t kMaxPredecessors = 4;
+
+    BBType type;
+    size_t num_successors;
+    BasicBlockId successors[kMaxPredecessors];
+    size_t num_predecessors;
+    BasicBlockId predecessors[kMaxPredecessors];
+  };
+
+  struct MIRDef {
+    static constexpr size_t kMaxSsaDefs = 2;
+    static constexpr size_t kMaxSsaUses = 4;
+
+    BasicBlockId bbid;
+    Instruction::Code opcode;
+    int64_t value;
+    uint32_t field_info;
+    size_t num_uses;
+    int32_t uses[kMaxSsaUses];
+    size_t num_defs;
+    int32_t defs[kMaxSsaDefs];
+  };
+
+#define DEF_SUCC0() \
+    0u, { }
+#define DEF_SUCC1(s1) \
+    1u, { s1 }
+#define DEF_SUCC2(s1, s2) \
+    2u, { s1, s2 }
+#define DEF_SUCC3(s1, s2, s3) \
+    3u, { s1, s2, s3 }
+#define DEF_SUCC4(s1, s2, s3, s4) \
+    4u, { s1, s2, s3, s4 }
+#define DEF_PRED0() \
+    0u, { }
+#define DEF_PRED1(p1) \
+    1u, { p1 }
+#define DEF_PRED2(p1, p2) \
+    2u, { p1, p2 }
+#define DEF_PRED3(p1, p2, p3) \
+    3u, { p1, p2, p3 }
+#define DEF_PRED4(p1, p2, p3, p4) \
+    4u, { p1, p2, p3, p4 }
+#define DEF_BB(type, succ, pred) \
+    { type, succ, pred }
+
+#define DEF_CONST(bb, opcode, reg, value) \
+    { bb, opcode, value, 0u, 0, { }, 1, { reg } }
+#define DEF_CONST_WIDE(bb, opcode, reg, value) \
+    { bb, opcode, value, 0u, 0, { }, 2, { reg, reg + 1 } }
+#define DEF_CONST_STRING(bb, opcode, reg, index) \
+    { bb, opcode, index, 0u, 0, { }, 1, { reg } }
+#define DEF_IGET(bb, opcode, reg, obj, field_info) \
+    { bb, opcode, 0u, field_info, 1, { obj }, 1, { reg } }
+#define DEF_IGET_WIDE(bb, opcode, reg, obj, field_info) \
+    { bb, opcode, 0u, field_info, 1, { obj }, 2, { reg, reg + 1 } }
+#define DEF_IPUT(bb, opcode, reg, obj, field_info) \
+    { bb, opcode, 0u, field_info, 2, { reg, obj }, 0, { } }
+#define DEF_IPUT_WIDE(bb, opcode, reg, obj, field_info) \
+    { bb, opcode, 0u, field_info, 3, { reg, reg + 1, obj }, 0, { } }
+#define DEF_SGET(bb, opcode, reg, field_info) \
+    { bb, opcode, 0u, field_info, 0, { }, 1, { reg } }
+#define DEF_SGET_WIDE(bb, opcode, reg, field_info) \
+    { bb, opcode, 0u, field_info, 0, { }, 2, { reg, reg + 1 } }
+#define DEF_SPUT(bb, opcode, reg, field_info) \
+    { bb, opcode, 0u, field_info, 1, { reg }, 0, { } }
+#define DEF_SPUT_WIDE(bb, opcode, reg, field_info) \
+    { bb, opcode, 0u, field_info, 2, { reg, reg + 1 }, 0, { } }
+#define DEF_AGET(bb, opcode, reg, obj, idx) \
+    { bb, opcode, 0u, 0u, 2, { obj, idx }, 1, { reg } }
+#define DEF_AGET_WIDE(bb, opcode, reg, obj, idx) \
+    { bb, opcode, 0u, 0u, 2, { obj, idx }, 2, { reg, reg + 1 } }
+#define DEF_APUT(bb, opcode, reg, obj, idx) \
+    { bb, opcode, 0u, 0u, 3, { reg, obj, idx }, 0, { } }
+#define DEF_APUT_WIDE(bb, opcode, reg, obj, idx) \
+    { bb, opcode, 0u, 0u, 4, { reg, reg + 1, obj, idx }, 0, { } }
+#define DEF_INVOKE1(bb, opcode, reg) \
+    { bb, opcode, 0u, 0u, 1, { reg }, 0, { } }
+#define DEF_UNIQUE_REF(bb, opcode, reg) \
+    { bb, opcode, 0u, 0u, 0, { }, 1, { reg } }  // CONST_CLASS, CONST_STRING, NEW_ARRAY, ...
+#define DEF_IFZ(bb, opcode, reg) \
+    { bb, opcode, 0u, 0u, 1, { reg }, 0, { } }
+#define DEF_MOVE(bb, opcode, reg, src) \
+    { bb, opcode, 0u, 0u, 1, { src }, 1, { reg } }
+#define DEF_MOVE_WIDE(bb, opcode, reg, src) \
+    { bb, opcode, 0u, 0u, 2, { src, src + 1 }, 2, { reg, reg + 1 } }
+#define DEF_PHI2(bb, reg, src1, src2) \
+    { bb, static_cast<Instruction::Code>(kMirOpPhi), 0, 0u, 2u, { src1, src2 }, 1, { reg } }
+#define DEF_UNOP(bb, opcode, result, src1) \
+    { bb, opcode, 0u, 0u, 1, { src1 }, 1, { result } }
+#define DEF_BINOP(bb, opcode, result, src1, src2) \
+    { bb, opcode, 0u, 0u, 2, { src1, src2 }, 1, { result } }
+
+  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, def->type);
+      if (def->declaring_dex_file != 0u) {
+        field_info.declaring_dex_file_ = reinterpret_cast<const DexFile*>(def->declaring_dex_file);
+        field_info.declaring_field_idx_ = def->declaring_field_idx;
+        field_info.flags_ =
+            MirIFieldLoweringInfo::kFlagFastGet | MirIFieldLoweringInfo::kFlagFastPut |
+            (field_info.flags_ & ~(def->is_volatile ? 0u : MirIFieldLoweringInfo::kFlagIsVolatile));
+      }
+      cu_.mir_graph->ifield_lowering_infos_.push_back(field_info);
+    }
+  }
+
+  template <size_t count>
+  void PrepareIFields(const IFieldDef (&defs)[count]) {
+    DoPrepareIFields(defs, count);
+  }
+
+  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, def->type);
+      // Mark even unresolved fields as initialized.
+      field_info.flags_ |= MirSFieldLoweringInfo::kFlagClassIsInitialized;
+      // NOTE: MirSFieldLoweringInfo::kFlagClassIsInDexCache isn't used by GVN.
+      if (def->declaring_dex_file != 0u) {
+        field_info.declaring_dex_file_ = reinterpret_cast<const DexFile*>(def->declaring_dex_file);
+        field_info.declaring_field_idx_ = def->declaring_field_idx;
+        field_info.flags_ =
+            MirSFieldLoweringInfo::kFlagFastGet | MirSFieldLoweringInfo::kFlagFastPut |
+            (field_info.flags_ & ~(def->is_volatile ? 0u : MirSFieldLoweringInfo::kFlagIsVolatile));
+      }
+      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();
+    ASSERT_LT(3u, count);  // null, entry, exit and at least one bytecode block.
+    ASSERT_EQ(kNullBlock, defs[0].type);
+    ASSERT_EQ(kEntryBlock, defs[1].type);
+    ASSERT_EQ(kExitBlock, defs[2].type);
+    for (size_t i = 0u; i != count; ++i) {
+      const BBDef* def = &defs[i];
+      BasicBlock* bb = cu_.mir_graph->CreateNewBB(def->type);
+      if (def->num_successors <= 2) {
+        bb->successor_block_list_type = kNotUsed;
+        bb->fall_through = (def->num_successors >= 1) ? def->successors[0] : 0u;
+        bb->taken = (def->num_successors >= 2) ? def->successors[1] : 0u;
+      } else {
+        bb->successor_block_list_type = kPackedSwitch;
+        bb->fall_through = 0u;
+        bb->taken = 0u;
+        bb->successor_blocks.reserve(def->num_successors);
+        for (size_t j = 0u; j != def->num_successors; ++j) {
+          SuccessorBlockInfo* successor_block_info =
+              static_cast<SuccessorBlockInfo*>(cu_.arena.Alloc(sizeof(SuccessorBlockInfo),
+                                                               kArenaAllocSuccessor));
+          successor_block_info->block = j;
+          successor_block_info->key = 0u;  // Not used by class init check elimination.
+          bb->successor_blocks.push_back(successor_block_info);
+        }
+      }
+      bb->predecessors.assign(def->predecessors, def->predecessors + def->num_predecessors);
+      if (def->type == kDalvikByteCode || def->type == kEntryBlock || def->type == kExitBlock) {
+        bb->data_flow_info = static_cast<BasicBlockDataFlow*>(
+            cu_.arena.Alloc(sizeof(BasicBlockDataFlow), kArenaAllocDFInfo));
+        bb->data_flow_info->live_in_v = live_in_v_;
+        bb->data_flow_info->vreg_to_ssa_map_exit = nullptr;
+      }
+    }
+    ASSERT_EQ(count, cu_.mir_graph->block_list_.size());
+    cu_.mir_graph->entry_block_ = cu_.mir_graph->block_list_[1];
+    ASSERT_EQ(kEntryBlock, cu_.mir_graph->entry_block_->block_type);
+    cu_.mir_graph->exit_block_ = cu_.mir_graph->block_list_[2];
+    ASSERT_EQ(kExitBlock, cu_.mir_graph->exit_block_->block_type);
+  }
+
+  template <size_t count>
+  void PrepareBasicBlocks(const BBDef (&defs)[count]) {
+    DoPrepareBasicBlocks(defs, count);
+  }
+
+  int SRegToVReg(int32_t s_reg, bool wide) {
+    int v_reg = cu_.mir_graph->SRegToVReg(s_reg);
+    CHECK_LT(static_cast<size_t>(v_reg), num_vregs_);
+    if (wide) {
+      CHECK_LT(static_cast<size_t>(v_reg + 1), num_vregs_);
+    }
+    return v_reg;
+  }
+
+  int SRegToVReg(int32_t* uses, size_t* use, bool wide) {
+    int v_reg = SRegToVReg(uses[*use], wide);
+    if (wide) {
+      CHECK_EQ(uses[*use] + 1, uses[*use + 1]);
+      *use += 2u;
+    } else {
+      *use += 1u;
+    }
+    return v_reg;
+  }
+
+  void DoPrepareMIRs(const MIRDef* defs, size_t count) {
+    mir_count_ = count;
+    mirs_ = reinterpret_cast<MIR*>(cu_.arena.Alloc(sizeof(MIR) * count, kArenaAllocMIR));
+    ssa_reps_.resize(count);
+    for (size_t i = 0u; i != count; ++i) {
+      const MIRDef* def = &defs[i];
+      MIR* mir = &mirs_[i];
+      ASSERT_LT(def->bbid, cu_.mir_graph->block_list_.size());
+      BasicBlock* bb = cu_.mir_graph->block_list_[def->bbid];
+      bb->AppendMIR(mir);
+      mir->dalvikInsn.opcode = def->opcode;
+      mir->dalvikInsn.vB = static_cast<int32_t>(def->value);
+      mir->dalvikInsn.vB_wide = def->value;
+      if (IsInstructionIGetOrIPut(def->opcode)) {
+        ASSERT_LT(def->field_info, cu_.mir_graph->ifield_lowering_infos_.size());
+        mir->meta.ifield_lowering_info = def->field_info;
+        ASSERT_EQ(cu_.mir_graph->ifield_lowering_infos_[def->field_info].MemAccessType(),
+                  IGetOrIPutMemAccessType(def->opcode));
+      } else if (IsInstructionSGetOrSPut(def->opcode)) {
+        ASSERT_LT(def->field_info, cu_.mir_graph->sfield_lowering_infos_.size());
+        mir->meta.sfield_lowering_info = def->field_info;
+        ASSERT_EQ(cu_.mir_graph->sfield_lowering_infos_[def->field_info].MemAccessType(),
+                  SGetOrSPutMemAccessType(def->opcode));
+      } else if (def->opcode == static_cast<Instruction::Code>(kMirOpPhi)) {
+        mir->meta.phi_incoming =
+            allocator_->AllocArray<BasicBlockId>(def->num_uses, kArenaAllocDFInfo);
+        ASSERT_EQ(def->num_uses, bb->predecessors.size());
+        std::copy(bb->predecessors.begin(), bb->predecessors.end(), mir->meta.phi_incoming);
+      }
+      mir->ssa_rep = &ssa_reps_[i];
+      cu_.mir_graph->AllocateSSAUseData(mir, def->num_uses);
+      std::copy_n(def->uses, def->num_uses, mir->ssa_rep->uses);
+      // Keep mir->ssa_rep->fp_use[.] zero-initialized (false). Not used by DCE, only copied.
+      cu_.mir_graph->AllocateSSADefData(mir, def->num_defs);
+      std::copy_n(def->defs, def->num_defs, mir->ssa_rep->defs);
+      // Keep mir->ssa_rep->fp_def[.] zero-initialized (false). Not used by DCE, only copied.
+      mir->dalvikInsn.opcode = def->opcode;
+      mir->offset = i;  // LVN uses offset only for debug output
+      mir->optimization_flags = 0u;
+      uint64_t df_attrs = MIRGraph::GetDataFlowAttributes(mir);
+      if ((df_attrs & DF_DA) != 0) {
+        CHECK_NE(def->num_defs, 0u);
+        mir->dalvikInsn.vA = SRegToVReg(def->defs[0], (df_attrs & DF_A_WIDE) != 0);
+        bb->data_flow_info->vreg_to_ssa_map_exit[mir->dalvikInsn.vA] = def->defs[0];
+        if ((df_attrs & DF_A_WIDE) != 0) {
+          CHECK_EQ(def->defs[0] + 1, def->defs[1]);
+          bb->data_flow_info->vreg_to_ssa_map_exit[mir->dalvikInsn.vA + 1u] = def->defs[0] + 1;
+        }
+      }
+      if ((df_attrs & (DF_UA | DF_UB | DF_UC)) != 0) {
+        size_t use = 0;
+        if ((df_attrs & DF_UA) != 0) {
+          mir->dalvikInsn.vA = SRegToVReg(mir->ssa_rep->uses, &use, (df_attrs & DF_A_WIDE) != 0);
+        }
+        if ((df_attrs & DF_UB) != 0) {
+          mir->dalvikInsn.vB = SRegToVReg(mir->ssa_rep->uses, &use, (df_attrs & DF_B_WIDE) != 0);
+        }
+        if ((df_attrs & DF_UC) != 0) {
+          mir->dalvikInsn.vC = SRegToVReg(mir->ssa_rep->uses, &use, (df_attrs & DF_C_WIDE) != 0);
+        }
+        DCHECK_EQ(def->num_uses, use);
+      }
+    }
+    DexFile::CodeItem* code_item = static_cast<DexFile::CodeItem*>(
+        cu_.arena.Alloc(sizeof(DexFile::CodeItem), kArenaAllocMisc));
+    code_item->insns_size_in_code_units_ = 2u * count;
+    code_item->registers_size_ = kMaxVRegs;
+    cu_.mir_graph->current_code_item_ = code_item;
+  }
+
+  template <size_t count>
+  void PrepareMIRs(const MIRDef (&defs)[count]) {
+    DoPrepareMIRs(defs, count);
+  }
+
+  template <size_t count>
+  void PrepareSRegToVRegMap(const int (&map)[count]) {
+    cu_.mir_graph->ssa_base_vregs_.assign(map, map + count);
+    num_vregs_ = *std::max_element(map, map + count) + 1u;
+    AllNodesIterator iterator(cu_.mir_graph.get());
+    for (BasicBlock* bb = iterator.Next(); bb != nullptr; bb = iterator.Next()) {
+      if (bb->data_flow_info != nullptr) {
+        bb->data_flow_info->vreg_to_ssa_map_exit = static_cast<int32_t*>(
+            cu_.arena.Alloc(sizeof(int32_t) * num_vregs_, kArenaAllocDFInfo));
+        std::fill_n(bb->data_flow_info->vreg_to_ssa_map_exit, num_vregs_, INVALID_SREG);
+      }
+    }
+  }
+
+  void PerformGVN() {
+    cu_.mir_graph->SSATransformationStart();
+    cu_.mir_graph->ComputeDFSOrders();
+    cu_.mir_graph->ComputeDominators();
+    cu_.mir_graph->ComputeTopologicalSortOrder();
+    cu_.mir_graph->SSATransformationEnd();
+    cu_.mir_graph->temp_.gvn.ifield_ids =  GlobalValueNumbering::PrepareGvnFieldIds(
+        allocator_.get(), cu_.mir_graph->ifield_lowering_infos_);
+    cu_.mir_graph->temp_.gvn.sfield_ids =  GlobalValueNumbering::PrepareGvnFieldIds(
+        allocator_.get(), cu_.mir_graph->sfield_lowering_infos_);
+    ASSERT_TRUE(gvn_ == nullptr);
+    gvn_.reset(new (allocator_.get()) GlobalValueNumbering(&cu_, allocator_.get(),
+                                                           GlobalValueNumbering::kModeGvn));
+    value_names_.resize(mir_count_, 0xffffu);
+    LoopRepeatingTopologicalSortIterator iterator(cu_.mir_graph.get());
+    bool change = false;
+    for (BasicBlock* bb = iterator.Next(change); bb != nullptr; bb = iterator.Next(change)) {
+      LocalValueNumbering* lvn = gvn_->PrepareBasicBlock(bb);
+      if (lvn != nullptr) {
+        for (MIR* mir = bb->first_mir_insn; mir != nullptr; mir = mir->next) {
+          value_names_[mir - mirs_] = lvn->GetValueNumber(mir);
+        }
+      }
+      change = (lvn != nullptr) && gvn_->FinishBasicBlock(bb);
+      ASSERT_TRUE(gvn_->Good());
+    }
+  }
+
+  void PerformGVNCodeModifications() {
+    ASSERT_TRUE(gvn_ != nullptr);
+    ASSERT_TRUE(gvn_->Good());
+    gvn_->StartPostProcessing();
+    TopologicalSortIterator iterator(cu_.mir_graph.get());
+    for (BasicBlock* bb = iterator.Next(); bb != nullptr; bb = iterator.Next()) {
+      LocalValueNumbering* lvn = gvn_->PrepareBasicBlock(bb);
+      if (lvn != nullptr) {
+        for (MIR* mir = bb->first_mir_insn; mir != nullptr; mir = mir->next) {
+          uint16_t value_name = lvn->GetValueNumber(mir);
+          ASSERT_EQ(value_name, value_names_[mir - mirs_]);
+        }
+      }
+      bool change = (lvn != nullptr) && gvn_->FinishBasicBlock(bb);
+      ASSERT_FALSE(change);
+      ASSERT_TRUE(gvn_->Good());
+    }
+  }
+
+  void FillVregToSsaRegExitMaps() {
+    // Fill in vreg_to_ssa_map_exit for each BB.
+    PreOrderDfsIterator iterator(cu_.mir_graph.get());
+    for (BasicBlock* bb = iterator.Next(); bb != nullptr; bb = iterator.Next()) {
+      if (bb->block_type == kDalvikByteCode) {
+        CHECK(!bb->predecessors.empty());
+        BasicBlock* pred_bb = cu_.mir_graph->GetBasicBlock(bb->predecessors[0]);
+        for (size_t v_reg = 0; v_reg != num_vregs_; ++v_reg) {
+          if (bb->data_flow_info->vreg_to_ssa_map_exit[v_reg] == INVALID_SREG) {
+            bb->data_flow_info->vreg_to_ssa_map_exit[v_reg] =
+                pred_bb->data_flow_info->vreg_to_ssa_map_exit[v_reg];
+          }
+        }
+      }
+    }
+  }
+
+  void PerformDCE() {
+    FillVregToSsaRegExitMaps();
+    cu_.mir_graph->GetNumOfCodeAndTempVRs();
+    dce_.reset(new (allocator_.get()) GvnDeadCodeElimination(gvn_.get(), allocator_.get()));
+    PreOrderDfsIterator iterator(cu_.mir_graph.get());
+    for (BasicBlock* bb = iterator.Next(); bb != nullptr; bb = iterator.Next()) {
+      if (bb->block_type == kDalvikByteCode) {
+        dce_->Apply(bb);
+      }
+    }
+  }
+
+  void PerformGVN_DCE() {
+    PerformGVN();
+    PerformGVNCodeModifications();  // Eliminate null/range checks.
+    PerformDCE();
+  }
+
+  template <size_t count>
+  void ExpectValueNamesNE(const size_t (&indexes)[count]) {
+    for (size_t i1 = 0; i1 != count; ++i1) {
+      size_t idx1 = indexes[i1];
+      for (size_t i2 = i1 + 1; i2 != count; ++i2) {
+        size_t idx2 = indexes[i2];
+        EXPECT_NE(value_names_[idx1], value_names_[idx2]) << idx1 << " " << idx2;
+      }
+    }
+  }
+
+  template <size_t count>
+  void ExpectNoNullCheck(const size_t (&indexes)[count]) {
+    for (size_t i = 0; i != count; ++i) {
+      size_t idx = indexes[i];
+      EXPECT_EQ(MIR_IGNORE_NULL_CHECK, mirs_[idx].optimization_flags & MIR_IGNORE_NULL_CHECK)
+          << idx;
+    }
+    size_t num_no_null_ck = 0u;
+    for (size_t i = 0; i != mir_count_; ++i) {
+      if ((mirs_[i].optimization_flags & MIR_IGNORE_NULL_CHECK) != 0) {
+        ++num_no_null_ck;
+      }
+    }
+    EXPECT_EQ(count, num_no_null_ck);
+  }
+
+  GvnDeadCodeEliminationTest()
+      : pool_(),
+        cu_(&pool_, kRuntimeISA, nullptr, nullptr),
+        num_vregs_(0u),
+        mir_count_(0u),
+        mirs_(nullptr),
+        ssa_reps_(),
+        allocator_(),
+        gvn_(),
+        dce_(),
+        value_names_(),
+        live_in_v_(new (&cu_.arena) ArenaBitVector(&cu_.arena, kMaxSsaRegs, false, kBitMapMisc)) {
+    cu_.mir_graph.reset(new MIRGraph(&cu_, &cu_.arena));
+    cu_.access_flags = kAccStatic;  // Don't let "this" interfere with this test.
+    allocator_.reset(ScopedArenaAllocator::Create(&cu_.arena_stack));
+    // By default, the zero-initialized reg_location_[.] with ref == false tells LVN that
+    // 0 constants are integral, not references. Nothing else is used by LVN/GVN.
+    cu_.mir_graph->reg_location_ = static_cast<RegLocation*>(cu_.arena.Alloc(
+        kMaxSsaRegs * sizeof(cu_.mir_graph->reg_location_[0]), kArenaAllocRegAlloc));
+    // Bind all possible sregs to live vregs for test purposes.
+    live_in_v_->SetInitialBits(kMaxSsaRegs);
+    cu_.mir_graph->ssa_base_vregs_.reserve(kMaxSsaRegs);
+    cu_.mir_graph->ssa_subscripts_.reserve(kMaxSsaRegs);
+    for (unsigned int i = 0; i < kMaxSsaRegs; i++) {
+      cu_.mir_graph->ssa_base_vregs_.push_back(i);
+      cu_.mir_graph->ssa_subscripts_.push_back(0);
+    }
+    // Set shorty for a void-returning method without arguments.
+    cu_.shorty = "V";
+  }
+
+  static constexpr size_t kMaxSsaRegs = 16384u;
+  static constexpr size_t kMaxVRegs = 256u;
+
+  ArenaPool pool_;
+  CompilationUnit cu_;
+  size_t num_vregs_;
+  size_t mir_count_;
+  MIR* mirs_;
+  std::vector<SSARepresentation> ssa_reps_;
+  std::unique_ptr<ScopedArenaAllocator> allocator_;
+  std::unique_ptr<GlobalValueNumbering> gvn_;
+  std::unique_ptr<GvnDeadCodeElimination> dce_;
+  std::vector<uint16_t> value_names_;
+  ArenaBitVector* live_in_v_;
+};
+
+constexpr uint16_t GvnDeadCodeEliminationTest::kNoValue;
+
+class GvnDeadCodeEliminationTestSimple : public GvnDeadCodeEliminationTest {
+ public:
+  GvnDeadCodeEliminationTestSimple();
+
+ private:
+  static const BBDef kSimpleBbs[];
+};
+
+const GvnDeadCodeEliminationTest::BBDef GvnDeadCodeEliminationTestSimple::kSimpleBbs[] = {
+    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)),
+};
+
+GvnDeadCodeEliminationTestSimple::GvnDeadCodeEliminationTestSimple()
+    : GvnDeadCodeEliminationTest() {
+  PrepareBasicBlocks(kSimpleBbs);
+}
+
+class GvnDeadCodeEliminationTestDiamond : public GvnDeadCodeEliminationTest {
+ public:
+  GvnDeadCodeEliminationTestDiamond();
+
+ private:
+  static const BBDef kDiamondBbs[];
+};
+
+const GvnDeadCodeEliminationTest::BBDef GvnDeadCodeEliminationTestDiamond::kDiamondBbs[] = {
+    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)),  // Block #3, top of the diamond.
+    DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)),     // Block #4, left side.
+    DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)),     // Block #5, right side.
+    DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED2(4, 5)),  // Block #6, bottom.
+};
+
+GvnDeadCodeEliminationTestDiamond::GvnDeadCodeEliminationTestDiamond()
+    : GvnDeadCodeEliminationTest() {
+  PrepareBasicBlocks(kDiamondBbs);
+}
+
+class GvnDeadCodeEliminationTestLoop : public GvnDeadCodeEliminationTest {
+ public:
+  GvnDeadCodeEliminationTestLoop();
+
+ private:
+  static const BBDef kLoopBbs[];
+};
+
+const GvnDeadCodeEliminationTest::BBDef GvnDeadCodeEliminationTestLoop::kLoopBbs[] = {
+    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)),
+};
+
+GvnDeadCodeEliminationTestLoop::GvnDeadCodeEliminationTestLoop()
+    : GvnDeadCodeEliminationTest() {
+  PrepareBasicBlocks(kLoopBbs);
+}
+
+TEST_F(GvnDeadCodeEliminationTestSimple, Rename1) {
+  static const IFieldDef ifields[] = {
+      { 0u, 1u, 0u, false, kDexMemAccessWord },
+      { 1u, 1u, 1u, false, kDexMemAccessWord },
+  };
+  static const MIRDef mirs[] = {
+      DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u),
+      DEF_IGET(3, Instruction::IGET, 1u, 0u, 0u),
+      DEF_MOVE(3, Instruction::MOVE_OBJECT, 2u, 0u),
+      DEF_IGET(3, Instruction::IGET, 3u, 2u, 1u),
+  };
+
+  static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 2 };
+  PrepareSRegToVRegMap(sreg_to_vreg_map);
+
+  PrepareIFields(ifields);
+  PrepareMIRs(mirs);
+  PerformGVN_DCE();
+
+  ASSERT_EQ(arraysize(mirs), value_names_.size());
+  static const size_t diff_indexes[] = { 0, 1, 3 };
+  ExpectValueNamesNE(diff_indexes);
+  EXPECT_EQ(value_names_[0], value_names_[2]);
+
+  const size_t no_null_ck_indexes[] = { 1, 3 };
+  ExpectNoNullCheck(no_null_ck_indexes);
+
+  static const bool eliminated[] = {
+      false, false, true, false
+  };
+  static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch");
+  for (size_t i = 0; i != arraysize(eliminated); ++i) {
+    bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop);
+    EXPECT_EQ(eliminated[i], actually_eliminated) << i;
+  }
+  // Check that the IGET uses the s_reg 0, v_reg 0, defined by mirs_[0].
+  ASSERT_EQ(1, mirs_[3].ssa_rep->num_uses);
+  EXPECT_EQ(0, mirs_[3].ssa_rep->uses[0]);
+  EXPECT_EQ(0u, mirs_[3].dalvikInsn.vB);
+}
+
+TEST_F(GvnDeadCodeEliminationTestSimple, Rename2) {
+  static const IFieldDef ifields[] = {
+      { 0u, 1u, 0u, false, kDexMemAccessWord },
+      { 1u, 1u, 1u, false, kDexMemAccessWord },
+  };
+  static const MIRDef mirs[] = {
+      DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u),
+      DEF_IGET(3, Instruction::IGET, 1u, 0u, 0u),
+      DEF_MOVE(3, Instruction::MOVE_OBJECT, 2u, 0u),
+      DEF_IGET(3, Instruction::IGET, 3u, 2u, 1u),
+      DEF_CONST(3, Instruction::CONST, 4u, 1000),
+  };
+
+  static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 3, 2 };
+  PrepareSRegToVRegMap(sreg_to_vreg_map);
+
+  PrepareIFields(ifields);
+  PrepareMIRs(mirs);
+  PerformGVN_DCE();
+
+  ASSERT_EQ(arraysize(mirs), value_names_.size());
+  static const size_t diff_indexes[] = { 0, 1, 3, 4 };
+  ExpectValueNamesNE(diff_indexes);
+  EXPECT_EQ(value_names_[0], value_names_[2]);
+
+  const size_t no_null_ck_indexes[] = { 1, 3 };
+  ExpectNoNullCheck(no_null_ck_indexes);
+
+  static const bool eliminated[] = {
+      false, false, true, false, false
+  };
+  static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch");
+  for (size_t i = 0; i != arraysize(eliminated); ++i) {
+    bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop);
+    EXPECT_EQ(eliminated[i], actually_eliminated) << i;
+  }
+  // Check that the IGET uses the s_reg 0, v_reg 0, defined by mirs_[0].
+  ASSERT_EQ(1, mirs_[3].ssa_rep->num_uses);
+  EXPECT_EQ(0, mirs_[3].ssa_rep->uses[0]);
+  EXPECT_EQ(0u, mirs_[3].dalvikInsn.vB);
+}
+
+TEST_F(GvnDeadCodeEliminationTestSimple, Rename3) {
+  static const IFieldDef ifields[] = {
+      { 0u, 1u, 0u, false, kDexMemAccessWord },
+      { 1u, 1u, 1u, false, kDexMemAccessWord },
+  };
+  static const MIRDef mirs[] = {
+      DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u),
+      DEF_IGET(3, Instruction::IGET, 1u, 0u, 0u),
+      DEF_MOVE(3, Instruction::MOVE_OBJECT, 2u, 0u),
+      DEF_IGET(3, Instruction::IGET, 3u, 2u, 1u),
+  };
+
+  static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 0 };
+  PrepareSRegToVRegMap(sreg_to_vreg_map);
+
+  PrepareIFields(ifields);
+  PrepareMIRs(mirs);
+  PerformGVN_DCE();
+
+  ASSERT_EQ(arraysize(mirs), value_names_.size());
+  static const size_t diff_indexes[] = { 0, 1, 3 };
+  ExpectValueNamesNE(diff_indexes);
+  EXPECT_EQ(value_names_[0], value_names_[2]);
+
+  const size_t no_null_ck_indexes[] = { 1, 3 };
+  ExpectNoNullCheck(no_null_ck_indexes);
+
+  static const bool eliminated[] = {
+      false, false, true, false
+  };
+  static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch");
+  for (size_t i = 0; i != arraysize(eliminated); ++i) {
+    bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop);
+    EXPECT_EQ(eliminated[i], actually_eliminated) << i;
+  }
+  // Check that the NEW_INSTANCE defines the s_reg 2, v_reg 2, originally defined by the move.
+  ASSERT_EQ(1, mirs_[0].ssa_rep->num_defs);
+  EXPECT_EQ(2, mirs_[0].ssa_rep->defs[0]);
+  EXPECT_EQ(2u, mirs_[0].dalvikInsn.vA);
+  // Check that the first IGET is using the s_reg 2, v_reg 2.
+  ASSERT_EQ(1, mirs_[1].ssa_rep->num_uses);
+  EXPECT_EQ(2, mirs_[1].ssa_rep->uses[0]);
+  EXPECT_EQ(2u, mirs_[1].dalvikInsn.vB);
+}
+
+TEST_F(GvnDeadCodeEliminationTestSimple, Rename4) {
+  static const MIRDef mirs[] = {
+      DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u),
+      DEF_MOVE(3, Instruction::MOVE_OBJECT, 1u, 0u),
+      DEF_MOVE(3, Instruction::MOVE_OBJECT, 2u, 1u),
+      DEF_CONST_WIDE(3, Instruction::CONST_WIDE, 3u, 1000u),
+  };
+
+  static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 0, 1 /* high word */ };
+  PrepareSRegToVRegMap(sreg_to_vreg_map);
+
+  PrepareMIRs(mirs);
+  PerformGVN_DCE();
+
+  ASSERT_EQ(arraysize(mirs), value_names_.size());
+  static const size_t diff_indexes[] = { 0, 3 };
+  ExpectValueNamesNE(diff_indexes);
+  EXPECT_EQ(value_names_[0], value_names_[1]);
+  EXPECT_EQ(value_names_[0], value_names_[2]);
+
+  static const bool eliminated[] = {
+      false, true, true, false
+  };
+  static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch");
+  for (size_t i = 0; i != arraysize(eliminated); ++i) {
+    bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop);
+    EXPECT_EQ(eliminated[i], actually_eliminated) << i;
+  }
+  // Check that the NEW_INSTANCE defines the s_reg 2, v_reg 2, originally defined by the move 2u.
+  ASSERT_EQ(1, mirs_[0].ssa_rep->num_defs);
+  EXPECT_EQ(2, mirs_[0].ssa_rep->defs[0]);
+  EXPECT_EQ(2u, mirs_[0].dalvikInsn.vA);
+}
+
+TEST_F(GvnDeadCodeEliminationTestSimple, Rename5) {
+  static const IFieldDef ifields[] = {
+      { 0u, 1u, 0u, false, kDexMemAccessWord },
+  };
+  static const MIRDef mirs[] = {
+      DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u),
+      DEF_IGET(3, Instruction::IGET, 1u, 0u, 0u),
+      DEF_UNOP(3, Instruction::INT_TO_FLOAT, 2u, 1u),
+      DEF_MOVE(3, Instruction::MOVE_OBJECT, 3u, 0u),
+      DEF_MOVE(3, Instruction::MOVE_OBJECT, 4u, 3u),
+      DEF_CONST_WIDE(3, Instruction::CONST_WIDE, 5u, 1000u),
+  };
+
+  static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 1, 3, 0, 1 /* high word */ };
+  PrepareSRegToVRegMap(sreg_to_vreg_map);
+
+  PrepareIFields(ifields);
+  PrepareMIRs(mirs);
+  PerformGVN_DCE();
+
+  ASSERT_EQ(arraysize(mirs), value_names_.size());
+  static const size_t diff_indexes[] = { 0, 1, 2, 5 };
+  ExpectValueNamesNE(diff_indexes);
+  EXPECT_EQ(value_names_[0], value_names_[3]);
+  EXPECT_EQ(value_names_[0], value_names_[4]);
+
+  static const bool eliminated[] = {
+      false, false, false, true, true, false
+  };
+  static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch");
+  for (size_t i = 0; i != arraysize(eliminated); ++i) {
+    bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop);
+    EXPECT_EQ(eliminated[i], actually_eliminated) << i;
+  }
+  // Check that the NEW_INSTANCE defines the s_reg 4, v_reg 3, originally defined by the move 4u.
+  ASSERT_EQ(1, mirs_[0].ssa_rep->num_defs);
+  EXPECT_EQ(4, mirs_[0].ssa_rep->defs[0]);
+  EXPECT_EQ(3u, mirs_[0].dalvikInsn.vA);
+}
+
+TEST_F(GvnDeadCodeEliminationTestSimple, Rename6) {
+  static const MIRDef mirs[] = {
+      DEF_CONST_WIDE(3, Instruction::CONST_WIDE, 0u, 1000u),
+      DEF_MOVE_WIDE(3, Instruction::MOVE_WIDE, 2u, 0u),
+  };
+
+  static const int32_t sreg_to_vreg_map[] = { 0, 1 /* high word */, 1, 2 /* high word */ };
+  PrepareSRegToVRegMap(sreg_to_vreg_map);
+
+  PrepareMIRs(mirs);
+  PerformGVN_DCE();
+
+  ASSERT_EQ(arraysize(mirs), value_names_.size());
+  EXPECT_EQ(value_names_[0], value_names_[1]);
+
+  static const bool eliminated[] = {
+      false, true
+  };
+  static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch");
+  for (size_t i = 0; i != arraysize(eliminated); ++i) {
+    bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop);
+    EXPECT_EQ(eliminated[i], actually_eliminated) << i;
+  }
+  // Check that the CONST_WIDE defines the s_reg 2, v_reg 1, originally defined by the move 2u.
+  ASSERT_EQ(2, mirs_[0].ssa_rep->num_defs);
+  EXPECT_EQ(2, mirs_[0].ssa_rep->defs[0]);
+  EXPECT_EQ(3, mirs_[0].ssa_rep->defs[1]);
+  EXPECT_EQ(1u, mirs_[0].dalvikInsn.vA);
+}
+
+TEST_F(GvnDeadCodeEliminationTestSimple, Rename7) {
+  static const MIRDef mirs[] = {
+      DEF_CONST(3, Instruction::CONST, 0u, 1000u),
+      DEF_MOVE(3, Instruction::MOVE, 1u, 0u),
+      DEF_BINOP(3, Instruction::ADD_INT, 2u, 0u, 1u),
+  };
+
+  static const int32_t sreg_to_vreg_map[] = { 0, 1, 0 };
+  PrepareSRegToVRegMap(sreg_to_vreg_map);
+
+  PrepareMIRs(mirs);
+  PerformGVN_DCE();
+
+  ASSERT_EQ(arraysize(mirs), value_names_.size());
+  EXPECT_NE(value_names_[0], value_names_[2]);
+  EXPECT_EQ(value_names_[0], value_names_[1]);
+
+  static const bool eliminated[] = {
+      false, true, false
+  };
+  static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch");
+  for (size_t i = 0; i != arraysize(eliminated); ++i) {
+    bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop);
+    EXPECT_EQ(eliminated[i], actually_eliminated) << i;
+  }
+  // Check that the CONST defines the s_reg 1, v_reg 1, originally defined by the move 1u.
+  ASSERT_EQ(1, mirs_[0].ssa_rep->num_defs);
+  EXPECT_EQ(1, mirs_[0].ssa_rep->defs[0]);
+  EXPECT_EQ(1u, mirs_[0].dalvikInsn.vA);
+  // Check that the ADD_INT inputs are both s_reg1, vreg 1.
+  ASSERT_EQ(2, mirs_[2].ssa_rep->num_uses);
+  EXPECT_EQ(1, mirs_[2].ssa_rep->uses[0]);
+  EXPECT_EQ(1, mirs_[2].ssa_rep->uses[1]);
+  EXPECT_EQ(1u, mirs_[2].dalvikInsn.vB);
+  EXPECT_EQ(1u, mirs_[2].dalvikInsn.vC);
+}
+
+TEST_F(GvnDeadCodeEliminationTestSimple, Rename8) {
+  static const MIRDef mirs[] = {
+      DEF_CONST(3, Instruction::CONST, 0u, 1000u),
+      DEF_MOVE(3, Instruction::MOVE, 1u, 0u),
+      DEF_BINOP(3, Instruction::ADD_INT_2ADDR, 2u, 0u, 1u),
+  };
+
+  static const int32_t sreg_to_vreg_map[] = { 0, 1, 0 };
+  PrepareSRegToVRegMap(sreg_to_vreg_map);
+
+  PrepareMIRs(mirs);
+  PerformGVN_DCE();
+
+  ASSERT_EQ(arraysize(mirs), value_names_.size());
+  EXPECT_NE(value_names_[0], value_names_[2]);
+  EXPECT_EQ(value_names_[0], value_names_[1]);
+
+  static const bool eliminated[] = {
+      false, true, false
+  };
+  static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch");
+  for (size_t i = 0; i != arraysize(eliminated); ++i) {
+    bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop);
+    EXPECT_EQ(eliminated[i], actually_eliminated) << i;
+  }
+  // Check that the CONST defines the s_reg 1, v_reg 1, originally defined by the move 1u.
+  ASSERT_EQ(1, mirs_[0].ssa_rep->num_defs);
+  EXPECT_EQ(1, mirs_[0].ssa_rep->defs[0]);
+  EXPECT_EQ(1u, mirs_[0].dalvikInsn.vA);
+  // Check that the ADD_INT_2ADDR was replaced by ADD_INT and inputs are both s_reg 1, vreg 1.
+  EXPECT_EQ(Instruction::ADD_INT, mirs_[2].dalvikInsn.opcode);
+  ASSERT_EQ(2, mirs_[2].ssa_rep->num_uses);
+  EXPECT_EQ(1, mirs_[2].ssa_rep->uses[0]);
+  EXPECT_EQ(1, mirs_[2].ssa_rep->uses[1]);
+  EXPECT_EQ(1u, mirs_[2].dalvikInsn.vB);
+  EXPECT_EQ(1u, mirs_[2].dalvikInsn.vC);
+}
+
+TEST_F(GvnDeadCodeEliminationTestSimple, Rename9) {
+  static const MIRDef mirs[] = {
+      DEF_CONST(3, Instruction::CONST, 0u, 1000u),
+      DEF_BINOP(3, Instruction::ADD_INT_2ADDR, 1u, 0u, 0u),
+      DEF_MOVE(3, Instruction::MOVE, 2u, 1u),
+      DEF_CONST(3, Instruction::CONST, 3u, 3000u),
+  };
+
+  static const int32_t sreg_to_vreg_map[] = { 0, 0, 1, 0 };
+  PrepareSRegToVRegMap(sreg_to_vreg_map);
+
+  PrepareMIRs(mirs);
+  PerformGVN_DCE();
+
+  ASSERT_EQ(arraysize(mirs), value_names_.size());
+  static const size_t diff_indexes[] = { 0, 1, 3 };
+  ExpectValueNamesNE(diff_indexes);
+  EXPECT_EQ(value_names_[1], value_names_[2]);
+
+  static const bool eliminated[] = {
+      false, false, true, false
+  };
+  static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch");
+  for (size_t i = 0; i != arraysize(eliminated); ++i) {
+    bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop);
+    EXPECT_EQ(eliminated[i], actually_eliminated) << i;
+  }
+  // Check that the ADD_INT_2ADDR was replaced by ADD_INT and output is in s_reg 2, vreg 1.
+  EXPECT_EQ(Instruction::ADD_INT, mirs_[1].dalvikInsn.opcode);
+  ASSERT_EQ(2, mirs_[1].ssa_rep->num_uses);
+  EXPECT_EQ(0, mirs_[1].ssa_rep->uses[0]);
+  EXPECT_EQ(0, mirs_[1].ssa_rep->uses[1]);
+  EXPECT_EQ(0u, mirs_[1].dalvikInsn.vB);
+  EXPECT_EQ(0u, mirs_[1].dalvikInsn.vC);
+  ASSERT_EQ(1, mirs_[1].ssa_rep->num_defs);
+  EXPECT_EQ(2, mirs_[1].ssa_rep->defs[0]);
+  EXPECT_EQ(1u, mirs_[1].dalvikInsn.vA);
+}
+
+TEST_F(GvnDeadCodeEliminationTestSimple, NoRename1) {
+  static const IFieldDef ifields[] = {
+      { 0u, 1u, 0u, false, kDexMemAccessWord },
+      { 1u, 1u, 1u, false, kDexMemAccessWord },
+  };
+  static const MIRDef mirs[] = {
+      DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u),
+      DEF_IGET(3, Instruction::IGET, 1u, 0u, 0u),
+      DEF_UNOP(3, Instruction::INT_TO_FLOAT, 2u, 1u),
+      DEF_MOVE(3, Instruction::MOVE_OBJECT, 3u, 0u),
+      DEF_CONST(3, Instruction::CONST, 4u, 1000),
+      DEF_IGET(3, Instruction::IGET, 5u, 3u, 1u),
+  };
+
+  static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 1, 0, 1 };
+  PrepareSRegToVRegMap(sreg_to_vreg_map);
+
+  PrepareIFields(ifields);
+  PrepareMIRs(mirs);
+  PerformGVN_DCE();
+
+  ASSERT_EQ(arraysize(mirs), value_names_.size());
+  static const size_t diff_indexes[] = { 0, 1, 2, 4, 5 };
+  ExpectValueNamesNE(diff_indexes);
+  EXPECT_EQ(value_names_[0], value_names_[3]);
+
+  const size_t no_null_ck_indexes[] = { 1, 5 };
+  ExpectNoNullCheck(no_null_ck_indexes);
+
+  static const bool eliminated[] = {
+      false, false, false, false, false, false
+  };
+  static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch");
+  for (size_t i = 0; i != arraysize(eliminated); ++i) {
+    bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop);
+    EXPECT_EQ(eliminated[i], actually_eliminated) << i;
+  }
+}
+
+TEST_F(GvnDeadCodeEliminationTestSimple, NoRename2) {
+  static const IFieldDef ifields[] = {
+      { 0u, 1u, 0u, false, kDexMemAccessWord },
+      { 1u, 1u, 1u, false, kDexMemAccessWord },
+  };
+  static const MIRDef mirs[] = {
+      DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u),
+      DEF_IGET(3, Instruction::IGET, 1u, 0u, 0u),
+      DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 2u),
+      DEF_MOVE(3, Instruction::MOVE_OBJECT, 3u, 0u),
+      DEF_CONST(3, Instruction::CONST, 4u, 1000),
+      DEF_IGET(3, Instruction::IGET, 5u, 3u, 1u),
+      DEF_CONST(3, Instruction::CONST, 6u, 2000),
+  };
+
+  static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 2, 0, 3, 2 };
+  PrepareSRegToVRegMap(sreg_to_vreg_map);
+
+  PrepareIFields(ifields);
+  PrepareMIRs(mirs);
+  PerformGVN_DCE();
+
+  ASSERT_EQ(arraysize(mirs), value_names_.size());
+  static const size_t diff_indexes[] = { 0, 1, 2, 4, 5, 6 };
+  ExpectValueNamesNE(diff_indexes);
+  EXPECT_EQ(value_names_[0], value_names_[3]);
+
+  const size_t no_null_ck_indexes[] = { 1, 5 };
+  ExpectNoNullCheck(no_null_ck_indexes);
+
+  static const bool eliminated[] = {
+      false, false, false, false, false, false, false
+  };
+  static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch");
+  for (size_t i = 0; i != arraysize(eliminated); ++i) {
+    bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop);
+    EXPECT_EQ(eliminated[i], actually_eliminated) << i;
+  }
+}
+
+TEST_F(GvnDeadCodeEliminationTestSimple, NoRename3) {
+  static const IFieldDef ifields[] = {
+      { 0u, 1u, 0u, false, kDexMemAccessWord },
+      { 1u, 1u, 1u, false, kDexMemAccessWord },
+      { 2u, 1u, 2u, false, kDexMemAccessWord },
+  };
+  static const MIRDef mirs[] = {
+      DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u),
+      DEF_IGET(3, Instruction::IGET, 1u, 0u, 0u),
+      DEF_IGET(3, Instruction::IGET, 2u, 0u, 2u),
+      DEF_BINOP(3, Instruction::ADD_INT, 3u, 1u, 2u),
+      DEF_MOVE(3, Instruction::MOVE_OBJECT, 4u, 0u),
+      DEF_IGET(3, Instruction::IGET, 5u, 4u, 1u),
+  };
+
+  static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 3, 2, 0 };
+  PrepareSRegToVRegMap(sreg_to_vreg_map);
+
+  PrepareIFields(ifields);
+  PrepareMIRs(mirs);
+  PerformGVN_DCE();
+
+  ASSERT_EQ(arraysize(mirs), value_names_.size());
+  static const size_t diff_indexes[] = { 0, 1, 2, 3, 5 };
+  ExpectValueNamesNE(diff_indexes);
+  EXPECT_EQ(value_names_[0], value_names_[4]);
+
+  const size_t no_null_ck_indexes[] = { 1, 2, 5 };
+  ExpectNoNullCheck(no_null_ck_indexes);
+
+  static const bool eliminated[] = {
+      false, false, false, false, false, false
+  };
+  static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch");
+  for (size_t i = 0; i != arraysize(eliminated); ++i) {
+    bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop);
+    EXPECT_EQ(eliminated[i], actually_eliminated) << i;
+  }
+}
+
+TEST_F(GvnDeadCodeEliminationTestSimple, Simple1) {
+  static const IFieldDef ifields[] = {
+      { 0u, 1u, 0u, false, kDexMemAccessObject },
+      { 1u, 1u, 1u, false, kDexMemAccessObject },
+      { 2u, 1u, 2u, false, kDexMemAccessWord },
+  };
+  static const MIRDef mirs[] = {
+      DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u),
+      DEF_IGET(3, Instruction::IGET_OBJECT, 1u, 0u, 0u),
+      DEF_IGET(3, Instruction::IGET_OBJECT, 2u, 1u, 1u),
+      DEF_IGET(3, Instruction::IGET, 3u, 2u, 2u),
+      DEF_IGET(3, Instruction::IGET_OBJECT, 4u, 0u, 0u),
+      DEF_IGET(3, Instruction::IGET_OBJECT, 5u, 4u, 1u),
+  };
+
+  static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 3, 1, 2 };
+  PrepareSRegToVRegMap(sreg_to_vreg_map);
+
+  PrepareIFields(ifields);
+  PrepareMIRs(mirs);
+  PerformGVN_DCE();
+
+  ASSERT_EQ(arraysize(mirs), value_names_.size());
+  EXPECT_NE(value_names_[0], value_names_[1]);
+  EXPECT_NE(value_names_[0], value_names_[2]);
+  EXPECT_NE(value_names_[0], value_names_[3]);
+  EXPECT_NE(value_names_[1], value_names_[2]);
+  EXPECT_NE(value_names_[1], value_names_[3]);
+  EXPECT_NE(value_names_[2], value_names_[3]);
+  EXPECT_EQ(value_names_[1], value_names_[4]);
+  EXPECT_EQ(value_names_[2], value_names_[5]);
+
+  EXPECT_EQ(MIR_IGNORE_NULL_CHECK, mirs_[4].optimization_flags & MIR_IGNORE_NULL_CHECK);
+  EXPECT_EQ(MIR_IGNORE_NULL_CHECK, mirs_[5].optimization_flags & MIR_IGNORE_NULL_CHECK);
+
+  static const bool eliminated[] = {
+      false, false, false, false, true, true
+  };
+  static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch");
+  for (size_t i = 0; i != arraysize(eliminated); ++i) {
+    bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop);
+    EXPECT_EQ(eliminated[i], actually_eliminated) << i;
+  }
+  // Check that the sregs have been renamed correctly.
+  ASSERT_EQ(1, mirs_[1].ssa_rep->num_defs);
+  EXPECT_EQ(4, mirs_[1].ssa_rep->defs[0]);
+  ASSERT_EQ(1, mirs_[1].ssa_rep->num_uses);
+  EXPECT_EQ(0, mirs_[1].ssa_rep->uses[0]);
+  ASSERT_EQ(1, mirs_[2].ssa_rep->num_defs);
+  EXPECT_EQ(5, mirs_[2].ssa_rep->defs[0]);
+  ASSERT_EQ(1, mirs_[2].ssa_rep->num_uses);
+  EXPECT_EQ(4, mirs_[2].ssa_rep->uses[0]);
+  ASSERT_EQ(1, mirs_[3].ssa_rep->num_defs);
+  EXPECT_EQ(3, mirs_[3].ssa_rep->defs[0]);
+  ASSERT_EQ(1, mirs_[3].ssa_rep->num_uses);
+  EXPECT_EQ(5, mirs_[3].ssa_rep->uses[0]);
+}
+
+TEST_F(GvnDeadCodeEliminationTestSimple, Simple2) {
+  static const IFieldDef ifields[] = {
+      { 0u, 1u, 0u, false, kDexMemAccessWord },
+  };
+  static const MIRDef mirs[] = {
+      DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u),
+      DEF_CONST(3, Instruction::CONST, 1u, 1000),
+      DEF_IGET(3, Instruction::IGET, 2u, 0u, 0u),
+      DEF_BINOP(3, Instruction::ADD_INT_2ADDR, 3u, 2u, 1u),
+      DEF_UNOP(3, Instruction::INT_TO_FLOAT, 4u, 3u),
+      DEF_IGET(3, Instruction::IGET, 5u, 0u, 0u),
+      DEF_BINOP(3, Instruction::ADD_INT_2ADDR, 6u, 5u, 1u),
+  };
+
+  static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 2, 3, 2, 2 };
+  PrepareSRegToVRegMap(sreg_to_vreg_map);
+
+  PrepareIFields(ifields);
+  PrepareMIRs(mirs);
+  PerformGVN_DCE();
+
+  ASSERT_EQ(arraysize(mirs), value_names_.size());
+  static const size_t diff_indexes[] = { 0, 1, 2, 3 };
+  ExpectValueNamesNE(diff_indexes);
+  EXPECT_EQ(value_names_[2], value_names_[5]);
+  EXPECT_EQ(value_names_[3], value_names_[6]);
+
+  const size_t no_null_ck_indexes[] = { 2, 5 };
+  ExpectNoNullCheck(no_null_ck_indexes);
+
+  static const bool eliminated[] = {
+      false, false, false, false, false, true, true
+  };
+  static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch");
+  for (size_t i = 0; i != arraysize(eliminated); ++i) {
+    bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop);
+    EXPECT_EQ(eliminated[i], actually_eliminated) << i;
+  }
+  // Check that the sregs have been renamed correctly.
+  ASSERT_EQ(1, mirs_[3].ssa_rep->num_defs);
+  EXPECT_EQ(6, mirs_[3].ssa_rep->defs[0]);
+  ASSERT_EQ(2, mirs_[3].ssa_rep->num_uses);
+  EXPECT_EQ(2, mirs_[3].ssa_rep->uses[0]);
+  EXPECT_EQ(1, mirs_[3].ssa_rep->uses[1]);
+  ASSERT_EQ(1, mirs_[4].ssa_rep->num_defs);
+  EXPECT_EQ(4, mirs_[4].ssa_rep->defs[0]);
+  ASSERT_EQ(1, mirs_[4].ssa_rep->num_uses);
+  EXPECT_EQ(6, mirs_[4].ssa_rep->uses[0]);
+}
+
+TEST_F(GvnDeadCodeEliminationTestSimple, Simple3) {
+  static const IFieldDef ifields[] = {
+      { 0u, 1u, 0u, false, kDexMemAccessWord },
+  };
+  static const MIRDef mirs[] = {
+      DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u),
+      DEF_CONST(3, Instruction::CONST, 1u, 1000),
+      DEF_CONST(3, Instruction::CONST, 2u, 2000),
+      DEF_CONST(3, Instruction::CONST, 3u, 3000),
+      DEF_IGET(3, Instruction::IGET, 4u, 0u, 0u),
+      DEF_BINOP(3, Instruction::ADD_INT, 5u, 4u, 1u),
+      DEF_BINOP(3, Instruction::MUL_INT, 6u, 5u, 2u),
+      DEF_BINOP(3, Instruction::SUB_INT, 7u, 6u, 3u),
+      DEF_UNOP(3, Instruction::INT_TO_FLOAT, 8u, 7u),
+      DEF_IGET(3, Instruction::IGET, 9u, 0u, 0u),
+      DEF_BINOP(3, Instruction::ADD_INT, 10u, 9u, 1u),
+      DEF_BINOP(3, Instruction::MUL_INT, 11u, 10u, 2u),  // Simple elimination of ADD+MUL
+      DEF_BINOP(3, Instruction::SUB_INT, 12u, 11u, 3u),  // allows simple elimination of IGET+SUB.
+  };
+
+  static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 3, 4, 5, 5, 4, 6, 4, 5, 5, 4 };
+  PrepareSRegToVRegMap(sreg_to_vreg_map);
+
+  PrepareIFields(ifields);
+  PrepareMIRs(mirs);
+  PerformGVN_DCE();
+
+  ASSERT_EQ(arraysize(mirs), value_names_.size());
+  static const size_t diff_indexes[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
+  ExpectValueNamesNE(diff_indexes);
+  EXPECT_EQ(value_names_[4], value_names_[9]);
+  EXPECT_EQ(value_names_[5], value_names_[10]);
+  EXPECT_EQ(value_names_[6], value_names_[11]);
+  EXPECT_EQ(value_names_[7], value_names_[12]);
+
+  const size_t no_null_ck_indexes[] = { 4, 9 };
+  ExpectNoNullCheck(no_null_ck_indexes);
+
+  static const bool eliminated[] = {
+      false, false, false, false, false, false, false, false, false, true, true, true, true
+  };
+  static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch");
+  for (size_t i = 0; i != arraysize(eliminated); ++i) {
+    bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop);
+    EXPECT_EQ(eliminated[i], actually_eliminated) << i;
+  }
+  // Check that the sregs have been renamed correctly.
+  ASSERT_EQ(1, mirs_[6].ssa_rep->num_defs);
+  EXPECT_EQ(11, mirs_[6].ssa_rep->defs[0]);  // 6 -> 11
+  ASSERT_EQ(2, mirs_[6].ssa_rep->num_uses);
+  EXPECT_EQ(5, mirs_[6].ssa_rep->uses[0]);
+  EXPECT_EQ(2, mirs_[6].ssa_rep->uses[1]);
+  ASSERT_EQ(1, mirs_[7].ssa_rep->num_defs);
+  EXPECT_EQ(12, mirs_[7].ssa_rep->defs[0]);  // 7 -> 12
+  ASSERT_EQ(2, mirs_[7].ssa_rep->num_uses);
+  EXPECT_EQ(11, mirs_[7].ssa_rep->uses[0]);  // 6 -> 11
+  EXPECT_EQ(3, mirs_[7].ssa_rep->uses[1]);
+  ASSERT_EQ(1, mirs_[8].ssa_rep->num_defs);
+  EXPECT_EQ(8, mirs_[8].ssa_rep->defs[0]);
+  ASSERT_EQ(1, mirs_[8].ssa_rep->num_uses);
+  EXPECT_EQ(12, mirs_[8].ssa_rep->uses[0]);  // 7 -> 12
+}
+
+TEST_F(GvnDeadCodeEliminationTestSimple, Simple4) {
+  static const IFieldDef ifields[] = {
+      { 0u, 1u, 0u, false, kDexMemAccessWord },
+  };
+  static const MIRDef mirs[] = {
+      DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u),
+      DEF_CONST_WIDE(3, Instruction::CONST_WIDE, 1u, INT64_C(1)),
+      DEF_BINOP(3, Instruction::LONG_TO_FLOAT, 3u, 1u, 2u),
+      DEF_IGET(3, Instruction::IGET, 4u, 0u, 0u),
+      DEF_UNOP(3, Instruction::INT_TO_FLOAT, 5u, 4u),
+      DEF_CONST_WIDE(3, Instruction::CONST_WIDE, 6u, INT64_C(1)),
+      DEF_BINOP(3, Instruction::LONG_TO_FLOAT, 8u, 6u, 7u),
+      DEF_IGET(3, Instruction::IGET, 9u, 0u, 0u),
+  };
+
+  static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 1, 2, 3, 1, 2, 1, 2 };
+  PrepareSRegToVRegMap(sreg_to_vreg_map);
+
+  PrepareIFields(ifields);
+  PrepareMIRs(mirs);
+  PerformGVN_DCE();
+
+  ASSERT_EQ(arraysize(mirs), value_names_.size());
+  static const size_t diff_indexes[] = { 0, 1, 2, 3, 4 };
+  ExpectValueNamesNE(diff_indexes);
+  EXPECT_EQ(value_names_[1], value_names_[5]);
+  EXPECT_EQ(value_names_[2], value_names_[6]);
+  EXPECT_EQ(value_names_[3], value_names_[7]);
+
+  const size_t no_null_ck_indexes[] = { 3, 7 };
+  ExpectNoNullCheck(no_null_ck_indexes);
+
+  static const bool eliminated[] = {
+      // Simple elimination of CONST_WIDE+LONG_TO_FLOAT allows simple eliminatiion of IGET.
+      false, false, false, false, false, true, true, true
+  };
+  static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch");
+  for (size_t i = 0; i != arraysize(eliminated); ++i) {
+    bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop);
+    EXPECT_EQ(eliminated[i], actually_eliminated) << i;
+  }
+  // Check that the sregs have been renamed correctly.
+  ASSERT_EQ(1, mirs_[2].ssa_rep->num_defs);
+  EXPECT_EQ(8, mirs_[2].ssa_rep->defs[0]);   // 3 -> 8
+  ASSERT_EQ(2, mirs_[2].ssa_rep->num_uses);
+  EXPECT_EQ(1, mirs_[2].ssa_rep->uses[0]);
+  EXPECT_EQ(2, mirs_[2].ssa_rep->uses[1]);
+  ASSERT_EQ(1, mirs_[3].ssa_rep->num_defs);
+  EXPECT_EQ(9, mirs_[3].ssa_rep->defs[0]);   // 4 -> 9
+  ASSERT_EQ(1, mirs_[3].ssa_rep->num_uses);
+  EXPECT_EQ(0, mirs_[3].ssa_rep->uses[0]);
+  ASSERT_EQ(1, mirs_[4].ssa_rep->num_defs);
+  EXPECT_EQ(5, mirs_[4].ssa_rep->defs[0]);
+  ASSERT_EQ(1, mirs_[4].ssa_rep->num_uses);
+  EXPECT_EQ(9, mirs_[4].ssa_rep->uses[0]);   // 4 -> 9
+}
+
+TEST_F(GvnDeadCodeEliminationTestSimple, KillChain1) {
+  static const IFieldDef ifields[] = {
+      { 0u, 1u, 0u, false, kDexMemAccessWord },
+  };
+  static const MIRDef mirs[] = {
+      DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u),
+      DEF_CONST(3, Instruction::CONST, 1u, 1000),
+      DEF_CONST(3, Instruction::CONST, 2u, 2000),
+      DEF_CONST(3, Instruction::CONST, 3u, 3000),
+      DEF_IGET(3, Instruction::IGET, 4u, 0u, 0u),
+      DEF_BINOP(3, Instruction::ADD_INT, 5u, 4u, 1u),
+      DEF_BINOP(3, Instruction::MUL_INT, 6u, 5u, 2u),
+      DEF_BINOP(3, Instruction::SUB_INT, 7u, 6u, 3u),
+      DEF_UNOP(3, Instruction::INT_TO_FLOAT, 8u, 7u),
+      DEF_IGET(3, Instruction::IGET, 9u, 0u, 0u),
+      DEF_BINOP(3, Instruction::ADD_INT, 10u, 9u, 1u),
+      DEF_BINOP(3, Instruction::MUL_INT, 11u, 10u, 2u),
+      DEF_BINOP(3, Instruction::SUB_INT, 12u, 11u, 3u),
+  };
+
+  static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 3, 4, 5, 4, 5, 6, 4, 5, 4, 5 };
+  PrepareSRegToVRegMap(sreg_to_vreg_map);
+
+  PrepareIFields(ifields);
+  PrepareMIRs(mirs);
+  PerformGVN_DCE();
+
+  ASSERT_EQ(arraysize(mirs), value_names_.size());
+  static const size_t diff_indexes[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
+  ExpectValueNamesNE(diff_indexes);
+  EXPECT_EQ(value_names_[4], value_names_[9]);
+  EXPECT_EQ(value_names_[5], value_names_[10]);
+  EXPECT_EQ(value_names_[6], value_names_[11]);
+  EXPECT_EQ(value_names_[7], value_names_[12]);
+
+  const size_t no_null_ck_indexes[] = { 4, 9 };
+  ExpectNoNullCheck(no_null_ck_indexes);
+
+  static const bool eliminated[] = {
+      false, false, false, false, false, false, false, false, false, true, true, true, true
+  };
+  static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch");
+  for (size_t i = 0; i != arraysize(eliminated); ++i) {
+    bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop);
+    EXPECT_EQ(eliminated[i], actually_eliminated) << i;
+  }
+  // Check that the sregs have been renamed correctly.
+  ASSERT_EQ(1, mirs_[6].ssa_rep->num_defs);
+  EXPECT_EQ(11, mirs_[6].ssa_rep->defs[0]);  // 6 -> 11
+  ASSERT_EQ(2, mirs_[6].ssa_rep->num_uses);
+  EXPECT_EQ(5, mirs_[6].ssa_rep->uses[0]);
+  EXPECT_EQ(2, mirs_[6].ssa_rep->uses[1]);
+  ASSERT_EQ(1, mirs_[7].ssa_rep->num_defs);
+  EXPECT_EQ(12, mirs_[7].ssa_rep->defs[0]);  // 7 -> 12
+  ASSERT_EQ(2, mirs_[7].ssa_rep->num_uses);
+  EXPECT_EQ(11, mirs_[7].ssa_rep->uses[0]);  // 6 -> 11
+  EXPECT_EQ(3, mirs_[7].ssa_rep->uses[1]);
+  ASSERT_EQ(1, mirs_[8].ssa_rep->num_defs);
+  EXPECT_EQ(8, mirs_[8].ssa_rep->defs[0]);
+  ASSERT_EQ(1, mirs_[8].ssa_rep->num_uses);
+  EXPECT_EQ(12, mirs_[8].ssa_rep->uses[0]);   // 7 -> 12
+}
+
+TEST_F(GvnDeadCodeEliminationTestSimple, KillChain2) {
+  static const IFieldDef ifields[] = {
+      { 0u, 1u, 0u, false, kDexMemAccessWord },
+  };
+  static const MIRDef mirs[] = {
+      DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u),
+      DEF_CONST(3, Instruction::CONST, 1u, 1000),
+      DEF_CONST(3, Instruction::CONST, 2u, 2000),
+      DEF_CONST(3, Instruction::CONST, 3u, 3000),
+      DEF_IGET(3, Instruction::IGET, 4u, 0u, 0u),
+      DEF_BINOP(3, Instruction::ADD_INT, 5u, 4u, 1u),
+      DEF_BINOP(3, Instruction::MUL_INT, 6u, 5u, 2u),
+      DEF_BINOP(3, Instruction::SUB_INT, 7u, 6u, 3u),
+      DEF_UNOP(3, Instruction::INT_TO_FLOAT, 8u, 7u),
+      DEF_IGET(3, Instruction::IGET, 9u, 0u, 0u),
+      DEF_BINOP(3, Instruction::ADD_INT, 10u, 9u, 1u),
+      DEF_BINOP(3, Instruction::MUL_INT, 11u, 10u, 2u),
+      DEF_BINOP(3, Instruction::SUB_INT, 12u, 11u, 3u),
+      DEF_CONST(3, Instruction::CONST, 13u, 4000),
+  };
+
+  static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 3, 4, 5, 5, 4, 6, 4, 7, 7, 4, 7 };
+  PrepareSRegToVRegMap(sreg_to_vreg_map);
+
+  PrepareIFields(ifields);
+  PrepareMIRs(mirs);
+  PerformGVN_DCE();
+
+  ASSERT_EQ(arraysize(mirs), value_names_.size());
+  static const size_t diff_indexes[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 13 };
+  ExpectValueNamesNE(diff_indexes);
+  EXPECT_EQ(value_names_[4], value_names_[9]);
+  EXPECT_EQ(value_names_[5], value_names_[10]);
+  EXPECT_EQ(value_names_[6], value_names_[11]);
+  EXPECT_EQ(value_names_[7], value_names_[12]);
+
+  const size_t no_null_ck_indexes[] = { 4, 9 };
+  ExpectNoNullCheck(no_null_ck_indexes);
+
+  static const bool eliminated[] = {
+      false, false, false, false, false, false, false, false, false, true, true, true, true, false
+  };
+  static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch");
+  for (size_t i = 0; i != arraysize(eliminated); ++i) {
+    bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop);
+    EXPECT_EQ(eliminated[i], actually_eliminated) << i;
+  }
+  // Check that the sregs have been renamed correctly.
+  ASSERT_EQ(1, mirs_[7].ssa_rep->num_defs);
+  EXPECT_EQ(12, mirs_[7].ssa_rep->defs[0]);  // 7 -> 12
+  ASSERT_EQ(2, mirs_[7].ssa_rep->num_uses);
+  EXPECT_EQ(6, mirs_[7].ssa_rep->uses[0]);
+  EXPECT_EQ(3, mirs_[7].ssa_rep->uses[1]);
+  ASSERT_EQ(1, mirs_[8].ssa_rep->num_defs);
+  EXPECT_EQ(8, mirs_[8].ssa_rep->defs[0]);
+  ASSERT_EQ(1, mirs_[8].ssa_rep->num_uses);
+  EXPECT_EQ(12, mirs_[8].ssa_rep->uses[0]);   // 7 -> 12
+}
+
+TEST_F(GvnDeadCodeEliminationTestSimple, KillChain3) {
+  static const IFieldDef ifields[] = {
+      { 0u, 1u, 0u, false, kDexMemAccessWord },
+  };
+  static const MIRDef mirs[] = {
+      DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u),
+      DEF_CONST(3, Instruction::CONST, 1u, 1000),
+      DEF_CONST(3, Instruction::CONST, 2u, 2000),
+      DEF_CONST(3, Instruction::CONST, 3u, 3000),
+      DEF_IGET(3, Instruction::IGET, 4u, 0u, 0u),
+      DEF_BINOP(3, Instruction::ADD_INT, 5u, 4u, 1u),
+      DEF_BINOP(3, Instruction::MUL_INT, 6u, 5u, 2u),
+      DEF_BINOP(3, Instruction::SUB_INT, 7u, 6u, 3u),
+      DEF_UNOP(3, Instruction::INT_TO_FLOAT, 8u, 7u),
+      DEF_IGET(3, Instruction::IGET, 9u, 0u, 0u),
+      DEF_BINOP(3, Instruction::ADD_INT, 10u, 9u, 1u),
+      DEF_BINOP(3, Instruction::MUL_INT, 11u, 10u, 2u),
+      DEF_CONST(3, Instruction::CONST, 12u, 4000),
+      DEF_BINOP(3, Instruction::SUB_INT, 13u, 11u, 3u),
+  };
+
+  static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 3, 4, 5, 5, 4, 6, 4, 7, 4, 7, 4 };
+  PrepareSRegToVRegMap(sreg_to_vreg_map);
+
+  PrepareIFields(ifields);
+  PrepareMIRs(mirs);
+  PerformGVN_DCE();
+
+  ASSERT_EQ(arraysize(mirs), value_names_.size());
+  static const size_t diff_indexes[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 12 };
+  ExpectValueNamesNE(diff_indexes);
+  EXPECT_EQ(value_names_[4], value_names_[9]);
+  EXPECT_EQ(value_names_[5], value_names_[10]);
+  EXPECT_EQ(value_names_[6], value_names_[11]);
+  EXPECT_EQ(value_names_[7], value_names_[13]);
+
+  const size_t no_null_ck_indexes[] = { 4, 9 };
+  ExpectNoNullCheck(no_null_ck_indexes);
+
+  static const bool eliminated[] = {
+      false, false, false, false, false, false, false, false, false, true, true, true, false, true
+  };
+  static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch");
+  for (size_t i = 0; i != arraysize(eliminated); ++i) {
+    bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop);
+    EXPECT_EQ(eliminated[i], actually_eliminated) << i;
+  }
+  // Check that the sregs have been renamed correctly.
+  ASSERT_EQ(1, mirs_[7].ssa_rep->num_defs);
+  EXPECT_EQ(13, mirs_[7].ssa_rep->defs[0]);  // 7 -> 13
+  ASSERT_EQ(2, mirs_[7].ssa_rep->num_uses);
+  EXPECT_EQ(6, mirs_[7].ssa_rep->uses[0]);
+  EXPECT_EQ(3, mirs_[7].ssa_rep->uses[1]);
+  ASSERT_EQ(1, mirs_[8].ssa_rep->num_defs);
+  EXPECT_EQ(8, mirs_[8].ssa_rep->defs[0]);
+  ASSERT_EQ(1, mirs_[8].ssa_rep->num_uses);
+  EXPECT_EQ(13, mirs_[8].ssa_rep->uses[0]);   // 7 -> 13
+}
+
+TEST_F(GvnDeadCodeEliminationTestSimple, KeepChain1) {
+  // KillChain2 without the final CONST.
+  static const IFieldDef ifields[] = {
+      { 0u, 1u, 0u, false, kDexMemAccessWord },
+  };
+  static const MIRDef mirs[] = {
+      DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u),
+      DEF_CONST(3, Instruction::CONST, 1u, 1000),
+      DEF_CONST(3, Instruction::CONST, 2u, 2000),
+      DEF_CONST(3, Instruction::CONST, 3u, 3000),
+      DEF_IGET(3, Instruction::IGET, 4u, 0u, 0u),
+      DEF_BINOP(3, Instruction::ADD_INT, 5u, 4u, 1u),
+      DEF_BINOP(3, Instruction::MUL_INT, 6u, 5u, 2u),
+      DEF_BINOP(3, Instruction::SUB_INT, 7u, 6u, 3u),
+      DEF_UNOP(3, Instruction::INT_TO_FLOAT, 8u, 7u),
+      DEF_IGET(3, Instruction::IGET, 9u, 0u, 0u),
+      DEF_BINOP(3, Instruction::ADD_INT, 10u, 9u, 1u),
+      DEF_BINOP(3, Instruction::MUL_INT, 11u, 10u, 2u),
+      DEF_BINOP(3, Instruction::SUB_INT, 12u, 11u, 3u),
+  };
+
+  static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 3, 4, 5, 5, 4, 6, 4, 7, 7, 4 };
+  PrepareSRegToVRegMap(sreg_to_vreg_map);
+
+  PrepareIFields(ifields);
+  PrepareMIRs(mirs);
+  PerformGVN_DCE();
+
+  ASSERT_EQ(arraysize(mirs), value_names_.size());
+  static const size_t diff_indexes[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
+  ExpectValueNamesNE(diff_indexes);
+  EXPECT_EQ(value_names_[4], value_names_[9]);
+  EXPECT_EQ(value_names_[5], value_names_[10]);
+  EXPECT_EQ(value_names_[6], value_names_[11]);
+  EXPECT_EQ(value_names_[7], value_names_[12]);
+
+  const size_t no_null_ck_indexes[] = { 4, 9 };
+  ExpectNoNullCheck(no_null_ck_indexes);
+
+  static const bool eliminated[] = {
+      false, false, false, false, false, false, false, false, false, false, false, false, false
+  };
+  static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch");
+  for (size_t i = 0; i != arraysize(eliminated); ++i) {
+    bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop);
+    EXPECT_EQ(eliminated[i], actually_eliminated) << i;
+  }
+}
+
+TEST_F(GvnDeadCodeEliminationTestSimple, KeepChain2) {
+  // KillChain1 with MIRs in the middle of the chain.
+  static const IFieldDef ifields[] = {
+      { 0u, 1u, 0u, false, kDexMemAccessWord },
+  };
+  static const MIRDef mirs[] = {
+      DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u),
+      DEF_CONST(3, Instruction::CONST, 1u, 1000),
+      DEF_CONST(3, Instruction::CONST, 2u, 2000),
+      DEF_CONST(3, Instruction::CONST, 3u, 3000),
+      DEF_IGET(3, Instruction::IGET, 4u, 0u, 0u),
+      DEF_BINOP(3, Instruction::ADD_INT, 5u, 4u, 1u),
+      DEF_BINOP(3, Instruction::MUL_INT, 6u, 5u, 2u),
+      DEF_BINOP(3, Instruction::SUB_INT, 7u, 6u, 3u),
+      DEF_UNOP(3, Instruction::INT_TO_FLOAT, 8u, 7u),
+      DEF_IGET(3, Instruction::IGET, 9u, 0u, 0u),
+      DEF_BINOP(3, Instruction::ADD_INT, 10u, 9u, 1u),
+      DEF_CONST(3, Instruction::CONST, 11u, 4000),
+      DEF_UNOP(3, Instruction::INT_TO_FLOAT, 12u, 11u),
+      DEF_BINOP(3, Instruction::MUL_INT, 13u, 10u, 2u),
+      DEF_BINOP(3, Instruction::SUB_INT, 14u, 13u, 3u),
+  };
+
+  static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 3, 4, 5, 4, 5, 6, 4, 5, 4, 7, 4, 5 };
+  PrepareSRegToVRegMap(sreg_to_vreg_map);
+
+  PrepareIFields(ifields);
+  PrepareMIRs(mirs);
+  PerformGVN_DCE();
+
+  ASSERT_EQ(arraysize(mirs), value_names_.size());
+  static const size_t diff_indexes[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
+  ExpectValueNamesNE(diff_indexes);
+  EXPECT_EQ(value_names_[4], value_names_[9]);
+  EXPECT_EQ(value_names_[5], value_names_[10]);
+  EXPECT_EQ(value_names_[6], value_names_[13]);
+  EXPECT_EQ(value_names_[7], value_names_[14]);
+
+  const size_t no_null_ck_indexes[] = { 4, 9 };
+  ExpectNoNullCheck(no_null_ck_indexes);
+
+  static const bool eliminated[] = {
+      false, false, false, false, false, false, false, false, false,
+      false, false, false, false, false, false
+  };
+  static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch");
+  for (size_t i = 0; i != arraysize(eliminated); ++i) {
+    bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop);
+    EXPECT_EQ(eliminated[i], actually_eliminated) << i;
+  }
+}
+
+TEST_F(GvnDeadCodeEliminationTestDiamond, CreatePhi1) {
+  static const MIRDef mirs[] = {
+      DEF_CONST(3, Instruction::CONST, 0u, 1000),
+      DEF_CONST(4, Instruction::CONST, 1u, 1000),
+  };
+
+  static const int32_t sreg_to_vreg_map[] = { 0, 0 };
+  PrepareSRegToVRegMap(sreg_to_vreg_map);
+
+  PrepareMIRs(mirs);
+  PerformGVN_DCE();
+
+  ASSERT_EQ(arraysize(mirs), value_names_.size());
+  EXPECT_EQ(value_names_[0], value_names_[1]);
+
+  static const bool eliminated[] = {
+      false, true,
+  };
+  static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch");
+  for (size_t i = 0; i != arraysize(eliminated); ++i) {
+    bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop);
+    EXPECT_EQ(eliminated[i], actually_eliminated) << i;
+  }
+  // Check that we've created a single-input Phi to replace the CONST 3u.
+  BasicBlock* bb4 = cu_.mir_graph->GetBasicBlock(4);
+  MIR* phi = bb4->first_mir_insn;
+  ASSERT_TRUE(phi != nullptr);
+  ASSERT_EQ(kMirOpPhi, static_cast<int>(phi->dalvikInsn.opcode));
+  ASSERT_EQ(1, phi->ssa_rep->num_uses);
+  EXPECT_EQ(0, phi->ssa_rep->uses[0]);
+  ASSERT_EQ(1, phi->ssa_rep->num_defs);
+  EXPECT_EQ(1, phi->ssa_rep->defs[0]);
+  EXPECT_EQ(0u, phi->dalvikInsn.vA);
+}
+
+TEST_F(GvnDeadCodeEliminationTestDiamond, CreatePhi2) {
+  static const IFieldDef ifields[] = {
+      { 0u, 1u, 0u, false, kDexMemAccessWord },
+  };
+  static const MIRDef mirs[] = {
+      DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u),
+      DEF_CONST(4, Instruction::CONST, 1u, 1000),
+      DEF_IPUT(4, Instruction::IPUT, 1u, 0u, 0u),
+      DEF_CONST(5, Instruction::CONST, 3u, 2000),
+      DEF_IPUT(5, Instruction::IPUT, 3u, 0u, 0u),
+      DEF_IGET(6, Instruction::IGET, 5u, 0u, 0u),
+  };
+
+  static const int32_t sreg_to_vreg_map[] = { 0, 1, 2 /* dummy */, 1, 2 /* dummy */, 1 };
+  PrepareSRegToVRegMap(sreg_to_vreg_map);
+
+  PrepareIFields(ifields);
+  PrepareMIRs(mirs);
+  PerformGVN_DCE();
+
+  ASSERT_EQ(arraysize(mirs), value_names_.size());
+  static const size_t diff_indexes[] = { 0, 1, 3, 5 };
+  ExpectValueNamesNE(diff_indexes);
+
+  const size_t no_null_ck_indexes[] = { 2, 4, 5 };
+  ExpectNoNullCheck(no_null_ck_indexes);
+
+  static const bool eliminated[] = {
+      false, false, false, false, false, true,
+  };
+  static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch");
+  for (size_t i = 0; i != arraysize(eliminated); ++i) {
+    bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop);
+    EXPECT_EQ(eliminated[i], actually_eliminated) << i;
+  }
+  // Check that we've created a two-input Phi to replace the IGET 5u.
+  BasicBlock* bb6 = cu_.mir_graph->GetBasicBlock(6);
+  MIR* phi = bb6->first_mir_insn;
+  ASSERT_TRUE(phi != nullptr);
+  ASSERT_EQ(kMirOpPhi, static_cast<int>(phi->dalvikInsn.opcode));
+  ASSERT_EQ(2, phi->ssa_rep->num_uses);
+  EXPECT_EQ(1, phi->ssa_rep->uses[0]);
+  EXPECT_EQ(3, phi->ssa_rep->uses[1]);
+  ASSERT_EQ(1, phi->ssa_rep->num_defs);
+  EXPECT_EQ(5, phi->ssa_rep->defs[0]);
+  EXPECT_EQ(1u, phi->dalvikInsn.vA);
+}
+
+TEST_F(GvnDeadCodeEliminationTestDiamond, KillChainInAnotherBlock1) {
+  static const IFieldDef ifields[] = {
+      { 0u, 1u, 0u, false, kDexMemAccessObject },  // linked list
+  };
+  static const MIRDef mirs[] = {
+      DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u),
+      DEF_IGET(3, Instruction::IGET_OBJECT, 1u, 0u, 0u),
+      DEF_IGET(3, Instruction::IGET_OBJECT, 2u, 1u, 0u),
+      DEF_IGET(3, Instruction::IGET_OBJECT, 3u, 2u, 0u),
+      DEF_IGET(3, Instruction::IGET_OBJECT, 4u, 3u, 0u),
+      DEF_IFZ(3, Instruction::IF_NEZ, 4u),
+      DEF_IGET(4, Instruction::IGET_OBJECT, 6u, 0u, 0u),
+      DEF_IGET(4, Instruction::IGET_OBJECT, 7u, 6u, 0u),
+      DEF_IGET(4, Instruction::IGET_OBJECT, 8u, 7u, 0u),
+      DEF_IGET(4, Instruction::IGET_OBJECT, 9u, 8u, 0u),
+  };
+
+  static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 1, 2, 3 /* dummy */, 1, 2, 1, 2 };
+  PrepareSRegToVRegMap(sreg_to_vreg_map);
+
+  PrepareIFields(ifields);
+  PrepareMIRs(mirs);
+  PerformGVN_DCE();
+
+  ASSERT_EQ(arraysize(mirs), value_names_.size());
+  static const size_t diff_indexes[] = { 0, 1, 2, 3, 4 };
+  ExpectValueNamesNE(diff_indexes);
+  EXPECT_EQ(value_names_[1], value_names_[6]);
+  EXPECT_EQ(value_names_[2], value_names_[7]);
+  EXPECT_EQ(value_names_[3], value_names_[8]);
+  EXPECT_EQ(value_names_[4], value_names_[9]);
+
+  const size_t no_null_ck_indexes[] = { 1, 6, 7, 8, 9 };
+  ExpectNoNullCheck(no_null_ck_indexes);
+
+  static const bool eliminated[] = {
+      false, false, false, false, false, false, true, true, true, true,
+  };
+  static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch");
+  for (size_t i = 0; i != arraysize(eliminated); ++i) {
+    bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop);
+    EXPECT_EQ(eliminated[i], actually_eliminated) << i;
+  }
+  // Check that we've created two single-input Phis to replace the IGET 8u and IGET 9u;
+  // the IGET 6u and IGET 7u were killed without a replacement.
+  BasicBlock* bb4 = cu_.mir_graph->GetBasicBlock(4);
+  MIR* phi1 = bb4->first_mir_insn;
+  ASSERT_TRUE(phi1 != nullptr);
+  ASSERT_EQ(kMirOpPhi, static_cast<int>(phi1->dalvikInsn.opcode));
+  MIR* phi2 = phi1->next;
+  ASSERT_TRUE(phi2 != nullptr);
+  ASSERT_EQ(kMirOpPhi, static_cast<int>(phi2->dalvikInsn.opcode));
+  ASSERT_TRUE(phi2->next == &mirs_[6]);
+  if (phi1->dalvikInsn.vA == 2u) {
+    std::swap(phi1, phi2);
+  }
+  ASSERT_EQ(1, phi1->ssa_rep->num_uses);
+  EXPECT_EQ(3, phi1->ssa_rep->uses[0]);
+  ASSERT_EQ(1, phi1->ssa_rep->num_defs);
+  EXPECT_EQ(8, phi1->ssa_rep->defs[0]);
+  EXPECT_EQ(1u, phi1->dalvikInsn.vA);
+  ASSERT_EQ(1, phi2->ssa_rep->num_uses);
+  EXPECT_EQ(4, phi2->ssa_rep->uses[0]);
+  ASSERT_EQ(1, phi2->ssa_rep->num_defs);
+  EXPECT_EQ(9, phi2->ssa_rep->defs[0]);
+  EXPECT_EQ(2u, phi2->dalvikInsn.vA);
+}
+
+TEST_F(GvnDeadCodeEliminationTestDiamond, KillChainInAnotherBlock2) {
+  static const IFieldDef ifields[] = {
+      { 0u, 1u, 0u, false, kDexMemAccessObject },  // linked list
+  };
+  static const MIRDef mirs[] = {
+      DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u),
+      DEF_IGET(3, Instruction::IGET_OBJECT, 1u, 0u, 0u),
+      DEF_IGET(3, Instruction::IGET_OBJECT, 2u, 1u, 0u),
+      DEF_IGET(3, Instruction::IGET_OBJECT, 3u, 2u, 0u),
+      DEF_IGET(3, Instruction::IGET_OBJECT, 4u, 3u, 0u),
+      DEF_IFZ(3, Instruction::IF_NEZ, 4u),
+      DEF_IGET(4, Instruction::IGET_OBJECT, 6u, 0u, 0u),
+      DEF_IGET(4, Instruction::IGET_OBJECT, 7u, 6u, 0u),
+      DEF_IGET(4, Instruction::IGET_OBJECT, 8u, 7u, 0u),
+      DEF_CONST(4, Instruction::CONST, 9u, 1000),
+  };
+
+  static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 1, 2, 3 /* dummy */, 1, 2, 1, 2 };
+  PrepareSRegToVRegMap(sreg_to_vreg_map);
+
+  PrepareIFields(ifields);
+  PrepareMIRs(mirs);
+  PerformGVN_DCE();
+
+  ASSERT_EQ(arraysize(mirs), value_names_.size());
+  static const size_t diff_indexes[] = { 0, 1, 2, 3, 4, 9 };
+  ExpectValueNamesNE(diff_indexes);
+  EXPECT_EQ(value_names_[1], value_names_[6]);
+  EXPECT_EQ(value_names_[2], value_names_[7]);
+  EXPECT_EQ(value_names_[3], value_names_[8]);
+
+  const size_t no_null_ck_indexes[] = { 1, 6, 7, 8 };
+  ExpectNoNullCheck(no_null_ck_indexes);
+
+  static const bool eliminated[] = {
+      false, false, false, false, false, false, true, true, true, false,
+  };
+  static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch");
+  for (size_t i = 0; i != arraysize(eliminated); ++i) {
+    bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop);
+    EXPECT_EQ(eliminated[i], actually_eliminated) << i;
+  }
+  // Check that we've created a single-input Phi to replace the IGET 8u;
+  // the IGET 6u and IGET 7u were killed without a replacement.
+  BasicBlock* bb4 = cu_.mir_graph->GetBasicBlock(4);
+  MIR* phi = bb4->first_mir_insn;
+  ASSERT_TRUE(phi != nullptr);
+  ASSERT_EQ(kMirOpPhi, static_cast<int>(phi->dalvikInsn.opcode));
+  ASSERT_TRUE(phi->next == &mirs_[6]);
+  ASSERT_EQ(1, phi->ssa_rep->num_uses);
+  EXPECT_EQ(3, phi->ssa_rep->uses[0]);
+  ASSERT_EQ(1, phi->ssa_rep->num_defs);
+  EXPECT_EQ(8, phi->ssa_rep->defs[0]);
+  EXPECT_EQ(1u, phi->dalvikInsn.vA);
+}
+
+TEST_F(GvnDeadCodeEliminationTestLoop, IFieldLoopVariable) {
+  static const IFieldDef ifields[] = {
+      { 0u, 1u, 0u, false, kDexMemAccessWord },
+  };
+  static const MIRDef mirs[] = {
+      DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u),
+      DEF_CONST(3, Instruction::CONST, 1u, 1),
+      DEF_CONST(3, Instruction::CONST, 2u, 0),
+      DEF_IPUT(3, Instruction::IPUT, 2u, 0u, 0u),
+      DEF_IGET(4, Instruction::IGET, 4u, 0u, 0u),
+      DEF_BINOP(4, Instruction::ADD_INT, 5u, 4u, 1u),
+      DEF_IPUT(4, Instruction::IPUT, 5u, 0u, 0u),
+  };
+
+  static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 3 /* dummy */, 2, 2 };
+  PrepareSRegToVRegMap(sreg_to_vreg_map);
+
+  PrepareIFields(ifields);
+  PrepareMIRs(mirs);
+  PerformGVN_DCE();
+
+  ASSERT_EQ(arraysize(mirs), value_names_.size());
+  static const size_t diff_indexes[] = { 0, 1, 2, 4, 5 };
+  ExpectValueNamesNE(diff_indexes);
+
+  const size_t no_null_ck_indexes[] = { 3, 4, 6 };
+  ExpectNoNullCheck(no_null_ck_indexes);
+
+  static const bool eliminated[] = {
+      false, false, false, false, true, false, false,
+  };
+  static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch");
+  for (size_t i = 0; i != arraysize(eliminated); ++i) {
+    bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop);
+    EXPECT_EQ(eliminated[i], actually_eliminated) << i;
+  }
+  // Check that we've created a two-input Phi to replace the IGET 3u.
+  BasicBlock* bb4 = cu_.mir_graph->GetBasicBlock(4);
+  MIR* phi = bb4->first_mir_insn;
+  ASSERT_TRUE(phi != nullptr);
+  ASSERT_EQ(kMirOpPhi, static_cast<int>(phi->dalvikInsn.opcode));
+  ASSERT_TRUE(phi->next == &mirs_[4]);
+  ASSERT_EQ(2, phi->ssa_rep->num_uses);
+  EXPECT_EQ(2, phi->ssa_rep->uses[0]);
+  EXPECT_EQ(5, phi->ssa_rep->uses[1]);
+  ASSERT_EQ(1, phi->ssa_rep->num_defs);
+  EXPECT_EQ(4, phi->ssa_rep->defs[0]);
+  EXPECT_EQ(2u, phi->dalvikInsn.vA);
+}
+
+}  // namespace art
diff --git a/compiler/dex/local_value_numbering.cc b/compiler/dex/local_value_numbering.cc
index aecde51fc..d67768077 100644
--- a/compiler/dex/local_value_numbering.cc
+++ b/compiler/dex/local_value_numbering.cc
@@ -901,9 +901,9 @@ void LocalValueNumbering::MergeAliasingValues(const typename Map::value_type& en
     // Calculate merged values for the intersection.
     for (auto& load_value_entry : my_values->load_value_map) {
       uint16_t location = load_value_entry.first;
-      bool same_values = true;
-      uint16_t value_name = kNoValue;
       merge_names_.clear();
+      uint16_t value_name = kNoValue;
+      bool same_values = true;
       for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) {
         value_name = Versions::LookupMergeValue(gvn_, lvn, key, location);
         same_values = same_values && (merge_names_.empty() || value_name == merge_names_.back());
@@ -937,6 +937,10 @@ void LocalValueNumbering::MergeAliasingValues(const typename Map::value_type& en
 void LocalValueNumbering::Merge(MergeType merge_type) {
   DCHECK_GE(gvn_->merge_lvns_.size(), 2u);
 
+  // Always reserve space in merge_names_. Even if we don't use it in Merge() we may need it
+  // in GetStartingVregValueNumberImpl() when the merge_names_'s allocator is not the top.
+  merge_names_.reserve(gvn_->merge_lvns_.size());
+
   IntersectSregValueMaps<&LocalValueNumbering::sreg_value_map_>();
   IntersectSregValueMaps<&LocalValueNumbering::sreg_wide_value_map_>();
   if (merge_type == kReturnMerge) {
@@ -1169,8 +1173,8 @@ uint16_t LocalValueNumbering::HandlePhi(MIR* mir) {
   int first_s_reg = uses[pos];
   bool wide = (first_lvn->sreg_wide_value_map_.count(first_s_reg) != 0u);
   // Iterate over *merge_lvns_ and skip incoming sregs for BBs without associated LVN.
-  uint16_t value_name = kNoValue;
   merge_names_.clear();
+  uint16_t value_name = kNoValue;
   bool same_values = true;
   for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) {
     DCHECK_LT(pos, mir->ssa_rep->num_uses);
@@ -1592,12 +1596,18 @@ uint16_t LocalValueNumbering::GetValueNumber(MIR* mir) {
       break;
     case Instruction::MOVE_EXCEPTION:
     case Instruction::NEW_INSTANCE:
-    case Instruction::CONST_CLASS:
     case Instruction::NEW_ARRAY:
       // 1 result, treat as unique each time, use result s_reg - will be unique.
       res = MarkNonAliasingNonNull(mir);
       SetOperandValue(mir->ssa_rep->defs[0], res);
       break;
+    case Instruction::CONST_CLASS:
+      DCHECK_EQ(Low16Bits(mir->dalvikInsn.vB), mir->dalvikInsn.vB);
+      res = gvn_->LookupValue(Instruction::CONST_CLASS, mir->dalvikInsn.vB, 0, 0);
+      SetOperandValue(mir->ssa_rep->defs[0], res);
+      null_checked_.insert(res);
+      non_aliasing_refs_.insert(res);
+      break;
     case Instruction::CONST_STRING:
     case Instruction::CONST_STRING_JUMBO:
       // These strings are internalized, so assign value based on the string pool index.
@@ -1641,16 +1651,22 @@ uint16_t LocalValueNumbering::GetValueNumber(MIR* mir) {
       SetOperandValueWide(mir->ssa_rep->defs[0], res);
       break;
 
+    case Instruction::CONST_HIGH16:
+      if (mir->dalvikInsn.vB != 0) {
+        res = gvn_->LookupValue(Instruction::CONST, 0, mir->dalvikInsn.vB, 0);
+        SetOperandValue(mir->ssa_rep->defs[0], res);
+        break;
+      }
+      FALLTHROUGH_INTENDED;
     case Instruction::CONST:
     case Instruction::CONST_4:
     case Instruction::CONST_16:
-      res = gvn_->LookupValue(Instruction::CONST, Low16Bits(mir->dalvikInsn.vB),
-                              High16Bits(mir->dalvikInsn.vB), 0);
-      SetOperandValue(mir->ssa_rep->defs[0], res);
-      break;
-
-    case Instruction::CONST_HIGH16:
-      res = gvn_->LookupValue(Instruction::CONST, 0, mir->dalvikInsn.vB, 0);
+      if (mir->dalvikInsn.vB == 0 && gvn_->GetMirGraph()->GetRawDest(mir).ref) {
+        res = GlobalValueNumbering::kNullValue;
+      } else {
+        res = gvn_->LookupValue(Instruction::CONST, Low16Bits(mir->dalvikInsn.vB),
+                                High16Bits(mir->dalvikInsn.vB), 0);
+      }
       SetOperandValue(mir->ssa_rep->defs[0], res);
       break;
 
@@ -1956,4 +1972,55 @@ uint16_t LocalValueNumbering::GetValueNumber(MIR* mir) {
   return res;
 }
 
+uint16_t LocalValueNumbering::GetEndingVregValueNumberImpl(int v_reg, bool wide) const {
+  const BasicBlock* bb = gvn_->GetBasicBlock(Id());
+  DCHECK(bb != nullptr);
+  int s_reg = bb->data_flow_info->vreg_to_ssa_map_exit[v_reg];
+  if (s_reg == INVALID_SREG) {
+    return kNoValue;
+  }
+  if (wide) {
+    int high_s_reg = bb->data_flow_info->vreg_to_ssa_map_exit[v_reg + 1];
+    if (high_s_reg != s_reg + 1) {
+      return kNoValue;  // High word has been overwritten.
+    }
+    return GetSregValueWide(s_reg);
+  } else {
+    return GetSregValue(s_reg);
+  }
+}
+
+uint16_t LocalValueNumbering::GetStartingVregValueNumberImpl(int v_reg, bool wide) const {
+  DCHECK_EQ(gvn_->mode_, GlobalValueNumbering::kModeGvnPostProcessing);
+  DCHECK(gvn_->CanModify());
+  const BasicBlock* bb = gvn_->GetBasicBlock(Id());
+  DCHECK(bb != nullptr);
+  DCHECK_NE(bb->predecessors.size(), 0u);
+  if (bb->predecessors.size() == 1u) {
+    return gvn_->GetLvn(bb->predecessors[0])->GetEndingVregValueNumberImpl(v_reg, wide);
+  }
+  merge_names_.clear();
+  uint16_t value_name = kNoValue;
+  bool same_values = true;
+  for (BasicBlockId pred_id : bb->predecessors) {
+    value_name = gvn_->GetLvn(pred_id)->GetEndingVregValueNumberImpl(v_reg, wide);
+    if (value_name == kNoValue) {
+      return kNoValue;
+    }
+    same_values = same_values && (merge_names_.empty() || value_name == merge_names_.back());
+    merge_names_.push_back(value_name);
+  }
+  if (same_values) {
+    // value_name already contains the result.
+  } else {
+    auto lb = merge_map_.lower_bound(merge_names_);
+    if (lb != merge_map_.end() && !merge_map_.key_comp()(merge_names_, lb->first)) {
+      value_name = lb->second;
+    } else {
+      value_name = kNoValue;  // We never assigned a value name to this set of merged names.
+    }
+  }
+  return value_name;
+}
+
 }    // namespace art
diff --git a/compiler/dex/local_value_numbering.h b/compiler/dex/local_value_numbering.h
index aef8c6df0..f51b88611 100644
--- a/compiler/dex/local_value_numbering.h
+++ b/compiler/dex/local_value_numbering.h
@@ -52,13 +52,22 @@ class LocalValueNumbering : public DeletableArenaObject<kArenaAllocMisc> {
     return div_zero_checked_.find(value_name) != div_zero_checked_.end();
   }
 
-  bool IsSregValue(uint16_t s_reg, uint16_t value_name) const {
-    auto it = sreg_value_map_.find(s_reg);
-    if (it != sreg_value_map_.end()) {
-      return it->second == value_name;
-    } else {
-      return gvn_->HasValue(kNoValue, s_reg, kNoValue, kNoValue, value_name);
-    }
+  uint16_t GetSregValue(uint16_t s_reg) const {
+    return GetSregValueImpl(s_reg, &sreg_value_map_);
+  }
+
+  uint16_t GetSregValueWide(uint16_t s_reg) const {
+    return GetSregValueImpl(s_reg, &sreg_wide_value_map_);
+  }
+
+  // Get the starting value number for a given dalvik register.
+  uint16_t GetStartingVregValueNumber(int v_reg) const {
+    return GetStartingVregValueNumberImpl(v_reg, false);
+  }
+
+  // Get the starting value number for a given wide dalvik register.
+  uint16_t GetStartingVregValueNumberWide(int v_reg) const {
+    return GetStartingVregValueNumberImpl(v_reg, true);
   }
 
   enum MergeType {
@@ -80,6 +89,20 @@ class LocalValueNumbering : public DeletableArenaObject<kArenaAllocMisc> {
   // Key is s_reg, value is value name.
   typedef ScopedArenaSafeMap<uint16_t, uint16_t> SregValueMap;
 
+  uint16_t GetEndingVregValueNumberImpl(int v_reg, bool wide) const;
+  uint16_t GetStartingVregValueNumberImpl(int v_reg, bool wide) const;
+
+  uint16_t GetSregValueImpl(int s_reg, const SregValueMap* map) const {
+    uint16_t res = kNoValue;
+    auto lb = map->find(s_reg);
+    if (lb != map->end()) {
+      res = lb->second;
+    } else {
+      res = gvn_->FindValue(kNoValue, s_reg, kNoValue, kNoValue);
+    }
+    return res;
+  }
+
   void SetOperandValueImpl(uint16_t s_reg, uint16_t value, SregValueMap* map) {
     DCHECK_EQ(map->count(s_reg), 0u) << PrettyMethod(gvn_->cu_->method_idx, *gvn_->cu_->dex_file)
         << " LVN id: " << id_ << ", s_reg: " << s_reg;
@@ -370,9 +393,9 @@ class LocalValueNumbering : public DeletableArenaObject<kArenaAllocMisc> {
   ValueNameSet div_zero_checked_;
 
   // Reuse one vector for all merges to avoid leaking too much memory on the ArenaStack.
-  ScopedArenaVector<BasicBlockId> merge_names_;
+  mutable ScopedArenaVector<uint16_t> merge_names_;
   // Map to identify when different locations merge the same values.
-  ScopedArenaSafeMap<ScopedArenaVector<BasicBlockId>, uint16_t> merge_map_;
+  ScopedArenaSafeMap<ScopedArenaVector<uint16_t>, uint16_t> merge_map_;
   // New memory version for merge, kNoValue if all memory versions matched.
   uint16_t merge_new_memory_version_;
 
diff --git a/compiler/dex/local_value_numbering_test.cc b/compiler/dex/local_value_numbering_test.cc
index 9f18a3e62..ec1c39e0f 100644
--- a/compiler/dex/local_value_numbering_test.cc
+++ b/compiler/dex/local_value_numbering_test.cc
@@ -185,9 +185,9 @@ class LocalValueNumberingTest : public testing::Test {
   }
 
   void PerformLVN() {
-    cu_.mir_graph->temp_.gvn.ifield_ids_ =  GlobalValueNumbering::PrepareGvnFieldIds(
+    cu_.mir_graph->temp_.gvn.ifield_ids =  GlobalValueNumbering::PrepareGvnFieldIds(
         allocator_.get(), cu_.mir_graph->ifield_lowering_infos_);
-    cu_.mir_graph->temp_.gvn.sfield_ids_ =  GlobalValueNumbering::PrepareGvnFieldIds(
+    cu_.mir_graph->temp_.gvn.sfield_ids =  GlobalValueNumbering::PrepareGvnFieldIds(
         allocator_.get(), cu_.mir_graph->sfield_lowering_infos_);
     gvn_.reset(new (allocator_.get()) GlobalValueNumbering(&cu_, allocator_.get(),
                                                            GlobalValueNumbering::kModeLvn));
@@ -211,8 +211,14 @@ class LocalValueNumberingTest : public testing::Test {
         value_names_() {
     cu_.mir_graph.reset(new MIRGraph(&cu_, &cu_.arena));
     allocator_.reset(ScopedArenaAllocator::Create(&cu_.arena_stack));
+    // By default, the zero-initialized reg_location_[.] with ref == false tells LVN that
+    // 0 constants are integral, not references. Nothing else is used by LVN/GVN.
+    cu_.mir_graph->reg_location_ = static_cast<RegLocation*>(cu_.arena.Alloc(
+        kMaxSsaRegs * sizeof(cu_.mir_graph->reg_location_[0]), kArenaAllocRegAlloc));
   }
 
+  static constexpr size_t kMaxSsaRegs = 16384u;
+
   ArenaPool pool_;
   CompilationUnit cu_;
   size_t mir_count_;
diff --git a/compiler/dex/mir_dataflow.cc b/compiler/dex/mir_dataflow.cc
index 1f562769e..f9f7e22b0 100644
--- a/compiler/dex/mir_dataflow.cc
+++ b/compiler/dex/mir_dataflow.cc
@@ -910,11 +910,6 @@ const uint64_t MIRGraph::oat_data_flow_attributes_[kMirOpLast] = {
   DF_FORMAT_EXTENDED,
 };
 
-/* Return the base virtual register for a SSA name */
-int MIRGraph::SRegToVReg(int ssa_reg) const {
-  return ssa_base_vregs_[ssa_reg];
-}
-
 /* Any register that is used before being defined is considered live-in */
 void MIRGraph::HandleLiveInUse(ArenaBitVector* use_v, ArenaBitVector* def_v,
                                ArenaBitVector* live_in_v, int dalvik_reg_id) {
diff --git a/compiler/dex/mir_field_info.h b/compiler/dex/mir_field_info.h
index ff427f88d..98b2da829 100644
--- a/compiler/dex/mir_field_info.h
+++ b/compiler/dex/mir_field_info.h
@@ -149,6 +149,7 @@ class MirIFieldLoweringInfo : public MirFieldInfo {
 
   friend class NullCheckEliminationTest;
   friend class GlobalValueNumberingTest;
+  friend class GvnDeadCodeEliminationTest;
   friend class LocalValueNumberingTest;
 };
 
@@ -223,6 +224,7 @@ class MirSFieldLoweringInfo : public MirFieldInfo {
 
   friend class ClassInitCheckEliminationTest;
   friend class GlobalValueNumberingTest;
+  friend class GvnDeadCodeEliminationTest;
   friend class LocalValueNumberingTest;
 };
 
diff --git a/compiler/dex/mir_graph.cc b/compiler/dex/mir_graph.cc
index 9f985890b..08ca1b288 100644
--- a/compiler/dex/mir_graph.cc
+++ b/compiler/dex/mir_graph.cc
@@ -2559,4 +2559,13 @@ const uint16_t* MIRGraph::GetInsns(int m_unit_index) const {
   return m_units_[m_unit_index]->GetCodeItem()->insns_;
 }
 
+void MIRGraph::SetPuntToInterpreter(bool val) {
+  punt_to_interpreter_ = val;
+  if (val) {
+    // Disable all subsequent optimizations. They may not be safe to run. (For example,
+    // LVN/GVN assumes there are no conflicts found by the type inference pass.)
+    cu_->disable_opt = ~static_cast<decltype(cu_->disable_opt)>(0);
+  }
+}
+
 }  // namespace art
diff --git a/compiler/dex/mir_graph.h b/compiler/dex/mir_graph.h
index c33825bb0..020136c3d 100644
--- a/compiler/dex/mir_graph.h
+++ b/compiler/dex/mir_graph.h
@@ -37,6 +37,7 @@ struct CompilationUnit;
 class DexCompilationUnit;
 class DexFileMethodInliner;
 class GlobalValueNumbering;
+class GvnDeadCodeElimination;
 
 // Forward declaration.
 class MIRGraph;
@@ -1052,7 +1053,12 @@ class MIRGraph {
 
   void DumpCheckStats();
   MIR* FindMoveResult(BasicBlock* bb, MIR* mir);
-  int SRegToVReg(int ssa_reg) const;
+
+  /* Return the base virtual register for a SSA name */
+  int SRegToVReg(int ssa_reg) const {
+    return ssa_base_vregs_[ssa_reg];
+  }
+
   void VerifyDataflow();
   void CheckForDominanceFrontier(BasicBlock* dom_bb, const BasicBlock* succ_bb);
   bool EliminateNullChecksGate();
@@ -1065,6 +1071,9 @@ class MIRGraph {
   bool ApplyGlobalValueNumberingGate();
   bool ApplyGlobalValueNumbering(BasicBlock* bb);
   void ApplyGlobalValueNumberingEnd();
+  bool EliminateDeadCodeGate();
+  bool EliminateDeadCode(BasicBlock* bb);
+  void EliminateDeadCodeEnd();
   bool EliminateSuspendChecksGate();
   bool EliminateSuspendChecks(BasicBlock* bb);
   void EliminateSuspendChecksEnd();
@@ -1072,15 +1081,15 @@ class MIRGraph {
   uint16_t GetGvnIFieldId(MIR* mir) const {
     DCHECK(IsInstructionIGetOrIPut(mir->dalvikInsn.opcode));
     DCHECK_LT(mir->meta.ifield_lowering_info, ifield_lowering_infos_.size());
-    DCHECK(temp_.gvn.ifield_ids_ != nullptr);
-    return temp_.gvn.ifield_ids_[mir->meta.ifield_lowering_info];
+    DCHECK(temp_.gvn.ifield_ids != nullptr);
+    return temp_.gvn.ifield_ids[mir->meta.ifield_lowering_info];
   }
 
   uint16_t GetGvnSFieldId(MIR* mir) const {
     DCHECK(IsInstructionSGetOrSPut(mir->dalvikInsn.opcode));
     DCHECK_LT(mir->meta.sfield_lowering_info, sfield_lowering_infos_.size());
-    DCHECK(temp_.gvn.sfield_ids_ != nullptr);
-    return temp_.gvn.sfield_ids_[mir->meta.sfield_lowering_info];
+    DCHECK(temp_.gvn.sfield_ids != nullptr);
+    return temp_.gvn.sfield_ids[mir->meta.sfield_lowering_info];
   }
 
   /*
@@ -1115,9 +1124,7 @@ class MIRGraph {
     return punt_to_interpreter_;
   }
 
-  void SetPuntToInterpreter(bool val) {
-    punt_to_interpreter_ = val;
-  }
+  void SetPuntToInterpreter(bool val);
 
   void DisassembleExtendedInstr(const MIR* mir, std::string* decoded_mir);
   char* GetDalvikDisassembly(const MIR* mir);
@@ -1284,7 +1291,8 @@ class MIRGraph {
    * @param mir The mir to check.
    * @return Returns 'true' if the given MIR might throw an exception.
    */
-  bool CanThrow(MIR* mir);
+  bool CanThrow(MIR* mir) const;
+
   /**
    * @brief Combine multiply and add/sub MIRs into corresponding extended MAC MIR.
    * @param mul_mir The multiply MIR to be combined.
@@ -1382,8 +1390,9 @@ class MIRGraph {
     // Global value numbering.
     struct {
       GlobalValueNumbering* gvn;
-      uint16_t* ifield_ids_;  // Part of GVN/LVN but cached here for LVN to avoid recalculation.
-      uint16_t* sfield_ids_;  // Ditto.
+      uint16_t* ifield_ids;  // Part of GVN/LVN but cached here for LVN to avoid recalculation.
+      uint16_t* sfield_ids;  // Ditto.
+      GvnDeadCodeElimination* dce;
     } gvn;
     // Suspend check elimination.
     struct {
@@ -1437,6 +1446,7 @@ class MIRGraph {
   friend class SuspendCheckEliminationTest;
   friend class NullCheckEliminationTest;
   friend class GlobalValueNumberingTest;
+  friend class GvnDeadCodeEliminationTest;
   friend class LocalValueNumberingTest;
   friend class TopologicalSortOrderTest;
 };
diff --git a/compiler/dex/mir_optimization.cc b/compiler/dex/mir_optimization.cc
index dac021060..2f547ea45 100644
--- a/compiler/dex/mir_optimization.cc
+++ b/compiler/dex/mir_optimization.cc
@@ -21,6 +21,7 @@
 #include "driver/compiler_driver.h"
 #include "driver/dex_compilation_unit.h"
 #include "global_value_numbering.h"
+#include "gvn_dead_code_elimination.h"
 #include "local_value_numbering.h"
 #include "mir_field_info.h"
 #include "quick/dex_file_method_inliner.h"
@@ -1333,9 +1334,9 @@ bool MIRGraph::ApplyGlobalValueNumberingGate() {
 
   DCHECK(temp_scoped_alloc_ == nullptr);
   temp_scoped_alloc_.reset(ScopedArenaAllocator::Create(&cu_->arena_stack));
-  temp_.gvn.ifield_ids_ =
+  temp_.gvn.ifield_ids =
       GlobalValueNumbering::PrepareGvnFieldIds(temp_scoped_alloc_.get(), ifield_lowering_infos_);
-  temp_.gvn.sfield_ids_ =
+  temp_.gvn.sfield_ids =
       GlobalValueNumbering::PrepareGvnFieldIds(temp_scoped_alloc_.get(), sfield_lowering_infos_);
   DCHECK(temp_.gvn.gvn == nullptr);
   temp_.gvn.gvn = new (temp_scoped_alloc_.get()) GlobalValueNumbering(
@@ -1359,8 +1360,8 @@ void MIRGraph::ApplyGlobalValueNumberingEnd() {
   // Perform modifications.
   DCHECK(temp_.gvn.gvn != nullptr);
   if (temp_.gvn.gvn->Good()) {
+    temp_.gvn.gvn->StartPostProcessing();
     if (max_nested_loops_ != 0u) {
-      temp_.gvn.gvn->StartPostProcessing();
       TopologicalSortIterator iter(this);
       for (BasicBlock* bb = iter.Next(); bb != nullptr; bb = iter.Next()) {
         ScopedArenaAllocator allocator(&cu_->arena_stack);  // Reclaim memory after each LVN.
@@ -1378,12 +1379,45 @@ void MIRGraph::ApplyGlobalValueNumberingEnd() {
     cu_->disable_opt |= (1u << kLocalValueNumbering);
   } else {
     LOG(WARNING) << "GVN failed for " << PrettyMethod(cu_->method_idx, *cu_->dex_file);
+    cu_->disable_opt |= (1u << kGvnDeadCodeElimination);
   }
 
+  if ((cu_->disable_opt & (1 << kGvnDeadCodeElimination)) != 0) {
+    EliminateDeadCodeEnd();
+  }  // else preserve GVN data for CSE.
+}
+
+bool MIRGraph::EliminateDeadCodeGate() {
+  if ((cu_->disable_opt & (1 << kGvnDeadCodeElimination)) != 0) {
+    return false;
+  }
+  DCHECK(temp_scoped_alloc_ != nullptr);
+  temp_.gvn.dce = new (temp_scoped_alloc_.get()) GvnDeadCodeElimination(temp_.gvn.gvn,
+                                                                        temp_scoped_alloc_.get());
+  return true;
+}
+
+bool MIRGraph::EliminateDeadCode(BasicBlock* bb) {
+  DCHECK(temp_scoped_alloc_ != nullptr);
+  DCHECK(temp_.gvn.gvn != nullptr);
+  if (bb->block_type != kDalvikByteCode) {
+    return false;
+  }
+  DCHECK(temp_.gvn.dce != nullptr);
+  temp_.gvn.dce->Apply(bb);
+  return false;  // No need to repeat.
+}
+
+void MIRGraph::EliminateDeadCodeEnd() {
+  DCHECK_EQ(temp_.gvn.dce != nullptr, (cu_->disable_opt & (1 << kGvnDeadCodeElimination)) == 0);
+  if (temp_.gvn.dce != nullptr) {
+    delete temp_.gvn.dce;
+    temp_.gvn.dce = nullptr;
+  }
   delete temp_.gvn.gvn;
   temp_.gvn.gvn = nullptr;
-  temp_.gvn.ifield_ids_ = nullptr;
-  temp_.gvn.sfield_ids_ = nullptr;
+  temp_.gvn.ifield_ids = nullptr;
+  temp_.gvn.sfield_ids = nullptr;
   DCHECK(temp_scoped_alloc_ != nullptr);
   temp_scoped_alloc_.reset();
 }
@@ -1553,9 +1587,9 @@ bool MIRGraph::BuildExtendedBBList(class BasicBlock* bb) {
 void MIRGraph::BasicBlockOptimizationStart() {
   if ((cu_->disable_opt & (1 << kLocalValueNumbering)) == 0) {
     temp_scoped_alloc_.reset(ScopedArenaAllocator::Create(&cu_->arena_stack));
-    temp_.gvn.ifield_ids_ =
+    temp_.gvn.ifield_ids =
         GlobalValueNumbering::PrepareGvnFieldIds(temp_scoped_alloc_.get(), ifield_lowering_infos_);
-    temp_.gvn.sfield_ids_ =
+    temp_.gvn.sfield_ids =
         GlobalValueNumbering::PrepareGvnFieldIds(temp_scoped_alloc_.get(), sfield_lowering_infos_);
   }
 }
@@ -1581,8 +1615,8 @@ void MIRGraph::BasicBlockOptimization() {
 
 void MIRGraph::BasicBlockOptimizationEnd() {
   // Clean up after LVN.
-  temp_.gvn.ifield_ids_ = nullptr;
-  temp_.gvn.sfield_ids_ = nullptr;
+  temp_.gvn.ifield_ids = nullptr;
+  temp_.gvn.sfield_ids = nullptr;
   temp_scoped_alloc_.reset();
 }
 
@@ -1684,7 +1718,7 @@ void MIRGraph::EliminateSuspendChecksEnd() {
   temp_.sce.inliner = nullptr;
 }
 
-bool MIRGraph::CanThrow(MIR* mir) {
+bool MIRGraph::CanThrow(MIR* mir) const {
   if ((mir->dalvikInsn.FlagsOf() & Instruction::kThrow) == 0) {
     return false;
   }
@@ -1718,7 +1752,6 @@ bool MIRGraph::CanThrow(MIR* mir) {
     // Non-throwing only if range check has been eliminated.
     return ((opt_flags & MIR_IGNORE_RANGE_CHECK) == 0);
   } else if (mir->dalvikInsn.opcode == Instruction::ARRAY_LENGTH ||
-      mir->dalvikInsn.opcode == Instruction::FILL_ARRAY_DATA ||
       static_cast<int>(mir->dalvikInsn.opcode) == kMirOpNullCheck) {
     // No more checks for these (null check was processed above).
     return false;
diff --git a/compiler/dex/pass_driver_me_opts.cc b/compiler/dex/pass_driver_me_opts.cc
index 8c8bde63e..320d06aa0 100644
--- a/compiler/dex/pass_driver_me_opts.cc
+++ b/compiler/dex/pass_driver_me_opts.cc
@@ -45,6 +45,7 @@ void PassDriverMEOpts::SetupPasses(PassManager* pass_manager) {
   pass_manager->AddPass(new BBCombine);
   pass_manager->AddPass(new CodeLayout);
   pass_manager->AddPass(new GlobalValueNumberingPass);
+  pass_manager->AddPass(new DeadCodeEliminationPass);
   pass_manager->AddPass(new ConstantPropagation);
   pass_manager->AddPass(new MethodUseCount);
   pass_manager->AddPass(new BBOptimizations);
diff --git a/compiler/dex/quick/quick_compiler.cc b/compiler/dex/quick/quick_compiler.cc
index 909077eca..f39942973 100644
--- a/compiler/dex/quick/quick_compiler.cc
+++ b/compiler/dex/quick/quick_compiler.cc
@@ -560,6 +560,7 @@ static uint32_t kCompilerOptimizerDisableFlags = 0 |  // Disable specific optimi
   // (1 << kNullCheckElimination) |
   // (1 << kClassInitCheckElimination) |
   // (1 << kGlobalValueNumbering) |
+  // (1 << kGvnDeadCodeElimination) |
   // (1 << kLocalValueNumbering) |
   // (1 << kPromoteRegs) |
   // (1 << kTrackLiveTemps) |
diff --git a/compiler/utils/dex_instruction_utils.h b/compiler/utils/dex_instruction_utils.h
index 2c6e525e1..bb2c592f1 100644
--- a/compiler/utils/dex_instruction_utils.h
+++ b/compiler/utils/dex_instruction_utils.h
@@ -110,6 +110,10 @@ constexpr bool IsInstructionAGetOrAPut(Instruction::Code code) {
   return Instruction::AGET <= code && code <= Instruction::APUT_SHORT;
 }
 
+constexpr bool IsInstructionBinOp2Addr(Instruction::Code code) {
+  return Instruction::ADD_INT_2ADDR <= code && code <= Instruction::REM_DOUBLE_2ADDR;
+}
+
 // TODO: Remove the #if guards below when we fully migrate to C++14.
 
 constexpr bool IsInvokeInstructionRange(Instruction::Code opcode) {