diff --git a/Android.mk b/Android.mk
index 3cd6b5f..f8d46a4 100644
--- a/Android.mk
+++ b/Android.mk
@@ -77,7 +77,8 @@
 
 .PHONY: clean-oat-target
 clean-oat-target:
-	adb remount
+	adb root
+	adb wait-for-device remount
 	adb shell rm -rf $(ART_TARGET_NATIVETEST_DIR)
 	adb shell rm -rf $(ART_TARGET_TEST_DIR)
 	adb shell rm -rf $(ART_TARGET_DALVIK_CACHE_DIR)/*/*
@@ -140,7 +141,8 @@
 # Sync test files to the target, depends upon all things that must be pushed to the target.
 .PHONY: test-art-target-sync
 test-art-target-sync: $(TEST_ART_TARGET_SYNC_DEPS)
-	adb remount
+	adb root
+	adb wait-for-device remount
 	adb sync
 
 # Undefine variable now its served its purpose.
@@ -348,7 +350,8 @@
 
 .PHONY: oat-target-sync
 oat-target-sync: oat-target
-	adb remount
+	adb root
+	adb wait-for-device remount
 	adb sync
 
 ########################################################################
@@ -367,29 +370,29 @@
 
 .PHONY: use-art
 use-art:
-	adb root && sleep 3
-	adb shell stop
+	adb root
+	adb wait-for-device shell stop
 	adb shell setprop persist.sys.dalvik.vm.lib.2 libart.so
 	adb shell start
 
 .PHONY: use-artd
 use-artd:
-	adb root && sleep 3
-	adb shell stop
+	adb root
+	adb wait-for-device shell stop
 	adb shell setprop persist.sys.dalvik.vm.lib.2 libartd.so
 	adb shell start
 
 .PHONY: use-dalvik
 use-dalvik:
-	adb root && sleep 3
-	adb shell stop
+	adb root
+	adb wait-for-device shell stop
 	adb shell setprop persist.sys.dalvik.vm.lib.2 libdvm.so
 	adb shell start
 
 .PHONY: use-art-full
 use-art-full:
-	adb root && sleep 3
-	adb shell stop
+	adb root
+	adb wait-for-device shell stop
 	adb shell rm -rf $(ART_TARGET_DALVIK_CACHE_DIR)/*
 	adb shell setprop dalvik.vm.dex2oat-filter ""
 	adb shell setprop dalvik.vm.image-dex2oat-filter ""
@@ -398,8 +401,8 @@
 
 .PHONY: use-artd-full
 use-artd-full:
-	adb root && sleep 3
-	adb shell stop
+	adb root
+	adb wait-for-device shell stop
 	adb shell rm -rf $(ART_TARGET_DALVIK_CACHE_DIR)/*
 	adb shell setprop dalvik.vm.dex2oat-filter ""
 	adb shell setprop dalvik.vm.image-dex2oat-filter ""
@@ -408,8 +411,8 @@
 
 .PHONY: use-art-smart
 use-art-smart:
-	adb root && sleep 3
-	adb shell stop
+	adb root
+	adb wait-for-device shell stop
 	adb shell rm -rf $(ART_TARGET_DALVIK_CACHE_DIR)/*
 	adb shell setprop dalvik.vm.dex2oat-filter "interpret-only"
 	adb shell setprop dalvik.vm.image-dex2oat-filter ""
@@ -418,8 +421,8 @@
 
 .PHONY: use-art-interpret-only
 use-art-interpret-only:
-	adb root && sleep 3
-	adb shell stop
+	adb root
+	adb wait-for-device shell stop
 	adb shell rm -rf $(ART_TARGET_DALVIK_CACHE_DIR)/*
 	adb shell setprop dalvik.vm.dex2oat-filter "interpret-only"
 	adb shell setprop dalvik.vm.image-dex2oat-filter "interpret-only"
@@ -428,8 +431,8 @@
 
 .PHONY: use-artd-interpret-only
 use-artd-interpret-only:
-	adb root && sleep 3
-	adb shell stop
+	adb root
+	adb wait-for-device shell stop
 	adb shell rm -rf $(ART_TARGET_DALVIK_CACHE_DIR)/*
 	adb shell setprop dalvik.vm.dex2oat-filter "interpret-only"
 	adb shell setprop dalvik.vm.image-dex2oat-filter "interpret-only"
@@ -438,8 +441,8 @@
 
 .PHONY: use-art-verify-none
 use-art-verify-none:
-	adb root && sleep 3
-	adb shell stop
+	adb root
+	adb wait-for-device shell stop
 	adb shell rm -rf $(ART_TARGET_DALVIK_CACHE_DIR)/*
 	adb shell setprop dalvik.vm.dex2oat-filter "verify-none"
 	adb shell setprop dalvik.vm.image-dex2oat-filter "verify-none"
diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index 3f58527..d93d6dc 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -146,6 +146,7 @@
   compiler/optimizing/find_loops_test.cc \
   compiler/optimizing/graph_checker_test.cc \
   compiler/optimizing/graph_test.cc \
+  compiler/optimizing/gvn_test.cc \
   compiler/optimizing/linearize_test.cc \
   compiler/optimizing/liveness_test.cc \
   compiler/optimizing/live_interval_test.cc \
diff --git a/compiler/Android.mk b/compiler/Android.mk
index 35cddf9..7ac1c6b 100644
--- a/compiler/Android.mk
+++ b/compiler/Android.mk
@@ -94,6 +94,7 @@
 	optimizing/dead_code_elimination.cc \
 	optimizing/graph_checker.cc \
 	optimizing/graph_visualizer.cc \
+	optimizing/gvn.cc \
 	optimizing/locations.cc \
 	optimizing/nodes.cc \
 	optimizing/optimizing_compiler.cc \
diff --git a/compiler/dex/mir_graph.cc b/compiler/dex/mir_graph.cc
index 62a8f26..ce56255 100644
--- a/compiler/dex/mir_graph.cc
+++ b/compiler/dex/mir_graph.cc
@@ -2420,9 +2420,9 @@
     case kMirOpDivZeroCheck:
       return Instruction::kContinue | Instruction::kThrow;
     case kMirOpCheck:
-      return 0;
+      return Instruction::kContinue | Instruction::kThrow;
     case kMirOpCheckPart2:
-      return 0;
+      return Instruction::kContinue;
     case kMirOpSelect:
       return Instruction::kContinue;
     case kMirOpConstVector:
@@ -2457,6 +2457,12 @@
       return Instruction::kContinue;
     case kMirOpReturnVectorRegisters:
       return Instruction::kContinue;
+    case kMirOpMemBarrier:
+      return Instruction::kContinue;
+    case kMirOpPackedArrayGet:
+      return Instruction::kContinue | Instruction::kThrow;
+    case kMirOpPackedArrayPut:
+      return Instruction::kContinue | Instruction::kThrow;
     default:
       LOG(WARNING) << "ExtendedFlagsOf: Unhandled case: " << static_cast<int> (opcode);
       return 0;
diff --git a/compiler/dex/quick/arm/int_arm.cc b/compiler/dex/quick/arm/int_arm.cc
index b9a17cc..0de2a44 100644
--- a/compiler/dex/quick/arm/int_arm.cc
+++ b/compiler/dex/quick/arm/int_arm.cc
@@ -1039,6 +1039,7 @@
   jmp_to_ret->target = return_point;
 
   AddIntrinsicSlowPath(info, launchpad_branch, return_point);
+  ClobberCallerSave();  // We must clobber everything because slow path will return here
 
   return true;
 }
diff --git a/compiler/dex/quick/arm64/int_arm64.cc b/compiler/dex/quick/arm64/int_arm64.cc
index 1777e98..094db4c 100644
--- a/compiler/dex/quick/arm64/int_arm64.cc
+++ b/compiler/dex/quick/arm64/int_arm64.cc
@@ -918,6 +918,7 @@
   loop_finished->target = return_point;
 
   AddIntrinsicSlowPath(info, launchpad_branch, return_point);
+  ClobberCallerSave();  // We must clobber everything because slow path will return here
 
   return true;
 }
diff --git a/compiler/dex/quick/codegen_util.cc b/compiler/dex/quick/codegen_util.cc
index 6d8f288..d90bce1 100644
--- a/compiler/dex/quick/codegen_util.cc
+++ b/compiler/dex/quick/codegen_util.cc
@@ -1224,6 +1224,7 @@
 
 void Mir2Lir::AddSlowPath(LIRSlowPath* slowpath) {
   slow_paths_.Insert(slowpath);
+  ResetDefTracking();
 }
 
 void Mir2Lir::LoadCodeAddress(const MethodReference& target_method, InvokeType type,
diff --git a/compiler/dex/quick/gen_invoke.cc b/compiler/dex/quick/gen_invoke.cc
index 8ce696c..960f217 100755
--- a/compiler/dex/quick/gen_invoke.cc
+++ b/compiler/dex/quick/gen_invoke.cc
@@ -1193,7 +1193,7 @@
 
   LIR* intrinsic_finish = NewLIR0(kPseudoTargetLabel);
   AddIntrinsicSlowPath(info, slow_path_branch, intrinsic_finish);
-
+  ClobberCallerSave();  // We must clobber everything because slow path will return here
   return true;
 }
 
@@ -1492,6 +1492,7 @@
     LIR* resume_tgt = NewLIR0(kPseudoTargetLabel);
     info->opt_flags |= MIR_IGNORE_NULL_CHECK;  // Record that we've null checked.
     AddIntrinsicSlowPath(info, high_code_point_branch, resume_tgt);
+    ClobberCallerSave();  // We must clobber everything because slow path will return here
   } else {
     DCHECK_EQ(mir_graph_->ConstantValue(rl_char) & ~0xFFFF, 0);
     DCHECK(high_code_point_branch == nullptr);
diff --git a/compiler/dex/quick/mir_to_lir-inl.h b/compiler/dex/quick/mir_to_lir-inl.h
index 2e4e292..22588f3 100644
--- a/compiler/dex/quick/mir_to_lir-inl.h
+++ b/compiler/dex/quick/mir_to_lir-inl.h
@@ -97,7 +97,7 @@
 }
 
 inline LIR* Mir2Lir::NewLIR2NoDest(int opcode, int src, int info) {
-  DCHECK(IsPseudoLirOp(opcode) || (GetTargetInstFlags(opcode) & IS_UNARY_OP))
+  DCHECK(IsPseudoLirOp(opcode) || (GetTargetInstFlags(opcode) & IS_BINARY_OP))
       << GetTargetInstName(opcode) << " " << opcode << " "
       << PrettyMethod(cu_->method_idx, *cu_->dex_file) << " "
       << current_dalvik_offset_;
diff --git a/compiler/dex/quick/x86/assemble_x86.cc b/compiler/dex/quick/x86/assemble_x86.cc
index 9935a22..a9a0252 100644
--- a/compiler/dex/quick/x86/assemble_x86.cc
+++ b/compiler/dex/quick/x86/assemble_x86.cc
@@ -192,7 +192,7 @@
   { kX86Movnti32MR, kMemReg,    IS_STORE | IS_TERTIARY_OP | REG_USE02,   { 0x0F,          0, 0xC3, 0, 0, 0, 0, 0, false }, "Movnti32MR", "[!0r+!1d],!2r" },
   { kX86Movnti32AR, kArrayReg,  IS_STORE | IS_QUIN_OP     | REG_USE014,  { 0x0F,          0, 0xC3, 0, 0, 0, 0, 0, false }, "Movnti32AR", "[!0r+!1r<<!2d+!3d],!4r" },
   { kX86Mov32TR, kThreadReg, IS_STORE | IS_BINARY_OP   | REG_USE1,       { THREAD_PREFIX, 0, 0x89, 0, 0, 0, 0, 0, false }, "Mov32TR", "fs:[!0d],!1r" },
-  { kX86Mov32RR, kRegReg,               IS_BINARY_OP   | REG_DEF0_USE1,  { 0,             0, 0x8B, 0, 0, 0, 0, 0, false }, "Mov32RR", "!0r,!1r" },
+  { kX86Mov32RR, kRegReg,    IS_MOVE  | IS_BINARY_OP   | REG_DEF0_USE1,  { 0,             0, 0x8B, 0, 0, 0, 0, 0, false }, "Mov32RR", "!0r,!1r" },
   { kX86Mov32RM, kRegMem,    IS_LOAD  | IS_TERTIARY_OP | REG_DEF0_USE1,  { 0,             0, 0x8B, 0, 0, 0, 0, 0, false }, "Mov32RM", "!0r,[!1r+!2d]" },
   { kX86Mov32RA, kRegArray,  IS_LOAD  | IS_QUIN_OP     | REG_DEF0_USE12, { 0,             0, 0x8B, 0, 0, 0, 0, 0, false }, "Mov32RA", "!0r,[!1r+!2r<<!3d+!4d]" },
   { kX86Mov32RT, kRegThread, IS_LOAD  | IS_BINARY_OP   | REG_DEF0,       { THREAD_PREFIX, 0, 0x8B, 0, 0, 0, 0, 0, false }, "Mov32RT", "!0r,fs:[!1d]" },
@@ -201,15 +201,15 @@
   { kX86Mov32AI, kArrayImm,  IS_STORE | IS_QUIN_OP     | REG_USE01,      { 0,             0, 0xC7, 0, 0, 0, 0, 4, false }, "Mov32AI", "[!0r+!1r<<!2d+!3d],!4d" },
   { kX86Mov32TI, kThreadImm, IS_STORE | IS_BINARY_OP,                    { THREAD_PREFIX, 0, 0xC7, 0, 0, 0, 0, 4, false }, "Mov32TI", "fs:[!0d],!1d" },
 
-  { kX86Lea32RM, kRegMem, IS_TERTIARY_OP | IS_LOAD | REG_DEF0_USE1,      { 0,             0, 0x8D, 0, 0, 0, 0, 0, false }, "Lea32RM", "!0r,[!1r+!2d]" },
-  { kX86Lea32RA, kRegArray, IS_QUIN_OP | REG_DEF0_USE12,                 { 0,             0, 0x8D, 0, 0, 0, 0, 0, false }, "Lea32RA", "!0r,[!1r+!2r<<!3d+!4d]" },
+  { kX86Lea32RM, kRegMem,               IS_TERTIARY_OP | REG_DEF0_USE1,  { 0,             0, 0x8D, 0, 0, 0, 0, 0, false }, "Lea32RM", "!0r,[!1r+!2d]" },
+  { kX86Lea32RA, kRegArray,             IS_QUIN_OP | REG_DEF0_USE12,     { 0,             0, 0x8D, 0, 0, 0, 0, 0, false }, "Lea32RA", "!0r,[!1r+!2r<<!3d+!4d]" },
 
   { kX86Mov64MR, kMemReg,    IS_STORE | IS_TERTIARY_OP | REG_USE02,      { REX_W,             0, 0x89, 0, 0, 0, 0, 0, false }, "Mov64MR", "[!0r+!1d],!2r" },
   { kX86Mov64AR, kArrayReg,  IS_STORE | IS_QUIN_OP     | REG_USE014,     { REX_W,             0, 0x89, 0, 0, 0, 0, 0, false }, "Mov64AR", "[!0r+!1r<<!2d+!3d],!4r" },
   { kX86Movnti64MR, kMemReg,    IS_STORE | IS_TERTIARY_OP | REG_USE02,   { 0x0F,              0, 0xC3, 0, 0, 0, 0, 0, false }, "Movnti64MR", "[!0r+!1d],!2r" },
   { kX86Movnti64AR, kArrayReg,  IS_STORE | IS_QUIN_OP     | REG_USE014,  { 0x0F,              0, 0xC3, 0, 0, 0, 0, 0, false }, "Movnti64AR", "[!0r+!1r<<!2d+!3d],!4r" },
   { kX86Mov64TR, kThreadReg, IS_STORE | IS_BINARY_OP   | REG_USE1,       { THREAD_PREFIX, REX_W, 0x89, 0, 0, 0, 0, 0, false }, "Mov64TR", "fs:[!0d],!1r" },
-  { kX86Mov64RR, kRegReg,               IS_BINARY_OP   | REG_DEF0_USE1,  { REX_W,             0, 0x8B, 0, 0, 0, 0, 0, false }, "Mov64RR", "!0r,!1r" },
+  { kX86Mov64RR, kRegReg,    IS_MOVE  | IS_BINARY_OP   | REG_DEF0_USE1,  { REX_W,             0, 0x8B, 0, 0, 0, 0, 0, false }, "Mov64RR", "!0r,!1r" },
   { kX86Mov64RM, kRegMem,    IS_LOAD  | IS_TERTIARY_OP | REG_DEF0_USE1,  { REX_W,             0, 0x8B, 0, 0, 0, 0, 0, false }, "Mov64RM", "!0r,[!1r+!2d]" },
   { kX86Mov64RA, kRegArray,  IS_LOAD  | IS_QUIN_OP     | REG_DEF0_USE12, { REX_W,             0, 0x8B, 0, 0, 0, 0, 0, false }, "Mov64RA", "!0r,[!1r+!2r<<!3d+!4d]" },
   { kX86Mov64RT, kRegThread, IS_LOAD  | IS_BINARY_OP   | REG_DEF0,       { THREAD_PREFIX, REX_W, 0x8B, 0, 0, 0, 0, 0, false }, "Mov64RT", "!0r,fs:[!1d]" },
@@ -219,8 +219,8 @@
   { kX86Mov64AI, kArrayImm,  IS_STORE | IS_QUIN_OP     | REG_USE01,      { REX_W,             0, 0xC7, 0, 0, 0, 0, 4, false }, "Mov64AI", "[!0r+!1r<<!2d+!3d],!4d" },
   { kX86Mov64TI, kThreadImm, IS_STORE | IS_BINARY_OP,                    { THREAD_PREFIX, REX_W, 0xC7, 0, 0, 0, 0, 4, false }, "Mov64TI", "fs:[!0d],!1d" },
 
-  { kX86Lea64RM, kRegMem, IS_TERTIARY_OP | IS_LOAD | REG_DEF0_USE1,      { REX_W,             0, 0x8D, 0, 0, 0, 0, 0, false }, "Lea64RM", "!0r,[!1r+!2d]" },
-  { kX86Lea64RA, kRegArray, IS_QUIN_OP | REG_DEF0_USE12,                 { REX_W,             0, 0x8D, 0, 0, 0, 0, 0, false }, "Lea64RA", "!0r,[!1r+!2r<<!3d+!4d]" },
+  { kX86Lea64RM, kRegMem,               IS_TERTIARY_OP | REG_DEF0_USE1,  { REX_W,             0, 0x8D, 0, 0, 0, 0, 0, false }, "Lea64RM", "!0r,[!1r+!2d]" },
+  { kX86Lea64RA, kRegArray,             IS_QUIN_OP | REG_DEF0_USE12,     { REX_W,             0, 0x8D, 0, 0, 0, 0, 0, false }, "Lea64RA", "!0r,[!1r+!2r<<!3d+!4d]" },
 
   { kX86Cmov32RRC, kRegRegCond, IS_TERTIARY_OP | REG_DEF0_USE01 | USES_CCODES, { 0,     0, 0x0F, 0x40, 0, 0, 0, 0, false }, "Cmovcc32RR", "!2c !0r,!1r" },
   { kX86Cmov64RRC, kRegRegCond, IS_TERTIARY_OP | REG_DEF0_USE01 | USES_CCODES, { REX_W, 0, 0x0F, 0x40, 0, 0, 0, 0, false }, "Cmovcc64RR", "!2c !0r,!1r" },
@@ -444,14 +444,14 @@
   { kX86PslldRI, kRegImm, IS_BINARY_OP | REG_DEF0_USE0, { 0x66, 0, 0x0F, 0x72, 0, 6, 0, 1, false }, "PslldRI", "!0r,!1d" },
   { kX86PsllqRI, kRegImm, IS_BINARY_OP | REG_DEF0_USE0, { 0x66, 0, 0x0F, 0x73, 0, 6, 0, 1, false }, "PsllqRI", "!0r,!1d" },
 
-  { kX86Fild32M,  kMem,     IS_LOAD    | IS_UNARY_OP | REG_USE0 | USE_FP_STACK, { 0x0,  0,    0xDB, 0x00, 0, 0, 0, 0, false }, "Fild32M",  "[!0r,!1d]" },
-  { kX86Fild64M,  kMem,     IS_LOAD    | IS_UNARY_OP | REG_USE0 | USE_FP_STACK, { 0x0,  0,    0xDF, 0x00, 0, 5, 0, 0, false }, "Fild64M",  "[!0r,!1d]" },
-  { kX86Fld32M,   kMem,     IS_LOAD    | IS_UNARY_OP | REG_USE0 | USE_FP_STACK, { 0x0,  0,    0xD9, 0x00, 0, 0, 0, 0, false }, "Fld32M",   "[!0r,!1d]" },
-  { kX86Fld64M,   kMem,     IS_LOAD    | IS_UNARY_OP | REG_USE0 | USE_FP_STACK, { 0x0,  0,    0xDD, 0x00, 0, 0, 0, 0, false }, "Fld64M",   "[!0r,!1d]" },
-  { kX86Fstp32M,  kMem,     IS_STORE   | IS_UNARY_OP | REG_USE0 | USE_FP_STACK, { 0x0,  0,    0xD9, 0x00, 0, 3, 0, 0, false }, "Fstps32M", "[!0r,!1d]" },
-  { kX86Fstp64M,  kMem,     IS_STORE   | IS_UNARY_OP | REG_USE0 | USE_FP_STACK, { 0x0,  0,    0xDD, 0x00, 0, 3, 0, 0, false }, "Fstpd64M", "[!0r,!1d]" },
-  { kX86Fst32M,   kMem,     IS_STORE   | IS_UNARY_OP | REG_USE0 | USE_FP_STACK, { 0x0,  0,    0xD9, 0x00, 0, 2, 0, 0, false }, "Fsts32M",  "[!0r,!1d]" },
-  { kX86Fst64M,   kMem,     IS_STORE   | IS_UNARY_OP | REG_USE0 | USE_FP_STACK, { 0x0,  0,    0xDD, 0x00, 0, 2, 0, 0, false }, "Fstd64M",  "[!0r,!1d]" },
+  { kX86Fild32M,  kMem,     IS_LOAD    | IS_BINARY_OP | REG_USE0 | USE_FP_STACK, { 0x0,  0,    0xDB, 0x00, 0, 0, 0, 0, false }, "Fild32M",  "[!0r,!1d]" },
+  { kX86Fild64M,  kMem,     IS_LOAD    | IS_BINARY_OP | REG_USE0 | USE_FP_STACK, { 0x0,  0,    0xDF, 0x00, 0, 5, 0, 0, false }, "Fild64M",  "[!0r,!1d]" },
+  { kX86Fld32M,   kMem,     IS_LOAD    | IS_BINARY_OP | REG_USE0 | USE_FP_STACK, { 0x0,  0,    0xD9, 0x00, 0, 0, 0, 0, false }, "Fld32M",   "[!0r,!1d]" },
+  { kX86Fld64M,   kMem,     IS_LOAD    | IS_BINARY_OP | REG_USE0 | USE_FP_STACK, { 0x0,  0,    0xDD, 0x00, 0, 0, 0, 0, false }, "Fld64M",   "[!0r,!1d]" },
+  { kX86Fstp32M,  kMem,     IS_STORE   | IS_BINARY_OP | REG_USE0 | USE_FP_STACK, { 0x0,  0,    0xD9, 0x00, 0, 3, 0, 0, false }, "Fstps32M", "[!0r,!1d]" },
+  { kX86Fstp64M,  kMem,     IS_STORE   | IS_BINARY_OP | REG_USE0 | USE_FP_STACK, { 0x0,  0,    0xDD, 0x00, 0, 3, 0, 0, false }, "Fstpd64M", "[!0r,!1d]" },
+  { kX86Fst32M,   kMem,     IS_STORE   | IS_BINARY_OP | REG_USE0 | USE_FP_STACK, { 0x0,  0,    0xD9, 0x00, 0, 2, 0, 0, false }, "Fsts32M",  "[!0r,!1d]" },
+  { kX86Fst64M,   kMem,     IS_STORE   | IS_BINARY_OP | REG_USE0 | USE_FP_STACK, { 0x0,  0,    0xDD, 0x00, 0, 2, 0, 0, false }, "Fstd64M",  "[!0r,!1d]" },
   { kX86Fprem,    kNullary, NO_OPERAND | USE_FP_STACK,                          { 0xD9, 0,    0xF8, 0,    0, 0, 0, 0, false }, "Fprem64",  "" },
   { kX86Fucompp,  kNullary, NO_OPERAND | USE_FP_STACK,                          { 0xDA, 0,    0xE9, 0,    0, 0, 0, 0, false }, "Fucompp",  "" },
   { kX86Fstsw16R, kNullary, NO_OPERAND | REG_DEFA | USE_FP_STACK,               { 0x9B, 0xDF, 0xE0, 0,    0, 0, 0, 0, false }, "Fstsw16R", "ax" },
@@ -680,7 +680,8 @@
     }
     if (displacement != 0 || LowRegisterBits(raw_base) == rs_rBP.GetRegNum()) {
       // BP requires an explicit displacement, even when it's 0.
-      if (entry->opcode != kX86Lea32RA && entry->opcode != kX86Lea64RA) {
+      if (entry->opcode != kX86Lea32RA && entry->opcode != kX86Lea64RA &&
+          entry->opcode != kX86Lea32RM && entry->opcode != kX86Lea64RM) {
         DCHECK_NE(entry->flags & (IS_LOAD | IS_STORE), UINT64_C(0)) << entry->name;
       }
       size += IS_SIMM8(displacement) ? 1 : 4;
diff --git a/compiler/dex/quick/x86/codegen_x86.h b/compiler/dex/quick/x86/codegen_x86.h
index dd4d661..6020e70 100644
--- a/compiler/dex/quick/x86/codegen_x86.h
+++ b/compiler/dex/quick/x86/codegen_x86.h
@@ -497,6 +497,8 @@
   void MaskVectorRegister(X86OpCode opcode, RegStorage rs_src1, uint32_t m1, uint32_t m2,
                           uint32_t m3, uint32_t m4);
   void AppendOpcodeWithConst(X86OpCode opcode, int reg, MIR* mir);
+  virtual void LoadVectorRegister(RegStorage rs_dest, RegStorage rs_src, OpSize opsize,
+                                  int op_mov);
 
   static bool ProvidesFullMemoryBarrier(X86OpCode opcode);
 
@@ -914,7 +916,7 @@
    * @param bb Basic block containing instruction.
    * @param mir Instruction to analyze.
    */
-  void AnalyzeFPInstruction(int opcode, BasicBlock * bb, MIR *mir);
+  virtual void AnalyzeFPInstruction(int opcode, BasicBlock * bb, MIR *mir);
 
   /*
    * @brief Analyze one use of a double operand.
diff --git a/compiler/dex/quick/x86/target_x86.cc b/compiler/dex/quick/x86/target_x86.cc
index aadb41a..de11996 100755
--- a/compiler/dex/quick/x86/target_x86.cc
+++ b/compiler/dex/quick/x86/target_x86.cc
@@ -1124,37 +1124,51 @@
   LoadValueDirectFixed(rl_src, rs_rAX);
   LoadWordDisp(rs_rAX, mirror::Array::LengthOffset().Int32Value(), rs_rAX);
   LIR* src_bad_len  = nullptr;
+  LIR* src_bad_off = nullptr;
   LIR* srcPos_negative  = nullptr;
   if (!rl_srcPos.is_const) {
     LoadValueDirectFixed(rl_srcPos, tmp_reg);
     srcPos_negative  = OpCmpImmBranch(kCondLt, tmp_reg, 0, nullptr);
-    OpRegReg(kOpAdd, tmp_reg, rs_rDX);
-    src_bad_len  = OpCmpBranch(kCondLt, rs_rAX, tmp_reg, nullptr);
+    // src_pos < src_len
+    src_bad_off = OpCmpBranch(kCondLt, rs_rAX, tmp_reg, nullptr);
+    // src_len - src_pos < copy_len
+    OpRegRegReg(kOpSub, tmp_reg, rs_rAX, tmp_reg);
+    src_bad_len = OpCmpBranch(kCondLt, tmp_reg, rs_rDX, nullptr);
   } else {
     int32_t pos_val = mir_graph_->ConstantValue(rl_srcPos.orig_sreg);
     if (pos_val == 0) {
       src_bad_len  = OpCmpBranch(kCondLt, rs_rAX, rs_rDX, nullptr);
     } else {
-      OpRegRegImm(kOpAdd, tmp_reg,  rs_rDX, pos_val);
-      src_bad_len  = OpCmpBranch(kCondLt, rs_rAX, tmp_reg, nullptr);
+      // src_pos < src_len
+      src_bad_off = OpCmpImmBranch(kCondLt, rs_rAX, pos_val, nullptr);
+      // src_len - src_pos < copy_len
+      OpRegRegImm(kOpSub, tmp_reg, rs_rAX, pos_val);
+      src_bad_len = OpCmpBranch(kCondLt, tmp_reg, rs_rDX, nullptr);
     }
   }
   LIR* dstPos_negative = nullptr;
   LIR* dst_bad_len = nullptr;
+  LIR* dst_bad_off = nullptr;
   LoadValueDirectFixed(rl_dst, rs_rAX);
   LoadWordDisp(rs_rAX, mirror::Array::LengthOffset().Int32Value(), rs_rAX);
   if (!rl_dstPos.is_const) {
     LoadValueDirectFixed(rl_dstPos, tmp_reg);
     dstPos_negative = OpCmpImmBranch(kCondLt, tmp_reg, 0, nullptr);
-    OpRegRegReg(kOpAdd, tmp_reg, tmp_reg, rs_rDX);
-    dst_bad_len = OpCmpBranch(kCondLt, rs_rAX, tmp_reg, nullptr);
+    // dst_pos < dst_len
+    dst_bad_off = OpCmpBranch(kCondLt, rs_rAX, tmp_reg, nullptr);
+    // dst_len - dst_pos < copy_len
+    OpRegRegReg(kOpSub, tmp_reg, rs_rAX, tmp_reg);
+    dst_bad_len = OpCmpBranch(kCondLt, tmp_reg, rs_rDX, nullptr);
   } else {
     int32_t pos_val = mir_graph_->ConstantValue(rl_dstPos.orig_sreg);
     if (pos_val == 0) {
       dst_bad_len = OpCmpBranch(kCondLt, rs_rAX, rs_rDX, nullptr);
     } else {
-      OpRegRegImm(kOpAdd, tmp_reg,  rs_rDX, pos_val);
-      dst_bad_len = OpCmpBranch(kCondLt, rs_rAX, tmp_reg, nullptr);
+      // dst_pos < dst_len
+      dst_bad_off = OpCmpImmBranch(kCondLt, rs_rAX, pos_val, nullptr);
+      // dst_len - dst_pos < copy_len
+      OpRegRegImm(kOpSub, tmp_reg, rs_rAX, pos_val);
+      dst_bad_len = OpCmpBranch(kCondLt, tmp_reg, rs_rDX, nullptr);
     }
   }
   // Everything is checked now.
@@ -1198,14 +1212,19 @@
   src_null_branch->target = check_failed;
   if (srcPos_negative != nullptr)
     srcPos_negative ->target = check_failed;
+  if (src_bad_off != nullptr)
+    src_bad_off->target = check_failed;
   if (src_bad_len != nullptr)
     src_bad_len->target = check_failed;
   dst_null_branch->target = check_failed;
   if (dstPos_negative != nullptr)
     dstPos_negative->target = check_failed;
+  if (dst_bad_off != nullptr)
+    dst_bad_off->target = check_failed;
   if (dst_bad_len != nullptr)
     dst_bad_len->target = check_failed;
   AddIntrinsicSlowPath(info, launchpad_branch, return_point);
+  ClobberCallerSave();  // We must clobber everything because slow path will return here
   return true;
 }
 
@@ -1384,6 +1403,7 @@
   if (slowpath_branch != nullptr) {
     LIR *return_point = NewLIR0(kPseudoTargetLabel);
     AddIntrinsicSlowPath(info, slowpath_branch, return_point);
+    ClobberCallerSave();  // We must clobber everything because slow path will return here
   }
 
   StoreValue(rl_dest, rl_return);
@@ -2268,6 +2288,20 @@
   }
 }
 
+void X86Mir2Lir::LoadVectorRegister(RegStorage rs_dest, RegStorage rs_src,
+                                    OpSize opsize, int op_mov) {
+  if (!cu_->target64 && opsize == k64) {
+    // Logic assumes that longs are loaded in GP register pairs.
+    NewLIR2(kX86MovdxrRR, rs_dest.GetReg(), rs_src.GetLowReg());
+    RegStorage r_tmp = AllocTempDouble();
+    NewLIR2(kX86MovdxrRR, r_tmp.GetReg(), rs_src.GetHighReg());
+    NewLIR2(kX86PunpckldqRR, rs_dest.GetReg(), r_tmp.GetReg());
+    FreeTemp(r_tmp);
+  } else {
+    NewLIR2(op_mov, rs_dest.GetReg(), rs_src.GetReg());
+  }
+}
+
 void X86Mir2Lir::GenSetVector(BasicBlock *bb, MIR *mir) {
   DCHECK_EQ(mir->dalvikInsn.vC & 0xFFFF, 128U);
   OpSize opsize = static_cast<OpSize>(mir->dalvikInsn.vC >> 16);
@@ -2321,16 +2355,7 @@
   RegStorage reg_to_shuffle = rl_src.reg;
 
   // Load the value into the XMM register.
-  if (!cu_->target64 && opsize == k64) {
-    // Logic assumes that longs are loaded in GP register pairs.
-    NewLIR2(kX86MovdxrRR, rs_dest.GetReg(), reg_to_shuffle.GetLowReg());
-    RegStorage r_tmp = AllocTempDouble();
-    NewLIR2(kX86MovdxrRR, r_tmp.GetReg(), reg_to_shuffle.GetHighReg());
-    NewLIR2(kX86PunpckldqRR, rs_dest.GetReg(), r_tmp.GetReg());
-    FreeTemp(r_tmp);
-  } else {
-    NewLIR2(op_mov, rs_dest.GetReg(), reg_to_shuffle.GetReg());
-  }
+  LoadVectorRegister(rs_dest, reg_to_shuffle, opsize, op_mov);
 
   if (opsize == kSignedByte || opsize == kUnsignedByte) {
     // In the byte case, first duplicate it to be a word
diff --git a/compiler/optimizing/graph_visualizer.h b/compiler/optimizing/graph_visualizer.h
index 7cd74e9..6e2c6fd 100644
--- a/compiler/optimizing/graph_visualizer.h
+++ b/compiler/optimizing/graph_visualizer.h
@@ -25,8 +25,10 @@
 class DexCompilationUnit;
 class HGraph;
 
+// TODO: Create an analysis/optimization abstraction.
 static const char* kLivenessPassName = "liveness";
 static const char* kRegisterAllocatorPassName = "register";
+static const char* kGVNPassName = "gvn";
 
 /**
  * If enabled, emits compilation information suitable for the c1visualizer tool
diff --git a/compiler/optimizing/gvn.cc b/compiler/optimizing/gvn.cc
new file mode 100644
index 0000000..027b3d4
--- /dev/null
+++ b/compiler/optimizing/gvn.cc
@@ -0,0 +1,186 @@
+/*
+ * Copyright (C) 2014 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 "gvn.h"
+
+namespace art {
+
+void GlobalValueNumberer::Run() {
+  ComputeSideEffects();
+
+  sets_.Put(graph_->GetEntryBlock()->GetBlockId(), new (allocator_) ValueSet(allocator_));
+
+  // Do reverse post order to ensure the non back-edge predecessors of a block are
+  // visited before the block itself.
+  for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
+    VisitBasicBlock(it.Current());
+  }
+}
+
+void GlobalValueNumberer::UpdateLoopEffects(HLoopInformation* info, SideEffects effects) {
+  int id = info->GetHeader()->GetBlockId();
+  loop_effects_.Put(id, loop_effects_.Get(id).Union(effects));
+}
+
+void GlobalValueNumberer::ComputeSideEffects() {
+  if (kIsDebugBuild) {
+    for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
+      HBasicBlock* block = it.Current();
+      SideEffects effects = GetBlockEffects(block);
+      DCHECK(!effects.HasSideEffects() && !effects.HasDependencies());
+      if (block->IsLoopHeader()) {
+        effects = GetLoopEffects(block);
+        DCHECK(!effects.HasSideEffects() && !effects.HasDependencies());
+      }
+    }
+  }
+
+  // Do a post order visit to ensure we visit a loop header after its loop body.
+  for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
+    HBasicBlock* block = it.Current();
+
+    SideEffects effects = SideEffects::None();
+    // Update `effects` with the side effects of all instructions in this block.
+    for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
+      HInstruction* instruction = it.Current();
+      effects = effects.Union(instruction->GetSideEffects());
+      if (effects.HasAllSideEffects()) {
+        break;
+      }
+    }
+
+    block_effects_.Put(block->GetBlockId(), effects);
+
+    if (block->IsLoopHeader()) {
+      // The side effects of the loop header are part of the loop.
+      UpdateLoopEffects(block->GetLoopInformation(), effects);
+      HBasicBlock* pre_header = block->GetLoopInformation()->GetPreHeader();
+      if (pre_header->IsInLoop()) {
+        // Update the side effects of the outer loop with the side effects of the inner loop.
+        // Note that this works because we know all the blocks of the inner loop are visited
+        // before the loop header of the outer loop.
+        UpdateLoopEffects(pre_header->GetLoopInformation(), GetLoopEffects(block));
+      }
+    } else if (block->IsInLoop()) {
+      // Update the side effects of the loop with the side effects of this block.
+      UpdateLoopEffects(block->GetLoopInformation(), effects);
+    }
+  }
+}
+
+SideEffects GlobalValueNumberer::GetLoopEffects(HBasicBlock* block) const {
+  DCHECK(block->IsLoopHeader());
+  return loop_effects_.Get(block->GetBlockId());
+}
+
+SideEffects GlobalValueNumberer::GetBlockEffects(HBasicBlock* block) const {
+  return block_effects_.Get(block->GetBlockId());
+}
+
+static bool IsLoopExit(HBasicBlock* block, HBasicBlock* successor) {
+  HLoopInformation* block_info = block->GetLoopInformation();
+  HLoopInformation* other_info = successor->GetLoopInformation();
+  return block_info != other_info && (other_info == nullptr || block_info->IsIn(*other_info));
+}
+
+void GlobalValueNumberer::VisitBasicBlock(HBasicBlock* block) {
+  if (kIsDebugBuild) {
+    // Check that all non back-edge processors have been visited.
+    for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) {
+      HBasicBlock* predecessor = block->GetPredecessors().Get(i);
+      DCHECK(visited_.Get(predecessor->GetBlockId())
+             || (block->GetLoopInformation() != nullptr
+                 && (block->GetLoopInformation()->GetBackEdges().Get(0) == predecessor)));
+    }
+    visited_.Put(block->GetBlockId(), true);
+  }
+
+  ValueSet* set = sets_.Get(block->GetBlockId());
+
+  if (block->IsLoopHeader()) {
+    set->Kill(GetLoopEffects(block));
+  }
+
+  HInstruction* current = block->GetFirstInstruction();
+  while (current != nullptr) {
+    set->Kill(current->GetSideEffects());
+    // Save the next instruction in case `current` is removed from the graph.
+    HInstruction* next = current->GetNext();
+    if (current->CanBeMoved()) {
+      HInstruction* existing = set->Lookup(current);
+      if (existing != nullptr) {
+        current->ReplaceWith(existing);
+        current->GetBlock()->RemoveInstruction(current);
+      } else {
+        set->Add(current);
+      }
+    }
+    current = next;
+  }
+
+  if (block == graph_->GetEntryBlock()) {
+    // The entry block should only accumulate constant instructions, and
+    // the builder puts constants only in the entry block.
+    // Therefore, there is no need to propagate the value set to the next block.
+    DCHECK_EQ(block->GetDominatedBlocks().Size(), 1u);
+    HBasicBlock* dominated = block->GetDominatedBlocks().Get(0);
+    sets_.Put(dominated->GetBlockId(), new (allocator_) ValueSet(allocator_));
+    return;
+  }
+
+  // Copy the value set to dominated blocks. We can re-use
+  // the current set for the last dominated block because we are done visiting
+  // this block.
+  for (size_t i = 0, e = block->GetDominatedBlocks().Size(); i < e; ++i) {
+    HBasicBlock* dominated = block->GetDominatedBlocks().Get(i);
+    sets_.Put(dominated->GetBlockId(), i == e - 1 ? set : set->Copy());
+  }
+
+  // Kill instructions in the value set of each successor. If the successor
+  // is a loop exit, then we use the side effects of the loop. If not, we use
+  // the side effects of this block.
+  for (size_t i = 0, e = block->GetSuccessors().Size(); i < e; ++i) {
+    HBasicBlock* successor = block->GetSuccessors().Get(i);
+    if (successor->IsLoopHeader()
+        && successor->GetLoopInformation()->GetBackEdges().Get(0) == block) {
+      // In case of a back edge, we already have visited the loop header.
+      // We should not update its value set, because the last dominated block
+      // of the loop header uses the same value set.
+      DCHECK(visited_.Get(successor->GetBlockId()));
+      continue;
+    }
+    DCHECK(!visited_.Get(successor->GetBlockId()));
+    ValueSet* successor_set = sets_.Get(successor->GetBlockId());
+    // The dominator sets the set, and we are guaranteed to have visited it already.
+    DCHECK(successor_set != nullptr);
+
+    // If this block dominates this successor there is nothing to do.
+    // Also if the set is empty, there is nothing to kill.
+    if (successor->GetDominator() != block && !successor_set->IsEmpty()) {
+      if (block->IsInLoop() && IsLoopExit(block, successor)) {
+        // All instructions killed in the loop must be killed for a loop exit.
+        SideEffects effects = GetLoopEffects(block->GetLoopInformation()->GetHeader());
+        sets_.Get(successor->GetBlockId())->Kill(effects);
+      } else {
+        // Following block (that might be in the same loop).
+        // Just kill instructions based on this block's side effects.
+        sets_.Get(successor->GetBlockId())->Kill(GetBlockEffects(block));
+      }
+    }
+  }
+}
+
+}  // namespace art
diff --git a/compiler/optimizing/gvn.h b/compiler/optimizing/gvn.h
new file mode 100644
index 0000000..41b3ceb
--- /dev/null
+++ b/compiler/optimizing/gvn.h
@@ -0,0 +1,230 @@
+/*
+ * Copyright (C) 2014 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_OPTIMIZING_GVN_H_
+#define ART_COMPILER_OPTIMIZING_GVN_H_
+
+#include <gtest/gtest.h>
+#include "nodes.h"
+
+namespace art {
+
+/**
+ * A node in the collision list of a ValueSet. Encodes the instruction,
+ * the hash code, and the next node in the collision list.
+ */
+class ValueSetNode : public ArenaObject {
+ public:
+  ValueSetNode(HInstruction* instruction, size_t hash_code, ValueSetNode* next)
+      : instruction_(instruction), hash_code_(hash_code), next_(next) {}
+
+  size_t GetHashCode() const { return hash_code_; }
+  HInstruction* GetInstruction() const { return instruction_; }
+  ValueSetNode* GetNext() const { return next_; }
+  void SetNext(ValueSetNode* node) { next_ = node; }
+
+ private:
+  HInstruction* const instruction_;
+  const size_t hash_code_;
+  ValueSetNode* next_;
+
+  DISALLOW_COPY_AND_ASSIGN(ValueSetNode);
+};
+
+/**
+ * A ValueSet holds instructions that can replace other instructions. It is updated
+ * through the `Add` method, and the `Kill` method. The `Kill` method removes
+ * instructions that are affected by the given side effect.
+ *
+ * The `Lookup` method returns an equivalent instruction to the given instruction
+ * if there is one in the set. In GVN, we would say those instructions have the
+ * same "number".
+ */
+class ValueSet : public ArenaObject {
+ public:
+  explicit ValueSet(ArenaAllocator* allocator)
+      : allocator_(allocator), number_of_entries_(0), collisions_(nullptr) {
+    for (size_t i = 0; i < kDefaultNumberOfEntries; ++i) {
+      table_[i] = nullptr;
+    }
+  }
+
+  // Adds an instruction in the set.
+  void Add(HInstruction* instruction) {
+    DCHECK(Lookup(instruction) == nullptr);
+    size_t hash_code = instruction->ComputeHashCode();
+    size_t index = hash_code % kDefaultNumberOfEntries;
+    if (table_[index] == nullptr) {
+      table_[index] = instruction;
+    } else {
+      collisions_ = new (allocator_) ValueSetNode(instruction, hash_code, collisions_);
+    }
+    ++number_of_entries_;
+  }
+
+  // If in the set, returns an equivalent instruction to the given instruction. Returns
+  // null otherwise.
+  HInstruction* Lookup(HInstruction* instruction) const {
+    size_t hash_code = instruction->ComputeHashCode();
+    size_t index = hash_code % kDefaultNumberOfEntries;
+    HInstruction* existing = table_[index];
+    if (existing != nullptr && existing->Equals(instruction)) {
+      return existing;
+    }
+
+    for (ValueSetNode* node = collisions_; node != nullptr; node = node->GetNext()) {
+      if (node->GetHashCode() == hash_code) {
+        existing = node->GetInstruction();
+        if (existing->Equals(instruction)) {
+          return existing;
+        }
+      }
+    }
+    return nullptr;
+  }
+
+  // Removes all instructions in the set that are affected by the given side effects.
+  void Kill(SideEffects side_effects) {
+    for (size_t i = 0; i < kDefaultNumberOfEntries; ++i) {
+      HInstruction* instruction = table_[i];
+      if (instruction != nullptr && instruction->GetSideEffects().DependsOn(side_effects)) {
+        table_[i] = nullptr;
+        --number_of_entries_;
+      }
+    }
+
+    ValueSetNode* current = collisions_;
+    ValueSetNode* previous = nullptr;
+    while (current != nullptr) {
+      HInstruction* instruction = current->GetInstruction();
+      if (instruction->GetSideEffects().DependsOn(side_effects)) {
+        if (previous == nullptr) {
+          collisions_ = current->GetNext();
+        } else {
+          previous->SetNext(current->GetNext());
+        }
+        --number_of_entries_;
+      } else {
+        previous = current;
+      }
+      current = current->GetNext();
+    }
+  }
+
+  // Returns a copy of this set.
+  ValueSet* Copy() const {
+    ValueSet* copy = new (allocator_) ValueSet(allocator_);
+
+    for (size_t i = 0; i < kDefaultNumberOfEntries; ++i) {
+      copy->table_[i] = table_[i];
+    }
+
+    // Note that the order will be inverted in the copy. This is fine, as the order is not
+    // relevant for a ValueSet.
+    for (ValueSetNode* node = collisions_; node != nullptr; node = node->GetNext()) {
+      copy->collisions_ = new (allocator_) ValueSetNode(
+          node->GetInstruction(), node->GetHashCode(), copy->collisions_);
+    }
+
+    copy->number_of_entries_ = number_of_entries_;
+    return copy;
+  }
+
+  bool IsEmpty() const { return number_of_entries_ == 0; }
+  size_t GetNumberOfEntries() const { return number_of_entries_; }
+
+ private:
+  static constexpr size_t kDefaultNumberOfEntries = 8;
+
+  ArenaAllocator* const allocator_;
+
+  // The number of entries in the set.
+  size_t number_of_entries_;
+
+  // The internal implementation of the set. It uses a combination of a hash code based
+  // fixed-size list, and a linked list to handle hash code collisions.
+  // TODO: Tune the fixed size list original size, and support growing it.
+  ValueSetNode* collisions_;
+  HInstruction* table_[kDefaultNumberOfEntries];
+
+  DISALLOW_COPY_AND_ASSIGN(ValueSet);
+};
+
+/**
+ * Optimization phase that removes redundant instruction.
+ */
+class GlobalValueNumberer : public ValueObject {
+ public:
+  GlobalValueNumberer(ArenaAllocator* allocator, HGraph* graph)
+      : allocator_(allocator),
+        graph_(graph),
+        block_effects_(allocator, graph->GetBlocks().Size()),
+        loop_effects_(allocator, graph->GetBlocks().Size()),
+        sets_(allocator, graph->GetBlocks().Size()),
+        visited_(allocator, graph->GetBlocks().Size()) {
+    size_t number_of_blocks = graph->GetBlocks().Size();
+    block_effects_.SetSize(number_of_blocks);
+    loop_effects_.SetSize(number_of_blocks);
+    sets_.SetSize(number_of_blocks);
+    visited_.SetSize(number_of_blocks);
+
+    for (size_t i = 0; i < number_of_blocks; ++i) {
+      block_effects_.Put(i, SideEffects::None());
+      loop_effects_.Put(i, SideEffects::None());
+    }
+  }
+
+  void Run();
+
+ private:
+  // Per-block GVN. Will also update the ValueSet of the dominated and
+  // successor blocks.
+  void VisitBasicBlock(HBasicBlock* block);
+
+  // Compute side effects of individual blocks and loops. The GVN algorithm
+  // will use these side effects to update the ValueSet of individual blocks.
+  void ComputeSideEffects();
+
+  void UpdateLoopEffects(HLoopInformation* info, SideEffects effects);
+  SideEffects GetLoopEffects(HBasicBlock* block) const;
+  SideEffects GetBlockEffects(HBasicBlock* block) const;
+
+  ArenaAllocator* const allocator_;
+  HGraph* const graph_;
+
+  // Side effects of individual blocks, that is the union of the side effects
+  // of the instructions in the block.
+  GrowableArray<SideEffects> block_effects_;
+
+  // Side effects of loops, that is the union of the side effects of the
+  // blocks contained in that loop.
+  GrowableArray<SideEffects> loop_effects_;
+
+  // ValueSet for blocks. Initially null, but for an individual block they
+  // are allocated and populated by the dominator, and updated by all blocks
+  // in the path from the dominator to the block.
+  GrowableArray<ValueSet*> sets_;
+
+  // Mark visisted blocks. Only used for debugging.
+  GrowableArray<bool> visited_;
+
+  FRIEND_TEST(GVNTest, LoopSideEffects);
+  DISALLOW_COPY_AND_ASSIGN(GlobalValueNumberer);
+};
+
+}  // namespace art
+
+#endif  // ART_COMPILER_OPTIMIZING_GVN_H_
diff --git a/compiler/optimizing/gvn_test.cc b/compiler/optimizing/gvn_test.cc
new file mode 100644
index 0000000..ad6e338
--- /dev/null
+++ b/compiler/optimizing/gvn_test.cc
@@ -0,0 +1,294 @@
+/*
+ * Copyright (C) 2014 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 "builder.h"
+#include "gvn.h"
+#include "nodes.h"
+#include "optimizing_unit_test.h"
+#include "utils/arena_allocator.h"
+
+#include "gtest/gtest.h"
+
+namespace art {
+
+TEST(GVNTest, LocalFieldElimination) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+
+  HGraph* graph = new (&allocator) HGraph(&allocator);
+  HBasicBlock* entry = new (&allocator) HBasicBlock(graph);
+  graph->AddBlock(entry);
+  graph->SetEntryBlock(entry);
+  HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimNot);
+  entry->AddInstruction(parameter);
+
+  HBasicBlock* block = new (&allocator) HBasicBlock(graph);
+  graph->AddBlock(block);
+  entry->AddSuccessor(block);
+
+  block->AddInstruction(
+      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimNot, MemberOffset(42)));
+  block->AddInstruction(
+      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimNot, MemberOffset(42)));
+  HInstruction* to_remove = block->GetLastInstruction();
+  block->AddInstruction(
+      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimNot, MemberOffset(43)));
+  HInstruction* different_offset = block->GetLastInstruction();
+  // Kill the value.
+  block->AddInstruction(new (&allocator) HInstanceFieldSet(
+      parameter, parameter, Primitive::kPrimNot, MemberOffset(42)));
+  block->AddInstruction(
+      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimNot, MemberOffset(42)));
+  HInstruction* use_after_kill = block->GetLastInstruction();
+  block->AddInstruction(new (&allocator) HExit());
+
+  ASSERT_EQ(to_remove->GetBlock(), block);
+  ASSERT_EQ(different_offset->GetBlock(), block);
+  ASSERT_EQ(use_after_kill->GetBlock(), block);
+
+  graph->BuildDominatorTree();
+  graph->TransformToSSA();
+  GlobalValueNumberer(&allocator, graph).Run();
+
+  ASSERT_TRUE(to_remove->GetBlock() == nullptr);
+  ASSERT_EQ(different_offset->GetBlock(), block);
+  ASSERT_EQ(use_after_kill->GetBlock(), block);
+}
+
+TEST(GVNTest, GlobalFieldElimination) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+
+  HGraph* graph = new (&allocator) HGraph(&allocator);
+  HBasicBlock* entry = new (&allocator) HBasicBlock(graph);
+  graph->AddBlock(entry);
+  graph->SetEntryBlock(entry);
+  HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimNot);
+  entry->AddInstruction(parameter);
+
+  HBasicBlock* block = new (&allocator) HBasicBlock(graph);
+  graph->AddBlock(block);
+  entry->AddSuccessor(block);
+  block->AddInstruction(
+      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, MemberOffset(42)));
+
+  block->AddInstruction(new (&allocator) HIf(block->GetLastInstruction()));
+  HBasicBlock* then = new (&allocator) HBasicBlock(graph);
+  HBasicBlock* else_ = new (&allocator) HBasicBlock(graph);
+  HBasicBlock* join = new (&allocator) HBasicBlock(graph);
+  graph->AddBlock(then);
+  graph->AddBlock(else_);
+  graph->AddBlock(join);
+
+  block->AddSuccessor(then);
+  block->AddSuccessor(else_);
+  then->AddSuccessor(join);
+  else_->AddSuccessor(join);
+
+  then->AddInstruction(
+      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, MemberOffset(42)));
+  then->AddInstruction(new (&allocator) HGoto());
+  else_->AddInstruction(
+      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, MemberOffset(42)));
+  else_->AddInstruction(new (&allocator) HGoto());
+  join->AddInstruction(
+      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, MemberOffset(42)));
+  join->AddInstruction(new (&allocator) HExit());
+
+  graph->BuildDominatorTree();
+  graph->TransformToSSA();
+  GlobalValueNumberer(&allocator, graph).Run();
+
+  // Check that all field get instructions have been GVN'ed.
+  ASSERT_TRUE(then->GetFirstInstruction()->IsGoto());
+  ASSERT_TRUE(else_->GetFirstInstruction()->IsGoto());
+  ASSERT_TRUE(join->GetFirstInstruction()->IsExit());
+}
+
+TEST(GVNTest, LoopFieldElimination) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+
+  HGraph* graph = new (&allocator) HGraph(&allocator);
+  HBasicBlock* entry = new (&allocator) HBasicBlock(graph);
+  graph->AddBlock(entry);
+  graph->SetEntryBlock(entry);
+
+  HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimNot);
+  entry->AddInstruction(parameter);
+
+  HBasicBlock* block = new (&allocator) HBasicBlock(graph);
+  graph->AddBlock(block);
+  entry->AddSuccessor(block);
+  block->AddInstruction(
+      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, MemberOffset(42)));
+  block->AddInstruction(new (&allocator) HGoto());
+
+  HBasicBlock* loop_header = new (&allocator) HBasicBlock(graph);
+  HBasicBlock* loop_body = new (&allocator) HBasicBlock(graph);
+  HBasicBlock* exit = new (&allocator) HBasicBlock(graph);
+
+  graph->AddBlock(loop_header);
+  graph->AddBlock(loop_body);
+  graph->AddBlock(exit);
+  block->AddSuccessor(loop_header);
+  loop_header->AddSuccessor(loop_body);
+  loop_header->AddSuccessor(exit);
+  loop_body->AddSuccessor(loop_header);
+
+  loop_header->AddInstruction(
+      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, MemberOffset(42)));
+  HInstruction* field_get_in_loop_header = loop_header->GetLastInstruction();
+  loop_header->AddInstruction(new (&allocator) HIf(block->GetLastInstruction()));
+
+  // Kill inside the loop body to prevent field gets inside the loop header
+  // and the body to be GVN'ed.
+  loop_body->AddInstruction(new (&allocator) HInstanceFieldSet(
+      parameter, parameter, Primitive::kPrimNot, MemberOffset(42)));
+  HInstruction* field_set = loop_body->GetLastInstruction();
+  loop_body->AddInstruction(
+      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, MemberOffset(42)));
+  HInstruction* field_get_in_loop_body = loop_body->GetLastInstruction();
+  loop_body->AddInstruction(new (&allocator) HGoto());
+
+  exit->AddInstruction(
+      new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, MemberOffset(42)));
+  HInstruction* field_get_in_exit = exit->GetLastInstruction();
+  exit->AddInstruction(new (&allocator) HExit());
+
+  ASSERT_EQ(field_get_in_loop_header->GetBlock(), loop_header);
+  ASSERT_EQ(field_get_in_loop_body->GetBlock(), loop_body);
+  ASSERT_EQ(field_get_in_exit->GetBlock(), exit);
+
+  graph->BuildDominatorTree();
+  graph->TransformToSSA();
+  graph->FindNaturalLoops();
+  GlobalValueNumberer(&allocator, graph).Run();
+
+  // Check that all field get instructions are still there.
+  ASSERT_EQ(field_get_in_loop_header->GetBlock(), loop_header);
+  ASSERT_EQ(field_get_in_loop_body->GetBlock(), loop_body);
+  // The exit block is dominated by the loop header, whose field get
+  // does not get killed by the loop flags.
+  ASSERT_TRUE(field_get_in_exit->GetBlock() == nullptr);
+
+  // Now remove the field set, and check that all field get instructions have been GVN'ed.
+  loop_body->RemoveInstruction(field_set);
+  GlobalValueNumberer(&allocator, graph).Run();
+
+  ASSERT_TRUE(field_get_in_loop_header->GetBlock() == nullptr);
+  ASSERT_TRUE(field_get_in_loop_body->GetBlock() == nullptr);
+  ASSERT_TRUE(field_get_in_exit->GetBlock() == nullptr);
+}
+
+// Test that inner loops affect the side effects of the outer loop.
+TEST(GVNTest, LoopSideEffects) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+
+  HGraph* graph = new (&allocator) HGraph(&allocator);
+  HBasicBlock* entry = new (&allocator) HBasicBlock(graph);
+  graph->AddBlock(entry);
+  graph->SetEntryBlock(entry);
+
+  HBasicBlock* outer_loop_header = new (&allocator) HBasicBlock(graph);
+  HBasicBlock* outer_loop_body = new (&allocator) HBasicBlock(graph);
+  HBasicBlock* outer_loop_exit = new (&allocator) HBasicBlock(graph);
+  HBasicBlock* inner_loop_header = new (&allocator) HBasicBlock(graph);
+  HBasicBlock* inner_loop_body = new (&allocator) HBasicBlock(graph);
+  HBasicBlock* inner_loop_exit = new (&allocator) HBasicBlock(graph);
+
+  graph->AddBlock(outer_loop_header);
+  graph->AddBlock(outer_loop_body);
+  graph->AddBlock(outer_loop_exit);
+  graph->AddBlock(inner_loop_header);
+  graph->AddBlock(inner_loop_body);
+  graph->AddBlock(inner_loop_exit);
+
+  entry->AddSuccessor(outer_loop_header);
+  outer_loop_header->AddSuccessor(outer_loop_body);
+  outer_loop_header->AddSuccessor(outer_loop_exit);
+  outer_loop_body->AddSuccessor(inner_loop_header);
+  inner_loop_header->AddSuccessor(inner_loop_body);
+  inner_loop_header->AddSuccessor(inner_loop_exit);
+  inner_loop_body->AddSuccessor(inner_loop_header);
+  inner_loop_exit->AddSuccessor(outer_loop_header);
+
+  HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimBoolean);
+  entry->AddInstruction(parameter);
+  entry->AddInstruction(new (&allocator) HGoto());
+  outer_loop_header->AddInstruction(new (&allocator) HIf(parameter));
+  outer_loop_body->AddInstruction(new (&allocator) HGoto());
+  inner_loop_header->AddInstruction(new (&allocator) HIf(parameter));
+  inner_loop_body->AddInstruction(new (&allocator) HGoto());
+  inner_loop_exit->AddInstruction(new (&allocator) HGoto());
+  outer_loop_exit->AddInstruction(new (&allocator) HExit());
+
+  graph->BuildDominatorTree();
+  graph->TransformToSSA();
+  graph->FindNaturalLoops();
+
+  ASSERT_TRUE(inner_loop_header->GetLoopInformation()->IsIn(
+      *outer_loop_header->GetLoopInformation()));
+
+  // Check that the loops don't have side effects.
+  {
+    // Make one block with a side effect.
+    entry->AddInstruction(new (&allocator) HInstanceFieldSet(
+        parameter, parameter, Primitive::kPrimNot, MemberOffset(42)));
+
+    GlobalValueNumberer gvn(&allocator, graph);
+    gvn.Run();
+
+    ASSERT_TRUE(gvn.GetBlockEffects(entry).HasSideEffects());
+    ASSERT_FALSE(gvn.GetLoopEffects(outer_loop_header).HasSideEffects());
+    ASSERT_FALSE(gvn.GetLoopEffects(inner_loop_header).HasSideEffects());
+  }
+
+  // Check that the side effects of the outer loop does not affect the inner loop.
+  {
+    outer_loop_body->InsertInstructionBefore(
+        new (&allocator) HInstanceFieldSet(
+            parameter, parameter, Primitive::kPrimNot, MemberOffset(42)),
+        outer_loop_body->GetLastInstruction());
+
+    GlobalValueNumberer gvn(&allocator, graph);
+    gvn.Run();
+
+    ASSERT_TRUE(gvn.GetBlockEffects(entry).HasSideEffects());
+    ASSERT_TRUE(gvn.GetBlockEffects(outer_loop_body).HasSideEffects());
+    ASSERT_TRUE(gvn.GetLoopEffects(outer_loop_header).HasSideEffects());
+    ASSERT_FALSE(gvn.GetLoopEffects(inner_loop_header).HasSideEffects());
+  }
+
+  // Check that the side effects of the inner loop affects the outer loop.
+  {
+    outer_loop_body->RemoveInstruction(outer_loop_body->GetFirstInstruction());
+    inner_loop_body->InsertInstructionBefore(
+        new (&allocator) HInstanceFieldSet(
+            parameter, parameter, Primitive::kPrimNot, MemberOffset(42)),
+        inner_loop_body->GetLastInstruction());
+
+    GlobalValueNumberer gvn(&allocator, graph);
+    gvn.Run();
+
+    ASSERT_TRUE(gvn.GetBlockEffects(entry).HasSideEffects());
+    ASSERT_FALSE(gvn.GetBlockEffects(outer_loop_body).HasSideEffects());
+    ASSERT_TRUE(gvn.GetLoopEffects(outer_loop_header).HasSideEffects());
+    ASSERT_TRUE(gvn.GetLoopEffects(inner_loop_header).HasSideEffects());
+  }
+}
+}  // namespace art
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 376d1af..1a24677 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -124,6 +124,7 @@
   // dominator of the block. We can then start visiting its successors.
   if (visits->Get(block->GetBlockId()) ==
       block->GetPredecessors().Size() - block->NumberOfBackEdges()) {
+    block->GetDominator()->AddDominatedBlock(block);
     reverse_post_order_.Add(block);
     for (size_t i = 0; i < block->GetSuccessors().Size(); i++) {
       VisitBlockForDominatorTree(block->GetSuccessors().Get(i), block, visits);
@@ -543,6 +544,7 @@
 
 bool HInstruction::Equals(HInstruction* other) const {
   if (!InstructionTypeEquals(other)) return false;
+  DCHECK_EQ(GetKind(), other->GetKind());
   if (!InstructionDataEquals(other)) return false;
   if (GetType() != other->GetType()) return false;
   if (InputCount() != other->InputCount()) return false;
@@ -550,6 +552,7 @@
   for (size_t i = 0, e = InputCount(); i < e; ++i) {
     if (InputAt(i) != other->InputAt(i)) return false;
   }
+  DCHECK_EQ(ComputeHashCode(), other->ComputeHashCode());
   return true;
 }
 
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index d98d2ad..af173c8 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -38,6 +38,7 @@
 static const int kDefaultNumberOfBlocks = 8;
 static const int kDefaultNumberOfSuccessors = 2;
 static const int kDefaultNumberOfPredecessors = 2;
+static const int kDefaultNumberOfDominatedBlocks = 1;
 static const int kDefaultNumberOfBackEdges = 1;
 
 enum IfCondition {
@@ -272,6 +273,7 @@
         successors_(graph->GetArena(), kDefaultNumberOfSuccessors),
         loop_information_(nullptr),
         dominator_(nullptr),
+        dominated_blocks_(graph->GetArena(), kDefaultNumberOfDominatedBlocks),
         block_id_(-1),
         lifetime_start_(kNoLifetime),
         lifetime_end_(kNoLifetime) {}
@@ -284,6 +286,10 @@
     return successors_;
   }
 
+  const GrowableArray<HBasicBlock*>& GetDominatedBlocks() const {
+    return dominated_blocks_;
+  }
+
   void AddBackEdge(HBasicBlock* back_edge) {
     if (loop_information_ == nullptr) {
       loop_information_ = new (graph_->GetArena()) HLoopInformation(this, graph_);
@@ -299,6 +305,7 @@
 
   HBasicBlock* GetDominator() const { return dominator_; }
   void SetDominator(HBasicBlock* dominator) { dominator_ = dominator; }
+  void AddDominatedBlock(HBasicBlock* block) { dominated_blocks_.Add(block); }
 
   int NumberOfBackEdges() const {
     return loop_information_ == nullptr
@@ -418,6 +425,7 @@
   HInstructionList phis_;
   HLoopInformation* loop_information_;
   HBasicBlock* dominator_;
+  GrowableArray<HBasicBlock*> dominated_blocks_;
   int block_id_;
   size_t lifetime_start_;
   size_t lifetime_end_;
@@ -473,6 +481,7 @@
 #undef FORWARD_DECLARATION
 
 #define DECLARE_INSTRUCTION(type)                                       \
+  virtual InstructionKind GetKind() const { return k##type; }           \
   virtual const char* DebugName() const { return #type; }               \
   virtual const H##type* As##type() const OVERRIDE { return this; }     \
   virtual H##type* As##type() OVERRIDE { return this; }                 \
@@ -504,6 +513,8 @@
 // Represents the side effects an instruction may have.
 class SideEffects : public ValueObject {
  public:
+  SideEffects() : flags_(0) {}
+
   static SideEffects None() {
     return SideEffects(0);
   }
@@ -521,11 +532,31 @@
     return SideEffects(((1 << count) - 1) << kFlagChangesCount);
   }
 
+  SideEffects Union(SideEffects other) const {
+    return SideEffects(flags_ | other.flags_);
+  }
+
   bool HasSideEffects() const {
     size_t all_bits_set = (1 << kFlagChangesCount) - 1;
     return (flags_ & all_bits_set) != 0;
   }
 
+  bool HasAllSideEffects() const {
+    size_t all_bits_set = (1 << kFlagChangesCount) - 1;
+    return all_bits_set == (flags_ & all_bits_set);
+  }
+
+  bool DependsOn(SideEffects other) const {
+    size_t depends_flags = other.ComputeDependsFlags();
+    return (flags_ & depends_flags) != 0;
+  }
+
+  bool HasDependencies() const {
+    int count = kFlagDependsOnCount - kFlagChangesCount;
+    size_t all_bits_set = (1 << count) - 1;
+    return ((flags_ >> kFlagChangesCount) & all_bits_set) != 0;
+  }
+
  private:
   static constexpr int kFlagChangesSomething = 0;
   static constexpr int kFlagChangesCount = kFlagChangesSomething + 1;
@@ -533,10 +564,13 @@
   static constexpr int kFlagDependsOnSomething = kFlagChangesCount;
   static constexpr int kFlagDependsOnCount = kFlagDependsOnSomething + 1;
 
- private:
   explicit SideEffects(size_t flags) : flags_(flags) {}
 
-  const size_t flags_;
+  size_t ComputeDependsFlags() const {
+    return flags_ << kFlagChangesCount;
+  }
+
+  size_t flags_;
 };
 
 class HInstruction : public ArenaObject {
@@ -557,6 +591,12 @@
 
   virtual ~HInstruction() {}
 
+#define DECLARE_KIND(type) k##type,
+  enum InstructionKind {
+    FOR_EACH_INSTRUCTION(DECLARE_KIND)
+  };
+#undef DECLARE_KIND
+
   HInstruction* GetNext() const { return next_; }
   HInstruction* GetPrevious() const { return previous_; }
 
@@ -659,6 +699,18 @@
   // 2) Their inputs are identical.
   bool Equals(HInstruction* other) const;
 
+  virtual InstructionKind GetKind() const = 0;
+
+  virtual size_t ComputeHashCode() const {
+    size_t result = GetKind();
+    for (size_t i = 0, e = InputCount(); i < e; ++i) {
+      result = (result * 31) + InputAt(i)->GetId();
+    }
+    return result;
+  }
+
+  SideEffects GetSideEffects() const { return side_effects_; }
+
   size_t GetLifetimePosition() const { return lifetime_position_; }
   void SetLifetimePosition(size_t position) { lifetime_position_ = position; }
   LiveInterval* GetLiveInterval() const { return live_interval_; }
@@ -1258,6 +1310,8 @@
     return other->AsIntConstant()->value_ == value_;
   }
 
+  virtual size_t ComputeHashCode() const { return GetValue(); }
+
   DECLARE_INSTRUCTION(IntConstant);
 
  private:
@@ -1276,6 +1330,8 @@
     return other->AsLongConstant()->value_ == value_;
   }
 
+  virtual size_t ComputeHashCode() const { return static_cast<size_t>(GetValue()); }
+
   DECLARE_INSTRUCTION(LongConstant);
 
  private:
@@ -1545,6 +1601,10 @@
     return other_offset == GetFieldOffset().SizeValue();
   }
 
+  virtual size_t ComputeHashCode() const {
+    return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue();
+  }
+
   MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); }
   Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); }
 
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 3ce8e77..702eba1 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -25,6 +25,7 @@
 #include "driver/compiler_driver.h"
 #include "driver/dex_compilation_unit.h"
 #include "graph_visualizer.h"
+#include "gvn.h"
 #include "nodes.h"
 #include "register_allocator.h"
 #include "ssa_phi_elimination.h"
@@ -260,6 +261,8 @@
 
     SsaRedundantPhiElimination(graph).Run();
     SsaDeadPhiElimination(graph).Run();
+    GlobalValueNumberer(graph->GetArena(), graph).Run();
+    visualizer.DumpGraph(kGVNPassName);
 
     SsaLivenessAnalysis liveness(*graph, codegen);
     liveness.Analyze();
@@ -300,6 +303,9 @@
     graph->TransformToSSA();
     visualizer.DumpGraph("ssa");
     graph->FindNaturalLoops();
+    SsaRedundantPhiElimination(graph).Run();
+    SsaDeadPhiElimination(graph).Run();
+    GlobalValueNumberer(graph->GetArena(), graph).Run();
     SsaLivenessAnalysis liveness(*graph, codegen);
     liveness.Analyze();
     visualizer.DumpGraph(kLivenessPassName);
diff --git a/compiler/utils/assembler_thumb_test.cc b/compiler/utils/assembler_thumb_test.cc
index 891a287..e3a9580 100644
--- a/compiler/utils/assembler_thumb_test.cc
+++ b/compiler/utils/assembler_thumb_test.cc
@@ -116,6 +116,19 @@
     std::string subdir = toolsdir + std::string("/") + std::string(entry->d_name);
     size_t eabi = subdir.find(TOOL_PREFIX);
     if (eabi != std::string::npos) {
+      // Check if "bin/{as,objcopy,objdump}" exist under this folder.
+      struct stat exec_st;
+      std::string exec_path;
+      exec_path = subdir + "/bin/" + TOOL_PREFIX + "as";
+      if (stat(exec_path.c_str(), &exec_st) != 0)
+        continue;
+      exec_path = subdir + "/bin/" + TOOL_PREFIX + "objcopy";
+      if (stat(exec_path.c_str(), &exec_st) != 0)
+        continue;
+      exec_path = subdir + "/bin/" + TOOL_PREFIX + "objdump";
+      if (stat(exec_path.c_str(), &exec_st) != 0)
+        continue;
+
       std::string suffix = subdir.substr(eabi + strlen(TOOL_PREFIX));
       double version = strtod(suffix.c_str(), nullptr);
       if (version > maxversion) {
diff --git a/oatdump/oatdump.cc b/oatdump/oatdump.cc
index bac3c33..888f2d2 100644
--- a/oatdump/oatdump.cc
+++ b/oatdump/oatdump.cc
@@ -53,10 +53,12 @@
 #include "runtime.h"
 #include "safe_map.h"
 #include "scoped_thread_state_change.h"
+#include "ScopedLocalRef.h"
 #include "thread_list.h"
 #include "verifier/dex_gc_map.h"
 #include "verifier/method_verifier.h"
 #include "vmap_table.h"
+#include "well_known_classes.h"
 
 namespace art {
 
@@ -105,7 +107,6 @@
           "  --no-disassemble may be used to disable disassembly.\n"
           "      Example: --no-disassemble\n"
           "\n");
-  exit(EXIT_FAILURE);
 }
 
 const char* image_roots_descriptions_[] = {
@@ -343,18 +344,21 @@
                    bool dump_raw_gc_map,
                    bool dump_vmap,
                    bool disassemble_code,
-                   bool absolute_addresses)
+                   bool absolute_addresses,
+                   Handle<mirror::ClassLoader>* class_loader)
     : dump_raw_mapping_table_(dump_raw_mapping_table),
       dump_raw_gc_map_(dump_raw_gc_map),
       dump_vmap_(dump_vmap),
       disassemble_code_(disassemble_code),
-      absolute_addresses_(absolute_addresses) {}
+      absolute_addresses_(absolute_addresses),
+      class_loader_(class_loader) {}
 
   const bool dump_raw_mapping_table_;
   const bool dump_raw_gc_map_;
   const bool dump_vmap_;
   const bool disassemble_code_;
   const bool absolute_addresses_;
+  Handle<mirror::ClassLoader>* class_loader_;
 };
 
 class OatDumper {
@@ -366,6 +370,7 @@
       disassembler_(Disassembler::Create(oat_file_.GetOatHeader().GetInstructionSet(),
                                          new DisassemblerOptions(options_->absolute_addresses_,
                                                                  oat_file.Begin()))) {
+    CHECK(options_->class_loader_ != nullptr);
     AddAllOffsets();
   }
 
@@ -780,10 +785,7 @@
                                     oat_method.GetVmapTableOffsetOffset());
         success = false;
       } else if (options_->dump_vmap_) {
-        if (oat_method.GetNativeGcMap() != nullptr) {
-          // The native GC map is null for methods compiled with the optimizing compiler.
-          DumpVmap(*indent2_os, oat_method);
-        }
+        DumpVmap(*indent2_os, oat_method);
       }
     }
     {
@@ -894,6 +896,12 @@
   }
 
   void DumpVmap(std::ostream& os, const OatFile::OatMethod& oat_method) {
+    // If the native GC map is null, then this method has been compiled with the
+    // optimizing compiler. The optimizing compiler currently outputs its stack map
+    // in the vmap table, and the code below does not work with such a stack map.
+    if (oat_method.GetNativeGcMap() == nullptr) {
+      return;
+    }
     const uint8_t* raw_table = oat_method.GetVmapTable();
     if (raw_table != nullptr) {
       const VmapTable vmap_table(raw_table);
@@ -1170,9 +1178,10 @@
       StackHandleScope<1> hs(soa.Self());
       Handle<mirror::DexCache> dex_cache(
           hs.NewHandle(Runtime::Current()->GetClassLinker()->FindDexCache(*dex_file)));
+      DCHECK(options_->class_loader_ != nullptr);
       return verifier::MethodVerifier::VerifyMethodAndDump(soa.Self(), os, dex_method_idx, dex_file,
                                                            dex_cache,
-                                                           NullHandle<mirror::ClassLoader>(),
+                                                           *options_->class_loader_,
                                                            &class_def, code_item,
                                                            NullHandle<mirror::ArtMethod>(),
                                                            method_access_flags);
@@ -1955,122 +1964,10 @@
   DISALLOW_COPY_AND_ASSIGN(ImageDumper);
 };
 
-static int oatdump(int argc, char** argv) {
-  InitLogging(argv);
+static NoopCompilerCallbacks callbacks;
 
-  // Skip over argv[0].
-  argv++;
-  argc--;
-
-  if (argc == 0) {
-    fprintf(stderr, "No arguments specified\n");
-    usage();
-  }
-
-  const char* oat_filename = nullptr;
-  const char* image_location = nullptr;
-  const char* boot_image_location = nullptr;
-  InstructionSet instruction_set = kRuntimeISA;
-  std::string elf_filename_prefix;
-  std::ostream* os = &std::cout;
-  std::unique_ptr<std::ofstream> out;
-  std::string output_name;
-  bool dump_raw_mapping_table = false;
-  bool dump_raw_gc_map = false;
-  bool dump_vmap = true;
-  bool disassemble_code = true;
-  bool symbolize = false;
-
-  for (int i = 0; i < argc; i++) {
-    const StringPiece option(argv[i]);
-    if (option.starts_with("--oat-file=")) {
-      oat_filename = option.substr(strlen("--oat-file=")).data();
-    } else if (option.starts_with("--image=")) {
-      image_location = option.substr(strlen("--image=")).data();
-    } else if (option.starts_with("--boot-image=")) {
-      boot_image_location = option.substr(strlen("--boot-image=")).data();
-    } else if (option.starts_with("--instruction-set=")) {
-      StringPiece instruction_set_str = option.substr(strlen("--instruction-set=")).data();
-      if (instruction_set_str == "arm") {
-        instruction_set = kThumb2;
-      } else if (instruction_set_str == "arm64") {
-        instruction_set = kArm64;
-      } else if (instruction_set_str == "mips") {
-        instruction_set = kMips;
-      } else if (instruction_set_str == "x86") {
-        instruction_set = kX86;
-      } else if (instruction_set_str == "x86_64") {
-        instruction_set = kX86_64;
-      }
-    } else if (option =="--dump:raw_mapping_table") {
-      dump_raw_mapping_table = true;
-    } else if (option == "--dump:raw_gc_map") {
-      dump_raw_gc_map = true;
-    } else if (option == "--no-dump:vmap") {
-      dump_vmap = false;
-    } else if (option == "--no-disassemble") {
-      disassemble_code = false;
-    } else if (option.starts_with("--output=")) {
-      output_name = option.substr(strlen("--output=")).ToString();
-      const char* filename = output_name.c_str();
-      out.reset(new std::ofstream(filename));
-      if (!out->good()) {
-        fprintf(stderr, "Failed to open output filename %s\n", filename);
-        usage();
-      }
-      os = out.get();
-    } else if (option.starts_with("--symbolize=")) {
-      oat_filename = option.substr(strlen("--symbolize=")).data();
-      symbolize = true;
-    } else {
-      fprintf(stderr, "Unknown argument %s\n", option.data());
-      usage();
-    }
-  }
-
-  if (image_location == nullptr && oat_filename == nullptr) {
-    fprintf(stderr, "Either --image or --oat must be specified\n");
-    return EXIT_FAILURE;
-  }
-
-  if (image_location != nullptr && oat_filename != nullptr) {
-    fprintf(stderr, "Either --image or --oat must be specified but not both\n");
-    return EXIT_FAILURE;
-  }
-
-  // If we are only doing the oat file, disable absolute_addresses. Keep them for image dumping.
-  bool absolute_addresses = (oat_filename == nullptr);
-  std::unique_ptr<OatDumperOptions> oat_dumper_options(new OatDumperOptions(dump_raw_mapping_table,
-                                                                            dump_raw_gc_map,
-                                                                            dump_vmap,
-                                                                            disassemble_code,
-                                                                            absolute_addresses));
-  if (oat_filename != nullptr) {
-    std::string error_msg;
-    OatFile* oat_file =
-        OatFile::Open(oat_filename, oat_filename, nullptr, false, &error_msg);
-    if (oat_file == nullptr) {
-      fprintf(stderr, "Failed to open oat file from '%s': %s\n", oat_filename, error_msg.c_str());
-      return EXIT_FAILURE;
-    }
-    if (symbolize) {
-      OatSymbolizer oat_symbolizer(oat_file, output_name);
-      if (!oat_symbolizer.Init()) {
-        fprintf(stderr, "Failed to initialize symbolizer\n");
-        return EXIT_FAILURE;
-      }
-      if (!oat_symbolizer.Symbolize()) {
-        fprintf(stderr, "Failed to symbolize\n");
-        return EXIT_FAILURE;
-      }
-    } else {
-      OatDumper oat_dumper(*oat_file, oat_dumper_options.release());
-      bool success = oat_dumper.Dump(*os);
-      return (success) ? EXIT_SUCCESS : EXIT_FAILURE;
-    }
-    return EXIT_SUCCESS;
-  }
-
+static Runtime* StartRuntime(const char* boot_image_location, const char* image_location,
+                             InstructionSet instruction_set) {
   RuntimeOptions options;
   std::string image_option;
   std::string oat_option;
@@ -2078,7 +1975,6 @@
   std::string boot_oat_option;
 
   // We are more like a compiler than a run-time. We don't want to execute code.
-  NoopCompilerCallbacks callbacks;
   options.push_back(std::make_pair("compilercallbacks", &callbacks));
 
   if (boot_image_location != nullptr) {
@@ -2097,14 +1993,24 @@
 
   if (!Runtime::Create(options, false)) {
     fprintf(stderr, "Failed to create runtime\n");
-    return EXIT_FAILURE;
+    return nullptr;
   }
-  std::unique_ptr<Runtime> runtime(Runtime::Current());
+
   // Runtime::Create acquired the mutator_lock_ that is normally given away when we Runtime::Start,
   // give it away now and then switch to a more manageable ScopedObjectAccess.
   Thread::Current()->TransitionFromRunnableToSuspended(kNative);
+
+  return Runtime::Current();
+}
+
+static int DumpImage(Runtime* runtime, const char* image_location, OatDumperOptions* options,
+                     std::ostream* os) {
+  // Dumping the image, no explicit class loader.
+  NullHandle<mirror::ClassLoader> null_class_loader;
+  options->class_loader_ = &null_class_loader;
+
   ScopedObjectAccess soa(Thread::Current());
-  gc::Heap* heap = Runtime::Current()->GetHeap();
+  gc::Heap* heap = runtime->GetHeap();
   gc::space::ImageSpace* image_space = heap->GetImageSpace();
   CHECK(image_space != nullptr);
   const ImageHeader& image_header = image_space->GetImageHeader();
@@ -2112,11 +2018,227 @@
     fprintf(stderr, "Invalid image header %s\n", image_location);
     return EXIT_FAILURE;
   }
-  ImageDumper image_dumper(os, *image_space, image_header, oat_dumper_options.release());
+  ImageDumper image_dumper(os, *image_space, image_header, options);
   bool success = image_dumper.Dump();
   return (success) ? EXIT_SUCCESS : EXIT_FAILURE;
 }
 
+static int DumpOatWithRuntime(Runtime* runtime, OatFile* oat_file, OatDumperOptions* options,
+                              std::ostream* os) {
+  CHECK(runtime != nullptr && oat_file != nullptr && options != nullptr);
+
+  Thread* self = Thread::Current();
+  CHECK(self != nullptr);
+  // Need well-known-classes.
+  WellKnownClasses::Init(self->GetJniEnv());
+
+  // Need to register dex files to get a working dex cache.
+  ScopedObjectAccess soa(self);
+  ClassLinker* class_linker = runtime->GetClassLinker();
+  class_linker->RegisterOatFile(oat_file);
+  std::vector<const DexFile*> dex_files;
+  for (const OatFile::OatDexFile* odf : oat_file->GetOatDexFiles()) {
+    std::string error_msg;
+    const DexFile* dex_file = odf->OpenDexFile(&error_msg);
+    CHECK(dex_file != nullptr) << error_msg;
+    class_linker->RegisterDexFile(*dex_file);
+    dex_files.push_back(dex_file);
+  }
+
+  // Need a class loader.
+  soa.Env()->AllocObject(WellKnownClasses::dalvik_system_PathClassLoader);
+  ScopedLocalRef<jobject> class_loader_local(soa.Env(),
+      soa.Env()->AllocObject(WellKnownClasses::dalvik_system_PathClassLoader));
+  jobject class_loader = soa.Env()->NewGlobalRef(class_loader_local.get());
+  // Fake that we're a compiler.
+  runtime->SetCompileTimeClassPath(class_loader, dex_files);
+
+  // Use the class loader while dumping.
+  StackHandleScope<1> scope(self);
+  Handle<mirror::ClassLoader> loader_handle = scope.NewHandle(
+      soa.Decode<mirror::ClassLoader*>(class_loader));
+  options->class_loader_ = &loader_handle;
+
+  OatDumper oat_dumper(*oat_file, options);
+  bool success = oat_dumper.Dump(*os);
+  return (success) ? EXIT_SUCCESS : EXIT_FAILURE;
+}
+
+static int DumpOatWithoutRuntime(OatFile* oat_file, OatDumperOptions* options, std::ostream* os) {
+  // No image = no class loader.
+  NullHandle<mirror::ClassLoader> null_class_loader;
+  options->class_loader_ = &null_class_loader;
+
+  OatDumper oat_dumper(*oat_file, options);
+  bool success = oat_dumper.Dump(*os);
+  return (success) ? EXIT_SUCCESS : EXIT_FAILURE;
+}
+
+static int DumpOat(Runtime* runtime, const char* oat_filename, OatDumperOptions* options,
+                   std::ostream* os) {
+  std::string error_msg;
+  OatFile* oat_file = OatFile::Open(oat_filename, oat_filename, nullptr, false, &error_msg);
+  if (oat_file == nullptr) {
+    fprintf(stderr, "Failed to open oat file from '%s': %s\n", oat_filename, error_msg.c_str());
+    return EXIT_FAILURE;
+  }
+
+  if (runtime != nullptr) {
+    return DumpOatWithRuntime(runtime, oat_file, options, os);
+  } else {
+    return DumpOatWithoutRuntime(oat_file, options, os);
+  }
+}
+
+static int SymbolizeOat(const char* oat_filename, std::string& output_name) {
+  std::string error_msg;
+  OatFile* oat_file = OatFile::Open(oat_filename, oat_filename, nullptr, false, &error_msg);
+  if (oat_file == nullptr) {
+    fprintf(stderr, "Failed to open oat file from '%s': %s\n", oat_filename, error_msg.c_str());
+    return EXIT_FAILURE;
+  }
+
+  OatSymbolizer oat_symbolizer(oat_file, output_name);
+  if (!oat_symbolizer.Init()) {
+    fprintf(stderr, "Failed to initialize symbolizer\n");
+    return EXIT_FAILURE;
+  }
+  if (!oat_symbolizer.Symbolize()) {
+    fprintf(stderr, "Failed to symbolize\n");
+    return EXIT_FAILURE;
+  }
+
+  return EXIT_SUCCESS;
+}
+
+struct OatdumpArgs {
+  bool Parse(int argc, char** argv) {
+    // Skip over argv[0].
+    argv++;
+    argc--;
+
+    if (argc == 0) {
+      fprintf(stderr, "No arguments specified\n");
+      usage();
+      return false;
+    }
+
+    for (int i = 0; i < argc; i++) {
+      const StringPiece option(argv[i]);
+      if (option.starts_with("--oat-file=")) {
+        oat_filename_ = option.substr(strlen("--oat-file=")).data();
+      } else if (option.starts_with("--image=")) {
+        image_location_ = option.substr(strlen("--image=")).data();
+      } else if (option.starts_with("--boot-image=")) {
+        boot_image_location_ = option.substr(strlen("--boot-image=")).data();
+      } else if (option.starts_with("--instruction-set=")) {
+        StringPiece instruction_set_str = option.substr(strlen("--instruction-set=")).data();
+        instruction_set_ = GetInstructionSetFromString(instruction_set_str.data());
+        if (instruction_set_ == kNone) {
+          fprintf(stderr, "Unsupported instruction set %s\n", instruction_set_str.data());
+          usage();
+          return false;
+        }
+      } else if (option =="--dump:raw_mapping_table") {
+        dump_raw_mapping_table_ = true;
+      } else if (option == "--dump:raw_gc_map") {
+        dump_raw_gc_map_ = true;
+      } else if (option == "--no-dump:vmap") {
+        dump_vmap_ = false;
+      } else if (option == "--no-disassemble") {
+        disassemble_code_ = false;
+      } else if (option.starts_with("--output=")) {
+        output_name_ = option.substr(strlen("--output=")).ToString();
+        const char* filename = output_name_.c_str();
+        out_.reset(new std::ofstream(filename));
+        if (!out_->good()) {
+          fprintf(stderr, "Failed to open output filename %s\n", filename);
+          usage();
+          return false;
+        }
+        os_ = out_.get();
+      } else if (option.starts_with("--symbolize=")) {
+        oat_filename_ = option.substr(strlen("--symbolize=")).data();
+        symbolize_ = true;
+      } else {
+        fprintf(stderr, "Unknown argument %s\n", option.data());
+        usage();
+        return false;
+      }
+    }
+
+    if (image_location_ == nullptr && oat_filename_ == nullptr) {
+      fprintf(stderr, "Either --image or --oat must be specified\n");
+      return false;
+    }
+
+    if (image_location_ != nullptr && oat_filename_ != nullptr) {
+      fprintf(stderr, "Either --image or --oat must be specified but not both\n");
+      return false;
+    }
+
+    return true;
+  }
+
+  const char* oat_filename_ = nullptr;
+  const char* image_location_ = nullptr;
+  const char* boot_image_location_ = nullptr;
+  InstructionSet instruction_set_ = kRuntimeISA;
+  std::string elf_filename_prefix_;
+  std::ostream* os_ = &std::cout;
+  std::unique_ptr<std::ofstream> out_;
+  std::string output_name_;
+  bool dump_raw_mapping_table_ = false;
+  bool dump_raw_gc_map_ = false;
+  bool dump_vmap_ = true;
+  bool disassemble_code_ = true;
+  bool symbolize_ = false;
+};
+
+static int oatdump(int argc, char** argv) {
+  InitLogging(argv);
+
+  OatdumpArgs args;
+  if (!args.Parse(argc, argv)) {
+    return EXIT_FAILURE;
+  }
+
+  // If we are only doing the oat file, disable absolute_addresses. Keep them for image dumping.
+  bool absolute_addresses = (args.oat_filename_ == nullptr);
+
+  std::unique_ptr<OatDumperOptions> oat_dumper_options(new OatDumperOptions(
+      args.dump_raw_mapping_table_,
+      args.dump_raw_gc_map_,
+      args.dump_vmap_,
+      args.disassemble_code_,
+      absolute_addresses,
+      nullptr));
+
+  std::unique_ptr<Runtime> runtime;
+  if ((args.boot_image_location_ != nullptr || args.image_location_ != nullptr) &&
+      !args.symbolize_) {
+    // If we have a boot image option, try to start the runtime; except when just symbolizing.
+    runtime.reset(StartRuntime(args.boot_image_location_,
+                               args.image_location_,
+                               args.instruction_set_));
+  }
+
+  if (args.oat_filename_ != nullptr) {
+    if (args.symbolize_) {
+      return SymbolizeOat(args.oat_filename_, args.output_name_);
+    } else {
+      return DumpOat(runtime.get(), args.oat_filename_, oat_dumper_options.release(), args.os_);
+    }
+  }
+
+  if (runtime.get() == nullptr) {
+    // We need the runtime when printing an image.
+    return EXIT_FAILURE;
+  }
+
+  return DumpImage(runtime.get(), args.image_location_, oat_dumper_options.release(), args.os_);
+}
+
 }  // namespace art
 
 int main(int argc, char** argv) {
diff --git a/patchoat/patchoat.cc b/patchoat/patchoat.cc
index f89a4f7..50b4ece 100644
--- a/patchoat/patchoat.cc
+++ b/patchoat/patchoat.cc
@@ -79,9 +79,10 @@
 
   bool have_android_data = false;
   bool dalvik_cache_exists = false;
+  bool is_global_cache = false;
   std::string dalvik_cache;
   GetDalvikCache(GetInstructionSetString(isa), false, &dalvik_cache,
-                 &have_android_data, &dalvik_cache_exists);
+                 &have_android_data, &dalvik_cache_exists, &is_global_cache);
 
   std::string cache_filename;
   if (have_android_data && dalvik_cache_exists) {
@@ -986,9 +987,11 @@
     std::string cache_filename;
     bool has_cache = false;
     bool has_android_data_unused = false;
+    bool is_global_cache = false;
     if (!gc::space::ImageSpace::FindImageFilename(patched_image_location.c_str(), isa,
                                                   &system_filename, &has_system, &cache_filename,
-                                                  &has_android_data_unused, &has_cache)) {
+                                                  &has_android_data_unused, &has_cache,
+                                                  &is_global_cache)) {
       Usage("Unable to determine image file for location %s", patched_image_location.c_str());
     }
     if (has_cache) {
diff --git a/runtime/class_linker.cc b/runtime/class_linker.cc
index 1686c27..cb0fe0a 100644
--- a/runtime/class_linker.cc
+++ b/runtime/class_linker.cc
@@ -1323,8 +1323,9 @@
   std::string dalvik_cache;
   bool have_android_data = false;
   bool have_dalvik_cache = false;
+  bool is_global_cache = false;
   GetDalvikCache(GetInstructionSetString(kRuntimeISA), false, &dalvik_cache,
-                 &have_android_data, &have_dalvik_cache);
+                 &have_android_data, &have_dalvik_cache, &is_global_cache);
   std::string cache_filename;
   if (have_dalvik_cache) {
     cache_filename = GetDalvikCacheFilenameOrDie(dex_location.c_str(), dalvik_cache.c_str());
diff --git a/runtime/debugger.cc b/runtime/debugger.cc
index 02064be..b1b157a 100644
--- a/runtime/debugger.cc
+++ b/runtime/debugger.cc
@@ -845,7 +845,9 @@
 }
 
 std::string Dbg::GetClassName(mirror::Class* klass) {
-  DCHECK(klass != nullptr);
+  if (klass == nullptr) {
+    return "NULL";
+  }
   std::string temp;
   return DescriptorToName(klass->GetDescriptor(&temp));
 }
@@ -1466,6 +1468,9 @@
 }
 
 bool Dbg::MatchType(mirror::Class* event_class, JDWP::RefTypeId class_id) {
+  if (event_class == nullptr) {
+    return false;
+  }
   JDWP::JdwpError error;
   mirror::Class* expected_class = DecodeClass(class_id, &error);
   CHECK(expected_class != nullptr);
@@ -1490,7 +1495,7 @@
 void Dbg::SetJdwpLocation(JDWP::JdwpLocation* location, mirror::ArtMethod* m, uint32_t dex_pc)
     SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
   if (m == nullptr) {
-    memset(&location, 0, sizeof(*location));
+    memset(location, 0, sizeof(*location));
   } else {
     mirror::Class* c = m->GetDeclaringClass();
     location->type_tag = GetTypeTag(c);
@@ -1502,11 +1507,18 @@
 
 std::string Dbg::GetMethodName(JDWP::MethodId method_id) {
   mirror::ArtMethod* m = FromMethodId(method_id);
+  if (m == nullptr) {
+    return "NULL";
+  }
   return m->GetName();
 }
 
 std::string Dbg::GetFieldName(JDWP::FieldId field_id) {
-  return FromFieldId(field_id)->GetName();
+  mirror::ArtField* f = FromFieldId(field_id);
+  if (f == nullptr) {
+    return "NULL";
+  }
+  return f->GetName();
 }
 
 /*
@@ -3154,6 +3166,8 @@
     // should never be null. We could just check we never encounter this case.
     return false;
   }
+  // Note: method verifier may cause thread suspension.
+  self->AssertThreadSuspensionIsAllowable();
   StackHandleScope<3> hs(self);
   mirror::Class* declaring_class = m->GetDeclaringClass();
   Handle<mirror::DexCache> dex_cache(hs.NewHandle(declaring_class->GetDexCache()));
@@ -3179,20 +3193,18 @@
 // Sanity checks all existing breakpoints on the same method.
 static void SanityCheckExistingBreakpoints(mirror::ArtMethod* m, bool need_full_deoptimization)
     SHARED_LOCKS_REQUIRED(Locks::mutator_lock_, Locks::breakpoint_lock_) {
-  if (kIsDebugBuild) {
-    for (const Breakpoint& breakpoint : gBreakpoints) {
-      CHECK_EQ(need_full_deoptimization, breakpoint.NeedFullDeoptimization());
-    }
-    if (need_full_deoptimization) {
-      // We should have deoptimized everything but not "selectively" deoptimized this method.
-      CHECK(Runtime::Current()->GetInstrumentation()->AreAllMethodsDeoptimized());
-      CHECK(!Runtime::Current()->GetInstrumentation()->IsDeoptimized(m));
-    } else {
-      // We should have "selectively" deoptimized this method.
-      // Note: while we have not deoptimized everything for this method, we may have done it for
-      // another event.
-      CHECK(Runtime::Current()->GetInstrumentation()->IsDeoptimized(m));
-    }
+  for (const Breakpoint& breakpoint : gBreakpoints) {
+    CHECK_EQ(need_full_deoptimization, breakpoint.NeedFullDeoptimization());
+  }
+  if (need_full_deoptimization) {
+    // We should have deoptimized everything but not "selectively" deoptimized this method.
+    CHECK(Runtime::Current()->GetInstrumentation()->AreAllMethodsDeoptimized());
+    CHECK(!Runtime::Current()->GetInstrumentation()->IsDeoptimized(m));
+  } else {
+    // We should have "selectively" deoptimized this method.
+    // Note: while we have not deoptimized everything for this method, we may have done it for
+    // another event.
+    CHECK(Runtime::Current()->GetInstrumentation()->IsDeoptimized(m));
   }
 }
 
@@ -3203,12 +3215,17 @@
   mirror::ArtMethod* m = FromMethodId(location->method_id);
   DCHECK(m != nullptr) << "No method for method id " << location->method_id;
 
-  WriterMutexLock mu(self, *Locks::breakpoint_lock_);
-  const Breakpoint* const existing_breakpoint = FindFirstBreakpointForMethod(m);
+  const Breakpoint* existing_breakpoint;
+  {
+    ReaderMutexLock mu(self, *Locks::breakpoint_lock_);
+    existing_breakpoint = FindFirstBreakpointForMethod(m);
+  }
   bool need_full_deoptimization;
   if (existing_breakpoint == nullptr) {
     // There is no breakpoint on this method yet: we need to deoptimize. If this method may be
     // inlined, we deoptimize everything; otherwise we deoptimize only this method.
+    // Note: IsMethodPossiblyInlined goes into the method verifier and may cause thread suspension.
+    // Therefore we must not hold any lock when we call it.
     need_full_deoptimization = IsMethodPossiblyInlined(self, m);
     if (need_full_deoptimization) {
       req->SetKind(DeoptimizationRequest::kFullDeoptimization);
@@ -3223,12 +3240,18 @@
     req->SetMethod(nullptr);
 
     need_full_deoptimization = existing_breakpoint->NeedFullDeoptimization();
-    SanityCheckExistingBreakpoints(m, need_full_deoptimization);
+    if (kIsDebugBuild) {
+      ReaderMutexLock mu(self, *Locks::breakpoint_lock_);
+      SanityCheckExistingBreakpoints(m, need_full_deoptimization);
+    }
   }
 
-  gBreakpoints.push_back(Breakpoint(m, location->dex_pc, need_full_deoptimization));
-  VLOG(jdwp) << "Set breakpoint #" << (gBreakpoints.size() - 1) << ": "
-             << gBreakpoints[gBreakpoints.size() - 1];
+  {
+    WriterMutexLock mu(self, *Locks::breakpoint_lock_);
+    gBreakpoints.push_back(Breakpoint(m, location->dex_pc, need_full_deoptimization));
+    VLOG(jdwp) << "Set breakpoint #" << (gBreakpoints.size() - 1) << ": "
+               << gBreakpoints[gBreakpoints.size() - 1];
+  }
 }
 
 // Uninstalls a breakpoint at the specified location. Also indicates through the deoptimization
@@ -3263,7 +3286,9 @@
     // There is at least one breakpoint for this method: we don't need to undeoptimize.
     req->SetKind(DeoptimizationRequest::kNothing);
     req->SetMethod(nullptr);
-    SanityCheckExistingBreakpoints(m, need_full_deoptimization);
+    if (kIsDebugBuild) {
+      SanityCheckExistingBreakpoints(m, need_full_deoptimization);
+    }
   }
 }
 
diff --git a/runtime/dex_instruction_list.h b/runtime/dex_instruction_list.h
index 6a9976a..05214a4 100644
--- a/runtime/dex_instruction_list.h
+++ b/runtime/dex_instruction_list.h
@@ -122,7 +122,7 @@
   V(0x65, SGET_CHAR, "sget-char", k21c, true, kFieldRef, kContinue | kThrow | kLoad | kRegBFieldOrConstant, kVerifyRegA | kVerifyRegBField) \
   V(0x66, SGET_SHORT, "sget-short", k21c, true, kFieldRef, kContinue | kThrow | kLoad | kRegBFieldOrConstant, kVerifyRegA | kVerifyRegBField) \
   V(0x67, SPUT, "sput", k21c, false, kFieldRef, kContinue | kThrow | kStore | kRegBFieldOrConstant, kVerifyRegA | kVerifyRegBField) \
-  V(0x68, SPUT_WIDE, "sput-wide", k21c, false, kFieldRef, kContinue | kThrow | kStore | kRegBFieldOrConstant, kVerifyRegA | kVerifyRegBField) \
+  V(0x68, SPUT_WIDE, "sput-wide", k21c, false, kFieldRef, kContinue | kThrow | kStore | kRegBFieldOrConstant, kVerifyRegAWide | kVerifyRegBField) \
   V(0x69, SPUT_OBJECT, "sput-object", k21c, false, kFieldRef, kContinue | kThrow | kStore | kRegBFieldOrConstant, kVerifyRegA | kVerifyRegBField) \
   V(0x6A, SPUT_BOOLEAN, "sput-boolean", k21c, false, kFieldRef, kContinue | kThrow | kStore | kRegBFieldOrConstant, kVerifyRegA | kVerifyRegBField) \
   V(0x6B, SPUT_BYTE, "sput-byte", k21c, false, kFieldRef, kContinue | kThrow | kStore | kRegBFieldOrConstant, kVerifyRegA | kVerifyRegBField) \
diff --git a/runtime/gc/space/image_space.cc b/runtime/gc/space/image_space.cc
index 41c34c9..353d00c 100644
--- a/runtime/gc/space/image_space.cc
+++ b/runtime/gc/space/image_space.cc
@@ -125,7 +125,7 @@
   }
   // We should clean up so we are more likely to have room for the image.
   if (Runtime::Current()->IsZygote()) {
-    LOG(INFO) << "Pruning dalvik-cache since we are relocating an image and will need to recompile";
+    LOG(INFO) << "Pruning dalvik-cache since we are generating an image and will need to recompile";
     PruneDexCache(image_isa);
   }
 
@@ -177,7 +177,8 @@
                                    bool* has_system,
                                    std::string* cache_filename,
                                    bool* dalvik_cache_exists,
-                                   bool* has_cache) {
+                                   bool* has_cache,
+                                   bool* is_global_cache) {
   *has_system = false;
   *has_cache = false;
   // image_location = /system/framework/boot.art
@@ -192,7 +193,7 @@
   *dalvik_cache_exists = false;
   std::string dalvik_cache;
   GetDalvikCache(GetInstructionSetString(image_isa), true, &dalvik_cache,
-                 &have_android_data, dalvik_cache_exists);
+                 &have_android_data, dalvik_cache_exists, is_global_cache);
 
   if (have_android_data && *dalvik_cache_exists) {
     // Always set output location even if it does not exist,
@@ -285,8 +286,9 @@
   std::string cache_filename;
   bool has_cache = false;
   bool dalvik_cache_exists = false;
+  bool is_global_cache = false;
   if (FindImageFilename(image_location, image_isa, &system_filename, &has_system,
-                        &cache_filename, &dalvik_cache_exists, &has_cache)) {
+                        &cache_filename, &dalvik_cache_exists, &has_cache, &is_global_cache)) {
     if (Runtime::Current()->ShouldRelocate()) {
       if (has_system && has_cache) {
         std::unique_ptr<ImageHeader> sys_hdr(new ImageHeader);
@@ -344,6 +346,21 @@
       && hdr_a.GetOatChecksum() == hdr_b.GetOatChecksum();
 }
 
+static bool ImageCreationAllowed(bool is_global_cache, std::string* error_msg) {
+  // Anyone can write into a "local" cache.
+  if (!is_global_cache) {
+    return true;
+  }
+
+  // Only the zygote is allowed to create the global boot image.
+  if (Runtime::Current()->IsZygote()) {
+    return true;
+  }
+
+  *error_msg = "Only the zygote can create the global boot image.";
+  return false;
+}
+
 ImageSpace* ImageSpace::Create(const char* image_location,
                                const InstructionSet image_isa,
                                std::string* error_msg) {
@@ -352,9 +369,10 @@
   std::string cache_filename;
   bool has_cache = false;
   bool dalvik_cache_exists = false;
+  bool is_global_cache = true;
   const bool found_image = FindImageFilename(image_location, image_isa, &system_filename,
                                              &has_system, &cache_filename, &dalvik_cache_exists,
-                                             &has_cache);
+                                             &has_cache, &is_global_cache);
 
   ImageSpace* space;
   bool relocate = Runtime::Current()->ShouldRelocate();
@@ -377,18 +395,27 @@
           relocated_version_used = true;
         } else {
           // We cannot have a relocated version, Relocate the system one and use it.
-          if (can_compile && RelocateImage(image_location, cache_filename.c_str(), image_isa,
-                                           error_msg)) {
+
+          std::string reason;
+          bool success;
+
+          // Check whether we are allowed to relocate.
+          if (!can_compile) {
+            reason = "Image dex2oat disabled by -Xnoimage-dex2oat.";
+            success = false;
+          } else if (!ImageCreationAllowed(is_global_cache, &reason)) {
+            // Whether we can write to the cache.
+            success = false;
+          } else {
+            // Try to relocate.
+            success = RelocateImage(image_location, cache_filename.c_str(), image_isa, &reason);
+          }
+
+          if (success) {
             relocated_version_used = true;
             image_filename = &cache_filename;
           } else {
-            std::string reason;
-            if (can_compile) {
-              reason = StringPrintf(": %s", error_msg->c_str());
-            } else {
-              reason = " because image dex2oat is disabled.";
-            }
-            *error_msg = StringPrintf("Unable to relocate image '%s' from '%s' to '%s'%s",
+            *error_msg = StringPrintf("Unable to relocate image '%s' from '%s' to '%s': %s",
                                       image_location, system_filename.c_str(),
                                       cache_filename.c_str(), reason.c_str());
             return nullptr;
@@ -460,6 +487,8 @@
   } else if (!dalvik_cache_exists) {
     *error_msg = StringPrintf("No place to put generated image.");
     return nullptr;
+  } else if (!ImageCreationAllowed(is_global_cache, error_msg)) {
+    return nullptr;
   } else if (!GenerateImage(cache_filename, image_isa, error_msg)) {
     *error_msg = StringPrintf("Failed to generate image '%s': %s",
                               cache_filename.c_str(), error_msg->c_str());
diff --git a/runtime/gc/space/image_space.h b/runtime/gc/space/image_space.h
index 28ebca6..2586ece 100644
--- a/runtime/gc/space/image_space.h
+++ b/runtime/gc/space/image_space.h
@@ -110,7 +110,8 @@
                                 bool* has_system,
                                 std::string* data_location,
                                 bool* dalvik_cache_exists,
-                                bool* has_data);
+                                bool* has_data,
+                                bool *is_global_cache);
 
  private:
   // Tries to initialize an ImageSpace from the given image path,
diff --git a/runtime/jdwp/jdwp_event.cc b/runtime/jdwp/jdwp_event.cc
index d61660b..7c8c63c 100644
--- a/runtime/jdwp/jdwp_event.cc
+++ b/runtime/jdwp/jdwp_event.cc
@@ -1125,12 +1125,19 @@
   DCHECK(exception_object != nullptr);
   DCHECK(pThrowLoc != nullptr);
   DCHECK(pCatchLoc != nullptr);
-  DCHECK(pThrowLoc->method != nullptr);
-  DCHECK_EQ(pThrowLoc->method->IsStatic(), thisPtr == nullptr);
+  if (pThrowLoc->method != nullptr) {
+    DCHECK_EQ(pThrowLoc->method->IsStatic(), thisPtr == nullptr);
+  } else {
+    VLOG(jdwp) << "Unexpected: exception event with empty throw location";
+  }
 
   ModBasket basket;
   basket.pLoc = pThrowLoc;
-  basket.locationClass = pThrowLoc->method->GetDeclaringClass();
+  if (pThrowLoc->method != nullptr) {
+    basket.locationClass = pThrowLoc->method->GetDeclaringClass();
+  } else {
+    basket.locationClass = nullptr;
+  }
   basket.thread = Thread::Current();
   basket.className = Dbg::GetClassName(basket.locationClass);
   basket.exceptionClass = exception_object->GetClass();
diff --git a/runtime/native/dalvik_system_DexFile.cc b/runtime/native/dalvik_system_DexFile.cc
index ff9dc38..003815e 100644
--- a/runtime/native/dalvik_system_DexFile.cc
+++ b/runtime/native/dalvik_system_DexFile.cc
@@ -504,7 +504,9 @@
   std::string cache_dir;
   bool have_android_data = false;
   bool dalvik_cache_exists = false;
-  GetDalvikCache(instruction_set, false, &cache_dir, &have_android_data, &dalvik_cache_exists);
+  bool is_global_cache = false;
+  GetDalvikCache(instruction_set, false, &cache_dir, &have_android_data, &dalvik_cache_exists,
+                 &is_global_cache);
   std::string cache_filename;  // was cache_location
   bool have_cache_filename = false;
   if (dalvik_cache_exists) {
diff --git a/runtime/runtime.cc b/runtime/runtime.cc
index de8634f..8386cc0 100644
--- a/runtime/runtime.cc
+++ b/runtime/runtime.cc
@@ -564,13 +564,15 @@
   std::string cache_filename_unused;
   bool dalvik_cache_exists_unused;
   bool has_cache_unused;
+  bool is_global_cache_unused;
   bool found_image = gc::space::ImageSpace::FindImageFilename(image_location.c_str(),
                                                               kRuntimeISA,
                                                               &system_filename,
                                                               &has_system,
                                                               &cache_filename_unused,
                                                               &dalvik_cache_exists_unused,
-                                                              &has_cache_unused);
+                                                              &has_cache_unused,
+                                                              &is_global_cache_unused);
   *failures = 0;
   if (!found_image || !has_system) {
     return false;
diff --git a/runtime/thread.cc b/runtime/thread.cc
index 650b0f9..ae89c90 100644
--- a/runtime/thread.cc
+++ b/runtime/thread.cc
@@ -931,6 +931,13 @@
     return false;
   }
 
+  // Threads with no managed stack frames should be shown.
+  const ManagedStack* managed_stack = thread->GetManagedStack();
+  if (managed_stack == NULL || (managed_stack->GetTopQuickFrame() == NULL &&
+      managed_stack->GetTopShadowFrame() == NULL)) {
+    return true;
+  }
+
   // In some other native method? That's interesting.
   // We don't just check kNative because native methods will be in state kSuspended if they're
   // calling back into the VM, or kBlocked if they're blocked on a monitor, or one of the
diff --git a/runtime/utils.cc b/runtime/utils.cc
index 6135e5d..9157f6c 100644
--- a/runtime/utils.cc
+++ b/runtime/utils.cc
@@ -1232,13 +1232,14 @@
 }
 
 void GetDalvikCache(const char* subdir, const bool create_if_absent, std::string* dalvik_cache,
-                    bool* have_android_data, bool* dalvik_cache_exists) {
+                    bool* have_android_data, bool* dalvik_cache_exists, bool* is_global_cache) {
   CHECK(subdir != nullptr);
   std::string error_msg;
   const char* android_data = GetAndroidDataSafe(&error_msg);
   if (android_data == nullptr) {
     *have_android_data = false;
     *dalvik_cache_exists = false;
+    *is_global_cache = false;
     return;
   } else {
     *have_android_data = true;
@@ -1246,7 +1247,8 @@
   const std::string dalvik_cache_root(StringPrintf("%s/dalvik-cache/", android_data));
   *dalvik_cache = dalvik_cache_root + subdir;
   *dalvik_cache_exists = OS::DirectoryExists(dalvik_cache->c_str());
-  if (create_if_absent && !*dalvik_cache_exists && strcmp(android_data, "/data") != 0) {
+  *is_global_cache = strcmp(android_data, "/data") == 0;
+  if (create_if_absent && !*dalvik_cache_exists && !*is_global_cache) {
     // Don't create the system's /data/dalvik-cache/... because it needs special permissions.
     *dalvik_cache_exists = ((mkdir(dalvik_cache_root.c_str(), 0700) == 0 || errno == EEXIST) &&
                             (mkdir(dalvik_cache->c_str(), 0700) == 0 || errno == EEXIST));
diff --git a/runtime/utils.h b/runtime/utils.h
index 50462b1..9ec6db1 100644
--- a/runtime/utils.h
+++ b/runtime/utils.h
@@ -449,8 +449,9 @@
 // Return true if we found the dalvik cache and stored it in the dalvik_cache argument.
 // have_android_data will be set to true if we have an ANDROID_DATA that exists,
 // dalvik_cache_exists will be true if there is a dalvik-cache directory that is present.
+// The flag is_global_cache tells whether this cache is /data/dalvik-cache.
 void GetDalvikCache(const char* subdir, bool create_if_absent, std::string* dalvik_cache,
-                    bool* have_android_data, bool* dalvik_cache_exists);
+                    bool* have_android_data, bool* dalvik_cache_exists, bool* is_global_cache);
 
 // Returns the absolute dalvik-cache path for a DexFile or OatFile. The path returned will be
 // rooted at cache_location.