Merge "Update comment about disabling vmap dump."
diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index 4ecda91..3f58527 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -140,8 +140,11 @@
   compiler/jni/jni_compiler_test.cc \
   compiler/oat_test.cc \
   compiler/optimizing/codegen_test.cc \
+  compiler/optimizing/dead_code_elimination_test.cc \
+  compiler/optimizing/constant_propagation_test.cc \
   compiler/optimizing/dominator_test.cc \
   compiler/optimizing/find_loops_test.cc \
+  compiler/optimizing/graph_checker_test.cc \
   compiler/optimizing/graph_test.cc \
   compiler/optimizing/linearize_test.cc \
   compiler/optimizing/liveness_test.cc \
diff --git a/compiler/Android.mk b/compiler/Android.mk
index 6e48bdf..35cddf9 100644
--- a/compiler/Android.mk
+++ b/compiler/Android.mk
@@ -90,6 +90,9 @@
 	optimizing/code_generator_arm.cc \
 	optimizing/code_generator_x86.cc \
 	optimizing/code_generator_x86_64.cc \
+	optimizing/constant_propagation.cc \
+	optimizing/dead_code_elimination.cc \
+	optimizing/graph_checker.cc \
 	optimizing/graph_visualizer.cc \
 	optimizing/locations.cc \
 	optimizing/nodes.cc \
diff --git a/compiler/dex/frontend.cc b/compiler/dex/frontend.cc
index b267841..07f3033 100644
--- a/compiler/dex/frontend.cc
+++ b/compiler/dex/frontend.cc
@@ -82,11 +82,22 @@
                                      jobject class_loader, const DexFile& dex_file,
                                      void* llvm_compilation_unit) {
   VLOG(compiler) << "Compiling " << PrettyMethod(method_idx, dex_file) << "...";
-  if (code_item->insns_size_in_code_units_ >= 0x10000) {
-    LOG(INFO) << "Method size exceeds compiler limits: " << code_item->insns_size_in_code_units_
+  /*
+   * Skip compilation for pathologically large methods - either by instruction count or num vregs.
+   * Dalvik uses 16-bit uints for instruction and register counts.  We'll limit to a quarter
+   * of that, which also guarantees we cannot overflow our 16-bit internal SSA name space.
+   */
+  if (code_item->insns_size_in_code_units_ >= UINT16_MAX / 4) {
+    LOG(INFO) << "Method exceeds compiler instruction limit: "
+              << code_item->insns_size_in_code_units_
               << " in " << PrettyMethod(method_idx, dex_file);
     return NULL;
   }
+  if (code_item->registers_size_ >= UINT16_MAX / 4) {
+    LOG(INFO) << "Method exceeds compiler virtual register limit: "
+              << code_item->registers_size_ << " in " << PrettyMethod(method_idx, dex_file);
+    return NULL;
+  }
 
   if (!driver.GetCompilerOptions().IsCompilationEnabled()) {
     return nullptr;
diff --git a/compiler/optimizing/constant_propagation.cc b/compiler/optimizing/constant_propagation.cc
new file mode 100644
index 0000000..d675164
--- /dev/null
+++ b/compiler/optimizing/constant_propagation.cc
@@ -0,0 +1,47 @@
+/*
+ * 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 "constant_propagation.h"
+
+namespace art {
+
+void ConstantPropagation::Run() {
+  // Process basic blocks in reverse post-order in the dominator tree,
+  // so that an instruction turned into a constant, used as input of
+  // another instruction, may possibly be used to turn that second
+  // instruction into a constant as well.
+  for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
+    HBasicBlock* block = it.Current();
+    // Traverse this block's instructions in (forward) order and
+    // replace the ones that can be statically evaluated by a
+    // compile-time counterpart.
+    for (HInstructionIterator it(block->GetInstructions());
+         !it.Done(); it.Advance()) {
+      HInstruction* inst = it.Current();
+      // Constant folding: replace `c <- a op b' with a compile-time
+      // evaluation of `a op b' if `a' and `b' are constant.
+      if (inst->IsBinaryOperation()) {
+        HConstant* constant =
+          inst->AsBinaryOperation()->TryStaticEvaluation(graph_->GetArena());
+        if (constant != nullptr) {
+          inst->GetBlock()->ReplaceAndRemoveInstructionWith(inst, constant);
+        }
+      }
+    }
+  }
+}
+
+}  // namespace art
diff --git a/compiler/optimizing/constant_propagation.h b/compiler/optimizing/constant_propagation.h
new file mode 100644
index 0000000..0729881
--- /dev/null
+++ b/compiler/optimizing/constant_propagation.h
@@ -0,0 +1,43 @@
+/*
+ * 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_CONSTANT_PROPAGATION_H_
+#define ART_COMPILER_OPTIMIZING_CONSTANT_PROPAGATION_H_
+
+#include "nodes.h"
+
+namespace art {
+
+/**
+ * Optimization pass performing a simple constant propagation on the
+ * SSA form.
+ */
+class ConstantPropagation : public ValueObject {
+ public:
+  explicit ConstantPropagation(HGraph* graph)
+    : graph_(graph) {}
+
+  void Run();
+
+ private:
+  HGraph* const graph_;
+
+  DISALLOW_COPY_AND_ASSIGN(ConstantPropagation);
+};
+
+}  // namespace art
+
+#endif  // ART_COMPILER_OPTIMIZING_CONSTANT_PROPAGATION_H_
diff --git a/compiler/optimizing/constant_propagation_test.cc b/compiler/optimizing/constant_propagation_test.cc
new file mode 100644
index 0000000..5c8c709
--- /dev/null
+++ b/compiler/optimizing/constant_propagation_test.cc
@@ -0,0 +1,487 @@
+/*
+ * 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 "constant_propagation.h"
+#include "dead_code_elimination.h"
+#include "pretty_printer.h"
+#include "graph_checker.h"
+#include "optimizing_unit_test.h"
+
+#include "gtest/gtest.h"
+
+namespace art {
+
+static void TestCode(const uint16_t* data,
+                     const std::string& expected_before,
+                     const std::string& expected_after_cp,
+                     const std::string& expected_after_dce) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+  HGraph* graph = CreateCFG(&allocator, data);
+  ASSERT_NE(graph, nullptr);
+
+  graph->BuildDominatorTree();
+  graph->TransformToSSA();
+
+  StringPrettyPrinter printer_before(graph);
+  printer_before.VisitInsertionOrder();
+  std::string actual_before = printer_before.str();
+  ASSERT_EQ(expected_before, actual_before);
+
+  ConstantPropagation(graph).Run();
+
+  StringPrettyPrinter printer_after_cp(graph);
+  printer_after_cp.VisitInsertionOrder();
+  std::string actual_after_cp = printer_after_cp.str();
+  ASSERT_EQ(expected_after_cp, actual_after_cp);
+
+  DeadCodeElimination(graph).Run();
+
+  StringPrettyPrinter printer_after_dce(graph);
+  printer_after_dce.VisitInsertionOrder();
+  std::string actual_after_dce = printer_after_dce.str();
+  ASSERT_EQ(expected_after_dce, actual_after_dce);
+
+  SSAChecker ssa_checker(&allocator, graph);
+  ssa_checker.VisitInsertionOrder();
+  ASSERT_TRUE(ssa_checker.IsValid());
+}
+
+
+/**
+ * Tiny three-register program exercising int constant folding on addition.
+ *
+ *                              16-bit
+ *                              offset
+ *                              ------
+ *     v0 <- 1                  0.      const/4 v0, #+1
+ *     v1 <- 2                  1.      const/4 v1, #+2
+ *     v2 <- v0 + v1            2.      add-int v2, v0, v1
+ *     return v2                4.      return v2
+ */
+TEST(ConstantPropagation, IntConstantFoldingOnAddition1) {
+  const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
+    Instruction::CONST_4 | 0 << 8 | 1 << 12,
+    Instruction::CONST_4 | 1 << 8 | 2 << 12,
+    Instruction::ADD_INT | 2 << 8, 0 | 1 << 8,
+    Instruction::RETURN | 2 << 8);
+
+  std::string expected_before =
+    "BasicBlock 0, succ: 1\n"
+    "  3: IntConstant [9]\n"
+    "  5: IntConstant [9]\n"
+    "  14: SuspendCheck\n"
+    "  15: Goto 1\n"
+    "BasicBlock 1, pred: 0, succ: 2\n"
+    "  9: Add(3, 5) [12]\n"
+    "  12: Return(9)\n"
+    "BasicBlock 2, pred: 1\n"
+    "  13: Exit\n";
+
+  // Expected difference after constant propagation.
+  diff_t expected_cp_diff = {
+    { "  3: IntConstant [9]\n", "  3: IntConstant\n" },
+    { "  5: IntConstant [9]\n", "  5: IntConstant\n" },
+    { "  9: Add(3, 5) [12]\n",  "  16: IntConstant [12]\n" },
+    { "  12: Return(9)\n",      "  12: Return(16)\n" }
+  };
+  std::string expected_after_cp = Patch(expected_before, expected_cp_diff);
+
+  // Expected difference after dead code elimination.
+  diff_t expected_dce_diff = {
+    { "  3: IntConstant\n", removed },
+    { "  5: IntConstant\n", removed }
+  };
+  std::string expected_after_dce = Patch(expected_after_cp, expected_dce_diff);
+
+  TestCode(data, expected_before, expected_after_cp, expected_after_dce);
+}
+
+/**
+ * Small three-register program exercising int constant folding on addition.
+ *
+ *                              16-bit
+ *                              offset
+ *                              ------
+ *     v0 <- 1                  0.      const/4 v0, #+1
+ *     v1 <- 2                  1.      const/4 v1, #+2
+ *     v0 <- v0 + v1            2.      add-int/2addr v0, v1
+ *     v1 <- 3                  3.      const/4 v1, #+3
+ *     v2 <- 4                  4.      const/4 v2, #+4
+ *     v1 <- v1 + v2            5.      add-int/2addr v1, v2
+ *     v2 <- v0 + v1            6.      add-int v2, v0, v1
+ *     return v2                8.      return v2
+ */
+TEST(ConstantPropagation, IntConstantFoldingOnAddition2) {
+  const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
+    Instruction::CONST_4 | 0 << 8 | 1 << 12,
+    Instruction::CONST_4 | 1 << 8 | 2 << 12,
+    Instruction::ADD_INT_2ADDR | 0 << 8 | 1 << 12,
+    Instruction::CONST_4 | 1 << 8 | 3 << 12,
+    Instruction::CONST_4 | 2 << 8 | 4 << 12,
+    Instruction::ADD_INT_2ADDR | 1 << 8 | 2 << 12,
+    Instruction::ADD_INT | 2 << 8, 0 | 1 << 8,
+    Instruction::RETURN | 2 << 8);
+
+  std::string expected_before =
+    "BasicBlock 0, succ: 1\n"
+    "  3: IntConstant [9]\n"
+    "  5: IntConstant [9]\n"
+    "  11: IntConstant [17]\n"
+    "  13: IntConstant [17]\n"
+    "  26: SuspendCheck\n"
+    "  27: Goto 1\n"
+    "BasicBlock 1, pred: 0, succ: 2\n"
+    "  9: Add(3, 5) [21]\n"
+    "  17: Add(11, 13) [21]\n"
+    "  21: Add(9, 17) [24]\n"
+    "  24: Return(21)\n"
+    "BasicBlock 2, pred: 1\n"
+    "  25: Exit\n";
+
+  // Expected difference after constant propagation.
+  diff_t expected_cp_diff = {
+    { "  3: IntConstant [9]\n",   "  3: IntConstant\n" },
+    { "  5: IntConstant [9]\n",   "  5: IntConstant\n" },
+    { "  11: IntConstant [17]\n", "  11: IntConstant\n" },
+    { "  13: IntConstant [17]\n", "  13: IntConstant\n" },
+    { "  9: Add(3, 5) [21]\n",    "  28: IntConstant\n" },
+    { "  17: Add(11, 13) [21]\n", "  29: IntConstant\n" },
+    { "  21: Add(9, 17) [24]\n",  "  30: IntConstant [24]\n" },
+    { "  24: Return(21)\n",       "  24: Return(30)\n" }
+  };
+  std::string expected_after_cp = Patch(expected_before, expected_cp_diff);
+
+  // Expected difference after dead code elimination.
+  diff_t expected_dce_diff = {
+    { "  3: IntConstant\n",  removed },
+    { "  5: IntConstant\n",  removed },
+    { "  11: IntConstant\n", removed },
+    { "  13: IntConstant\n", removed },
+    { "  28: IntConstant\n", removed },
+    { "  29: IntConstant\n", removed }
+  };
+  std::string expected_after_dce = Patch(expected_after_cp, expected_dce_diff);
+
+  TestCode(data, expected_before, expected_after_cp, expected_after_dce);
+}
+
+/**
+ * Tiny three-register program exercising int constant folding on subtraction.
+ *
+ *                              16-bit
+ *                              offset
+ *                              ------
+ *     v0 <- 3                  0.      const/4 v0, #+3
+ *     v1 <- 2                  1.      const/4 v1, #+2
+ *     v2 <- v0 - v1            2.      sub-int v2, v0, v1
+ *     return v2                4.      return v2
+ */
+TEST(ConstantPropagation, IntConstantFoldingOnSubtraction) {
+  const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
+    Instruction::CONST_4 | 0 << 8 | 3 << 12,
+    Instruction::CONST_4 | 1 << 8 | 2 << 12,
+    Instruction::SUB_INT | 2 << 8, 0 | 1 << 8,
+    Instruction::RETURN | 2 << 8);
+
+  std::string expected_before =
+    "BasicBlock 0, succ: 1\n"
+    "  3: IntConstant [9]\n"
+    "  5: IntConstant [9]\n"
+    "  14: SuspendCheck\n"
+    "  15: Goto 1\n"
+    "BasicBlock 1, pred: 0, succ: 2\n"
+    "  9: Sub(3, 5) [12]\n"
+    "  12: Return(9)\n"
+    "BasicBlock 2, pred: 1\n"
+    "  13: Exit\n";
+
+  // Expected difference after constant propagation.
+  diff_t expected_cp_diff = {
+    { "  3: IntConstant [9]\n", "  3: IntConstant\n" },
+    { "  5: IntConstant [9]\n", "  5: IntConstant\n" },
+    { "  9: Sub(3, 5) [12]\n",  "  16: IntConstant [12]\n" },
+    { "  12: Return(9)\n",      "  12: Return(16)\n" }
+  };
+  std::string expected_after_cp = Patch(expected_before, expected_cp_diff);
+
+  // Expected difference after dead code elimination.
+  diff_t expected_dce_diff = {
+    { "  3: IntConstant\n", removed },
+    { "  5: IntConstant\n", removed }
+  };
+  std::string expected_after_dce = Patch(expected_after_cp, expected_dce_diff);
+
+  TestCode(data, expected_before, expected_after_cp, expected_after_dce);
+}
+
+#define SIX_REGISTERS_CODE_ITEM(...)                                     \
+    { 6, 0, 0, 0, 0, 0, NUM_INSTRUCTIONS(__VA_ARGS__), 0, __VA_ARGS__ }
+
+/**
+ * Tiny three-register-pair program exercising long constant folding
+ * on addition.
+ *
+ *                              16-bit
+ *                              offset
+ *                              ------
+ *     (v0, v1) <- 1            0.      const-wide/16 v0, #+1
+ *     (v2, v3) <- 2            2.      const-wide/16 v2, #+2
+ *     (v4, v5) <-
+ *       (v0, v1) + (v1, v2)    4.      add-long v4, v0, v2
+ *     return (v4, v5)          6.      return-wide v4
+ */
+TEST(ConstantPropagation, LongConstantFoldingOnAddition) {
+  const uint16_t data[] = SIX_REGISTERS_CODE_ITEM(
+    Instruction::CONST_WIDE_16 | 0 << 8, 1,
+    Instruction::CONST_WIDE_16 | 2 << 8, 2,
+    Instruction::ADD_LONG | 4 << 8, 0 | 2 << 8,
+    Instruction::RETURN_WIDE | 4 << 8);
+
+  std::string expected_before =
+    "BasicBlock 0, succ: 1\n"
+    "  6: LongConstant [12]\n"
+    "  8: LongConstant [12]\n"
+    "  17: SuspendCheck\n"
+    "  18: Goto 1\n"
+    "BasicBlock 1, pred: 0, succ: 2\n"
+    "  12: Add(6, 8) [15]\n"
+    "  15: Return(12)\n"
+    "BasicBlock 2, pred: 1\n"
+    "  16: Exit\n";
+
+  // Expected difference after constant propagation.
+  diff_t expected_cp_diff = {
+    { "  6: LongConstant [12]\n", "  6: LongConstant\n" },
+    { "  8: LongConstant [12]\n", "  8: LongConstant\n" },
+    { "  12: Add(6, 8) [15]\n",   "  19: LongConstant [15]\n" },
+    { "  15: Return(12)\n",       "  15: Return(19)\n" }
+  };
+  std::string expected_after_cp = Patch(expected_before, expected_cp_diff);
+
+  // Expected difference after dead code elimination.
+  diff_t expected_dce_diff = {
+    { "  6: LongConstant\n", removed },
+    { "  8: LongConstant\n", removed }
+  };
+  std::string expected_after_dce = Patch(expected_after_cp, expected_dce_diff);
+
+  TestCode(data, expected_before, expected_after_cp, expected_after_dce);
+}
+
+/**
+ * Tiny three-register-pair program exercising long constant folding
+ * on subtraction.
+ *
+ *                              16-bit
+ *                              offset
+ *                              ------
+ *     (v0, v1) <- 3            0.      const-wide/16 v0, #+3
+ *     (v2, v3) <- 2            2.      const-wide/16 v2, #+2
+ *     (v4, v5) <-
+ *       (v0, v1) - (v1, v2)    4.      sub-long v4, v0, v2
+ *     return (v4, v5)          6.      return-wide v4
+ */
+TEST(ConstantPropagation, LongConstantFoldingOnSubtraction) {
+  const uint16_t data[] = SIX_REGISTERS_CODE_ITEM(
+    Instruction::CONST_WIDE_16 | 0 << 8, 3,
+    Instruction::CONST_WIDE_16 | 2 << 8, 2,
+    Instruction::SUB_LONG | 4 << 8, 0 | 2 << 8,
+    Instruction::RETURN_WIDE | 4 << 8);
+
+  std::string expected_before =
+    "BasicBlock 0, succ: 1\n"
+    "  6: LongConstant [12]\n"
+    "  8: LongConstant [12]\n"
+    "  17: SuspendCheck\n"
+    "  18: Goto 1\n"
+    "BasicBlock 1, pred: 0, succ: 2\n"
+    "  12: Sub(6, 8) [15]\n"
+    "  15: Return(12)\n"
+    "BasicBlock 2, pred: 1\n"
+    "  16: Exit\n";
+
+  // Expected difference after constant propagation.
+  diff_t expected_cp_diff = {
+    { "  6: LongConstant [12]\n", "  6: LongConstant\n" },
+    { "  8: LongConstant [12]\n", "  8: LongConstant\n" },
+    { "  12: Sub(6, 8) [15]\n",   "  19: LongConstant [15]\n" },
+    { "  15: Return(12)\n",       "  15: Return(19)\n" }
+  };
+  std::string expected_after_cp = Patch(expected_before, expected_cp_diff);
+
+  // Expected difference after dead code elimination.
+  diff_t expected_dce_diff = {
+    { "  6: LongConstant\n", removed },
+    { "  8: LongConstant\n", removed }
+  };
+  std::string expected_after_dce = Patch(expected_after_cp, expected_dce_diff);
+
+  TestCode(data, expected_before, expected_after_cp, expected_after_dce);
+}
+
+/**
+ * Three-register program with jumps leading to the creation of many
+ * blocks.
+ *
+ * The intent of this test is to ensure that all constant expressions
+ * are actually evaluated at compile-time, thanks to the reverse
+ * (forward) post-order traversal of the the dominator tree.
+ *
+ *                              16-bit
+ *                              offset
+ *                              ------
+ *     v0 <- 0                   0.     const/4 v0, #+0
+ *     v1 <- 1                   1.     const/4 v1, #+1
+ *     v2 <- v0 + v1             2.     add-int v2, v0, v1
+ *     goto L2                   4.     goto +4
+ * L1: v1 <- v0 + 3              5.     add-int/lit16 v1, v0, #+3
+ *     goto L3                   7.     goto +4
+ * L2: v0 <- v2 + 2              8.     add-int/lit16 v0, v2, #+2
+ *     goto L1                  10.     goto +(-5)
+ * L3: v2 <- v1 + 4             11.     add-int/lit16 v2, v1, #+4
+ *     return v2                13.     return v2
+ */
+TEST(ConstantPropagation, IntConstantFoldingAndJumps) {
+  const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
+    Instruction::CONST_4 | 0 << 8 | 0 << 12,
+    Instruction::CONST_4 | 1 << 8 | 1 << 12,
+    Instruction::ADD_INT | 2 << 8, 0 | 1 << 8,
+    Instruction::GOTO | 4 << 8,
+    Instruction::ADD_INT_LIT16 | 1 << 8 | 0 << 12, 3,
+    Instruction::GOTO | 4 << 8,
+    Instruction::ADD_INT_LIT16 | 0 << 8 | 2 << 12, 2,
+    static_cast<uint16_t>(Instruction::GOTO | -5 << 8),
+    Instruction::ADD_INT_LIT16 | 2 << 8 | 1 << 12, 4,
+    Instruction::RETURN | 2 << 8);
+
+  std::string expected_before =
+    "BasicBlock 0, succ: 1\n"
+    "  3: IntConstant [9]\n"
+    "  5: IntConstant [9]\n"
+    "  13: IntConstant [14]\n"
+    "  18: IntConstant [19]\n"
+    "  24: IntConstant [25]\n"
+    "  30: SuspendCheck\n"
+    "  31: Goto 1\n"
+    "BasicBlock 1, pred: 0, succ: 3\n"
+    "  9: Add(3, 5) [19]\n"
+    "  11: Goto 3\n"
+    "BasicBlock 2, pred: 3, succ: 4\n"
+    "  14: Add(19, 13) [25]\n"
+    "  16: Goto 4\n"
+    "BasicBlock 3, pred: 1, succ: 2\n"
+    "  19: Add(9, 18) [14]\n"
+    "  21: SuspendCheck\n"
+    "  22: Goto 2\n"
+    "BasicBlock 4, pred: 2, succ: 5\n"
+    "  25: Add(14, 24) [28]\n"
+    "  28: Return(25)\n"
+    "BasicBlock 5, pred: 4\n"
+    "  29: Exit\n";
+
+  // Expected difference after constant propagation.
+  diff_t expected_cp_diff = {
+    { "  3: IntConstant [9]\n",   "  3: IntConstant\n" },
+    { "  5: IntConstant [9]\n",   "  5: IntConstant []\n" },
+    { "  13: IntConstant [14]\n", "  13: IntConstant\n" },
+    { "  18: IntConstant [19]\n", "  18: IntConstant\n" },
+    { "  24: IntConstant [25]\n", "  24: IntConstant\n" },
+    { "  9: Add(3, 5) [19]\n",    "  32: IntConstant []\n" },
+    { "  14: Add(19, 13) [25]\n", "  34: IntConstant\n" },
+    { "  19: Add(9, 18) [14]\n",  "  33: IntConstant []\n" },
+    { "  25: Add(14, 24) [28]\n", "  35: IntConstant [28]\n" },
+    { "  28: Return(25)\n",       "  28: Return(35)\n"}
+  };
+  std::string expected_after_cp = Patch(expected_before, expected_cp_diff);
+
+  // Expected difference after dead code elimination.
+  diff_t expected_dce_diff = {
+    { "  3: IntConstant\n",     removed },
+    { "  13: IntConstant\n",    removed },
+    { "  18: IntConstant\n",    removed },
+    { "  24: IntConstant\n",    removed },
+    { "  34: IntConstant\n",    removed },
+  };
+  std::string expected_after_dce = Patch(expected_after_cp, expected_dce_diff);
+
+  TestCode(data, expected_before, expected_after_cp, expected_after_dce);
+}
+
+
+/**
+ * Three-register program with a constant (static) condition.
+ *
+ *                              16-bit
+ *                              offset
+ *                              ------
+ *     v1 <- 1                  0.      const/4 v1, #+1
+ *     v0 <- 0                  1.      const/4 v0, #+0
+ *     if v1 >= 0 goto L1       2.      if-gez v1, +3
+ *     v0 <- v1                 4.      move v0, v1
+ * L1: v2 <- v0 + v1            5.      add-int v2, v0, v1
+ *     return-void              7.      return
+ */
+TEST(ConstantPropagation, ConstantCondition) {
+  const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
+    Instruction::CONST_4 | 1 << 8 | 1 << 12,
+    Instruction::CONST_4 | 0 << 8 | 0 << 12,
+    Instruction::IF_GEZ | 1 << 8, 3,
+    Instruction::MOVE | 0 << 8 | 1 << 12,
+    Instruction::ADD_INT | 2 << 8, 0 | 1 << 8,
+    Instruction::RETURN_VOID);
+
+  std::string expected_before =
+    "BasicBlock 0, succ: 1\n"
+    "  3: IntConstant [15, 22, 8]\n"
+    "  5: IntConstant [22, 8]\n"
+    "  19: SuspendCheck\n"
+    "  20: Goto 1\n"
+    "BasicBlock 1, pred: 0, succ: 5, 2\n"
+    "  8: GreaterThanOrEqual(3, 5) [9]\n"
+    "  9: If(8)\n"
+    "BasicBlock 2, pred: 1, succ: 3\n"
+    "  12: Goto 3\n"
+    "BasicBlock 3, pred: 2, 5, succ: 4\n"
+    "  22: Phi(3, 5) [15]\n"
+    "  15: Add(22, 3)\n"
+    "  17: ReturnVoid\n"
+    "BasicBlock 4, pred: 3\n"
+    "  18: Exit\n"
+    "BasicBlock 5, pred: 1, succ: 3\n"
+    "  21: Goto 3\n";
+
+  // Expected difference after constant propagation.
+  diff_t expected_cp_diff = {
+    { "  3: IntConstant [15, 22, 8]\n",      "  3: IntConstant [15, 22]\n" },
+    { "  5: IntConstant [22, 8]\n",          "  5: IntConstant [22]\n" },
+    { "  8: GreaterThanOrEqual(3, 5) [9]\n", "  23: IntConstant [9]\n" },
+    { "  9: If(8)\n",                        "  9: If(23)\n" }
+  };
+  std::string expected_after_cp = Patch(expected_before, expected_cp_diff);
+
+  // Expected difference after dead code elimination.
+  diff_t expected_dce_diff = {
+    { "  3: IntConstant [15, 22]\n", "  3: IntConstant [22]\n" },
+    { "  22: Phi(3, 5) [15]\n",      "  22: Phi(3, 5)\n" },
+    { "  15: Add(22, 3)\n",          removed }
+  };
+  std::string expected_after_dce = Patch(expected_after_cp, expected_dce_diff);
+
+  TestCode(data, expected_before, expected_after_cp, expected_after_dce);
+}
+
+}  // namespace art
diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc
new file mode 100644
index 0000000..2f881d1
--- /dev/null
+++ b/compiler/optimizing/dead_code_elimination.cc
@@ -0,0 +1,45 @@
+/*
+ * 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 "dead_code_elimination.h"
+
+#include "base/bit_vector-inl.h"
+
+namespace art {
+
+void DeadCodeElimination::Run() {
+  // Process basic blocks in post-order in the dominator tree, so that
+  // a dead instruction depending on another dead instruction is
+  // removed.
+  for (HPostOrderIterator b(*graph_); !b.Done(); b.Advance()) {
+    HBasicBlock* block = b.Current();
+    // Traverse this block's instructions in backward order and remove
+    // the unused ones.
+    HBackwardInstructionIterator i(block->GetInstructions());
+    // Skip the first iteration, as the last instruction of a block is
+    // a branching instruction.
+    DCHECK(i.Current()->IsControlFlow());
+    for (i.Advance(); !i.Done(); i.Advance()) {
+      HInstruction* inst = i.Current();
+      DCHECK(!inst->IsControlFlow());
+      if (!inst->HasSideEffects() && !inst->HasUses()) {
+        block->RemoveInstruction(inst);
+      }
+    }
+  }
+}
+
+}  // namespace art
diff --git a/compiler/optimizing/dead_code_elimination.h b/compiler/optimizing/dead_code_elimination.h
new file mode 100644
index 0000000..48739be
--- /dev/null
+++ b/compiler/optimizing/dead_code_elimination.h
@@ -0,0 +1,43 @@
+/*
+ * 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_DEAD_CODE_ELIMINATION_H_
+#define ART_COMPILER_OPTIMIZING_DEAD_CODE_ELIMINATION_H_
+
+#include "nodes.h"
+
+namespace art {
+
+/**
+ * Optimization pass performing dead code elimination (removal of
+ * unused variables/instructions) on the SSA form.
+ */
+class DeadCodeElimination : public ValueObject {
+ public:
+  explicit DeadCodeElimination(HGraph* graph)
+      : graph_(graph) {}
+
+  void Run();
+
+ private:
+  HGraph* const graph_;
+
+  DISALLOW_COPY_AND_ASSIGN(DeadCodeElimination);
+};
+
+}  // namespace art
+
+#endif  // ART_COMPILER_OPTIMIZING_DEAD_CODE_ELIMINATION_H_
diff --git a/compiler/optimizing/dead_code_elimination_test.cc b/compiler/optimizing/dead_code_elimination_test.cc
new file mode 100644
index 0000000..245bcb2
--- /dev/null
+++ b/compiler/optimizing/dead_code_elimination_test.cc
@@ -0,0 +1,185 @@
+/*
+ * 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 "dead_code_elimination.h"
+#include "pretty_printer.h"
+#include "graph_checker.h"
+#include "optimizing_unit_test.h"
+
+#include "gtest/gtest.h"
+
+namespace art {
+
+static void TestCode(const uint16_t* data,
+                     const std::string& expected_before,
+                     const std::string& expected_after) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+  HGraph* graph = CreateCFG(&allocator, data);
+  ASSERT_NE(graph, nullptr);
+
+  graph->BuildDominatorTree();
+  graph->TransformToSSA();
+
+  StringPrettyPrinter printer_before(graph);
+  printer_before.VisitInsertionOrder();
+  std::string actual_before = printer_before.str();
+  ASSERT_EQ(actual_before, expected_before);
+
+  DeadCodeElimination(graph).Run();
+
+  StringPrettyPrinter printer_after(graph);
+  printer_after.VisitInsertionOrder();
+  std::string actual_after = printer_after.str();
+  ASSERT_EQ(actual_after, expected_after);
+
+  SSAChecker ssa_checker(&allocator, graph);
+  ssa_checker.VisitInsertionOrder();
+  ASSERT_TRUE(ssa_checker.IsValid());
+}
+
+
+/**
+ * Small three-register program.
+ *
+ *                              16-bit
+ *                              offset
+ *                              ------
+ *     v1 <- 1                  0.      const/4 v1, #+1
+ *     v0 <- 0                  1.      const/4 v0, #+0
+ *     if v1 >= 0 goto L1       2.      if-gez v1, +3
+ *     v0 <- v1                 4.      move v0, v1
+ * L1: v2 <- v0 + v1            5.      add-int v2, v0, v1
+ *     return-void              7.      return
+ */
+TEST(DeadCodeElimination, AdditionAndConditionalJump) {
+  const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
+    Instruction::CONST_4 | 1 << 8 | 1 << 12,
+    Instruction::CONST_4 | 0 << 8 | 0 << 12,
+    Instruction::IF_GEZ | 1 << 8, 3,
+    Instruction::MOVE | 0 << 8 | 1 << 12,
+    Instruction::ADD_INT | 2 << 8, 0 | 1 << 8,
+    Instruction::RETURN_VOID);
+
+  std::string expected_before =
+    "BasicBlock 0, succ: 1\n"
+    "  3: IntConstant [15, 22, 8]\n"
+    "  5: IntConstant [22, 8]\n"
+    "  19: SuspendCheck\n"
+    "  20: Goto 1\n"
+    "BasicBlock 1, pred: 0, succ: 5, 2\n"
+    "  8: GreaterThanOrEqual(3, 5) [9]\n"
+    "  9: If(8)\n"
+    "BasicBlock 2, pred: 1, succ: 3\n"
+    "  12: Goto 3\n"
+    "BasicBlock 3, pred: 2, 5, succ: 4\n"
+    "  22: Phi(3, 5) [15]\n"
+    "  15: Add(22, 3)\n"
+    "  17: ReturnVoid\n"
+    "BasicBlock 4, pred: 3\n"
+    "  18: Exit\n"
+    "BasicBlock 5, pred: 1, succ: 3\n"
+    "  21: Goto 3\n";
+
+  diff_t expected_diff = {
+    { "  3: IntConstant [15, 22, 8]\n", "  3: IntConstant [22, 8]\n" },
+    { "  22: Phi(3, 5) [15]\n",         "  22: Phi(3, 5)\n" },
+    { "  15: Add(22, 3)\n",             removed }
+  };
+  std::string expected_after = Patch(expected_before, expected_diff);
+
+  TestCode(data, expected_before, expected_after);
+}
+
+/**
+ * Three-register program with jumps leading to the creation of many
+ * blocks.
+ *
+ * The intent of this test is to ensure that all dead instructions are
+ * actually pruned at compile-time, thanks to the (backward)
+ * post-order traversal of the the dominator tree.
+ *
+ *                              16-bit
+ *                              offset
+ *                              ------
+ *     v0 <- 0                   0.     const/4 v0, #+0
+ *     v1 <- 1                   1.     const/4 v1, #+1
+ *     v2 <- v0 + v1             2.     add-int v2, v0, v1
+ *     goto L2                   4.     goto +4
+ * L1: v1 <- v0 + 3              5.     add-int/lit16 v1, v0, #+3
+ *     goto L3                   7.     goto +4
+ * L2: v0 <- v2 + 2              8.     add-int/lit16 v0, v2, #+2
+ *     goto L1                  10.     goto +(-5)
+ * L3: v2 <- v1 + 4             11.     add-int/lit16 v2, v1, #+4
+ *     return                   13.     return-void
+ */
+TEST(DeadCodeElimination, AdditionsAndInconditionalJumps) {
+  const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
+    Instruction::CONST_4 | 0 << 8 | 0 << 12,
+    Instruction::CONST_4 | 1 << 8 | 1 << 12,
+    Instruction::ADD_INT | 2 << 8, 0 | 1 << 8,
+    Instruction::GOTO | 4 << 8,
+    Instruction::ADD_INT_LIT16 | 1 << 8 | 0 << 12, 3,
+    Instruction::GOTO | 4 << 8,
+    Instruction::ADD_INT_LIT16 | 0 << 8 | 2 << 12, 2,
+    static_cast<uint16_t>(Instruction::GOTO | -5 << 8),
+    Instruction::ADD_INT_LIT16 | 2 << 8 | 1 << 12, 4,
+    Instruction::RETURN_VOID);
+
+  std::string expected_before =
+    "BasicBlock 0, succ: 1\n"
+    "  3: IntConstant [9]\n"
+    "  5: IntConstant [9]\n"
+    "  13: IntConstant [14]\n"
+    "  18: IntConstant [19]\n"
+    "  24: IntConstant [25]\n"
+    "  29: SuspendCheck\n"
+    "  30: Goto 1\n"
+    "BasicBlock 1, pred: 0, succ: 3\n"
+    "  9: Add(3, 5) [19]\n"
+    "  11: Goto 3\n"
+    "BasicBlock 2, pred: 3, succ: 4\n"
+    "  14: Add(19, 13) [25]\n"
+    "  16: Goto 4\n"
+    "BasicBlock 3, pred: 1, succ: 2\n"
+    "  19: Add(9, 18) [14]\n"
+    "  21: SuspendCheck\n"
+    "  22: Goto 2\n"
+    "BasicBlock 4, pred: 2, succ: 5\n"
+    "  25: Add(14, 24)\n"
+    "  27: ReturnVoid\n"
+    "BasicBlock 5, pred: 4\n"
+    "  28: Exit\n";
+
+  // Expected difference after constant propagation.
+  diff_t expected_diff = {
+    { "  13: IntConstant [14]\n", removed },
+    { "  24: IntConstant [25]\n", removed },
+    { "  14: Add(19, 13) [25]\n", removed },
+    // The SuspendCheck instruction following this Add instruction
+    // inserts the latter in an environment, thus making it "used" and
+    // therefore non removable.  It ensues that some other Add and
+    // IntConstant instructions cannot be removed, as they are direct
+    // or indirect inputs of the initial Add instruction.
+    { "  19: Add(9, 18) [14]\n",  "  19: Add(9, 18) []\n" },
+    { "  25: Add(14, 24)\n",      removed },
+  };
+  std::string expected_after = Patch(expected_before, expected_diff);
+
+  TestCode(data, expected_before, expected_after);
+}
+
+}  // namespace art
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
new file mode 100644
index 0000000..ad9ed0c
--- /dev/null
+++ b/compiler/optimizing/graph_checker.cc
@@ -0,0 +1,183 @@
+/*
+ * 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 "graph_checker.h"
+
+#include <string>
+#include <map>
+#include <sstream>
+
+namespace art {
+
+void GraphChecker::VisitBasicBlock(HBasicBlock* block) {
+  current_block_ = block;
+
+  // Check consistency with respect to predecessors of `block`.
+  const GrowableArray<HBasicBlock*>& predecessors = block->GetPredecessors();
+  std::map<HBasicBlock*, size_t> predecessors_count;
+  for (size_t i = 0, e = predecessors.Size(); i < e; ++i) {
+    HBasicBlock* p = predecessors.Get(i);
+    ++predecessors_count[p];
+  }
+  for (auto& pc : predecessors_count) {
+    HBasicBlock* p = pc.first;
+    size_t p_count_in_block_predecessors = pc.second;
+    const GrowableArray<HBasicBlock*>& p_successors = p->GetSuccessors();
+    size_t block_count_in_p_successors = 0;
+    for (size_t j = 0, f = p_successors.Size(); j < f; ++j) {
+      if (p_successors.Get(j) == block) {
+        ++block_count_in_p_successors;
+      }
+    }
+    if (p_count_in_block_predecessors != block_count_in_p_successors) {
+      std::stringstream error;
+      error << "Block " << block->GetBlockId()
+            << " lists " << p_count_in_block_predecessors
+            << " occurrences of block " << p->GetBlockId()
+            << " in its predecessors, whereas block " << p->GetBlockId()
+            << " lists " << block_count_in_p_successors
+            << " occurrences of block " << block->GetBlockId()
+            << " in its successors.";
+      errors_.Insert(error.str());
+    }
+  }
+
+  // Check consistency with respect to successors of `block`.
+  const GrowableArray<HBasicBlock*>& successors = block->GetSuccessors();
+  std::map<HBasicBlock*, size_t> successors_count;
+  for (size_t i = 0, e = successors.Size(); i < e; ++i) {
+    HBasicBlock* s = successors.Get(i);
+    ++successors_count[s];
+  }
+  for (auto& sc : successors_count) {
+    HBasicBlock* s = sc.first;
+    size_t s_count_in_block_successors = sc.second;
+    const GrowableArray<HBasicBlock*>& s_predecessors = s->GetPredecessors();
+    size_t block_count_in_s_predecessors = 0;
+    for (size_t j = 0, f = s_predecessors.Size(); j < f; ++j) {
+      if (s_predecessors.Get(j) == block) {
+        ++block_count_in_s_predecessors;
+      }
+    }
+    if (s_count_in_block_successors != block_count_in_s_predecessors) {
+      std::stringstream error;
+      error << "Block " << block->GetBlockId()
+            << " lists " << s_count_in_block_successors
+            << " occurrences of block " << s->GetBlockId()
+            << " in its successors, whereas block " << s->GetBlockId()
+            << " lists " << block_count_in_s_predecessors
+            << " occurrences of block " << block->GetBlockId()
+            << " in its predecessors.";
+      errors_.Insert(error.str());
+    }
+  }
+
+  // Ensure `block` ends with a branch instruction.
+  HInstruction* last_inst = block->GetLastInstruction();
+  if (last_inst == nullptr || !last_inst->IsControlFlow()) {
+    std::stringstream error;
+    error  << "Block " << block->GetBlockId()
+           << " does not end with a branch instruction.";
+    errors_.Insert(error.str());
+  }
+
+  // Visit this block's list of phis.
+  for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
+    // Ensure this block's list of phis contains only phis.
+    if (!it.Current()->IsPhi()) {
+      std::stringstream error;
+      error << "Block " << current_block_->GetBlockId()
+            << " has a non-phi in its phi list.";
+      errors_.Insert(error.str());
+    }
+    it.Current()->Accept(this);
+  }
+
+  // Visit this block's list of instructions.
+  for (HInstructionIterator it(block->GetInstructions()); !it.Done();
+       it.Advance()) {
+    // Ensure this block's list of instructions does not contains phis.
+    if (it.Current()->IsPhi()) {
+      std::stringstream error;
+      error << "Block " << current_block_->GetBlockId()
+            << " has a phi in its non-phi list.";
+      errors_.Insert(error.str());
+    }
+    it.Current()->Accept(this);
+  }
+}
+
+void GraphChecker::VisitInstruction(HInstruction* instruction) {
+  // Ensure `instruction` is associated with `current_block_`.
+  if (instruction->GetBlock() != current_block_) {
+    std::stringstream error;
+    if (instruction->IsPhi()) {
+      error << "Phi ";
+    } else {
+      error << "Instruction ";
+    }
+    error << instruction->GetId() << " in block "
+          << current_block_->GetBlockId();
+    if (instruction->GetBlock() != nullptr) {
+      error << " associated with block "
+            << instruction->GetBlock()->GetBlockId() << ".";
+    } else {
+      error << " not associated with any block.";
+    }
+    errors_.Insert(error.str());
+  }
+}
+
+void SSAChecker::VisitBasicBlock(HBasicBlock* block) {
+  super_type::VisitBasicBlock(block);
+
+  // Ensure there is no critical edge (i.e., an edge connecting a
+  // block with multiple successors to a block with multiple
+  // predecessors).
+  if (block->GetSuccessors().Size() > 1) {
+    for (size_t j = 0; j < block->GetSuccessors().Size(); ++j) {
+      HBasicBlock* successor = block->GetSuccessors().Get(j);
+      if (successor->GetPredecessors().Size() > 1) {
+        std::stringstream error;
+        error << "Critical edge between blocks " << block->GetBlockId()
+              << " and "  << successor->GetBlockId() << ".";
+        errors_.Insert(error.str());
+      }
+    }
+  }
+}
+
+void SSAChecker::VisitInstruction(HInstruction* instruction) {
+  super_type::VisitInstruction(instruction);
+
+  // Ensure an instruction dominates all its uses (or in the present
+  // case, that all uses of an instruction (used as input) are
+  // dominated by its definition).
+  for (HInputIterator input_it(instruction); !input_it.Done();
+       input_it.Advance()) {
+    HInstruction* input = input_it.Current();
+    if (!input->Dominates(instruction)) {
+      std::stringstream error;
+      error << "Instruction " << input->GetId()
+            << " in block " << input->GetBlock()->GetBlockId()
+            << " does not dominate use " << instruction->GetId()
+            << " in block " << current_block_->GetBlockId() << ".";
+      errors_.Insert(error.str());
+    }
+  }
+}
+
+}  // namespace art
diff --git a/compiler/optimizing/graph_checker.h b/compiler/optimizing/graph_checker.h
new file mode 100644
index 0000000..8ddd399
--- /dev/null
+++ b/compiler/optimizing/graph_checker.h
@@ -0,0 +1,80 @@
+/*
+ * 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_GRAPH_CHECKER_H_
+#define ART_COMPILER_OPTIMIZING_GRAPH_CHECKER_H_
+
+#include "nodes.h"
+
+namespace art {
+
+// A control-flow graph visitor performing various checks.
+class GraphChecker : public HGraphVisitor {
+ public:
+  GraphChecker(ArenaAllocator* allocator, HGraph* graph)
+    : HGraphVisitor(graph),
+      allocator_(allocator),
+      errors_(allocator, 0) {}
+
+  // Check `block`.
+  virtual void VisitBasicBlock(HBasicBlock* block) OVERRIDE;
+
+  // Check `instruction`.
+  virtual void VisitInstruction(HInstruction* instruction) OVERRIDE;
+
+  // Was the last visit of the graph valid?
+  bool IsValid() const {
+    return errors_.IsEmpty();
+  }
+
+  // Get the list of detected errors.
+  const GrowableArray<std::string>& GetErrors() const {
+    return errors_;
+  }
+
+ protected:
+  ArenaAllocator* const allocator_;
+  // The block currently visited.
+  HBasicBlock* current_block_ = nullptr;
+  // Errors encountered while checking the graph.
+  GrowableArray<std::string> errors_;
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(GraphChecker);
+};
+
+
+// An SSA graph visitor performing various checks.
+class SSAChecker : public GraphChecker {
+ public:
+  typedef GraphChecker super_type;
+
+  SSAChecker(ArenaAllocator* allocator, HGraph* graph)
+    : GraphChecker(allocator, graph) {}
+
+  // Perform SSA form checks on `block`.
+  virtual void VisitBasicBlock(HBasicBlock* block) OVERRIDE;
+
+  // Perform SSA form checks on `instruction`.
+  virtual void VisitInstruction(HInstruction* instruction) OVERRIDE;
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(SSAChecker);
+};
+
+}  // namespace art
+
+#endif  // ART_COMPILER_OPTIMIZING_GRAPH_CHECKER_H_
diff --git a/compiler/optimizing/graph_checker_test.cc b/compiler/optimizing/graph_checker_test.cc
new file mode 100644
index 0000000..ea06920
--- /dev/null
+++ b/compiler/optimizing/graph_checker_test.cc
@@ -0,0 +1,159 @@
+/*
+ * 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 "graph_checker.h"
+#include "optimizing_unit_test.h"
+
+#include "gtest/gtest.h"
+
+namespace art {
+
+/**
+ * Create a simple control-flow graph composed of two blocks:
+ *
+ *   BasicBlock 0, succ: 1
+ *     0: Goto 1
+ *   BasicBlock 1, pred: 0
+ *     1: Exit
+ */
+HGraph* CreateSimpleCFG(ArenaAllocator* allocator) {
+  HGraph* graph = new (allocator) HGraph(allocator);
+  HBasicBlock* entry_block = new (allocator) HBasicBlock(graph);
+  entry_block->AddInstruction(new (allocator) HGoto());
+  graph->AddBlock(entry_block);
+  graph->SetEntryBlock(entry_block);
+  HBasicBlock* exit_block = new (allocator) HBasicBlock(graph);
+  exit_block->AddInstruction(new (allocator) HExit());
+  graph->AddBlock(exit_block);
+  graph->SetExitBlock(exit_block);
+  entry_block->AddSuccessor(exit_block);
+  return graph;
+}
+
+
+static void TestCode(const uint16_t* data) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+  HGraph* graph = CreateCFG(&allocator, data);
+  ASSERT_NE(graph, nullptr);
+
+  GraphChecker graph_checker(&allocator, graph);
+  graph_checker.VisitInsertionOrder();
+  ASSERT_TRUE(graph_checker.IsValid());
+}
+
+static void TestCodeSSA(const uint16_t* data) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+  HGraph* graph = CreateCFG(&allocator, data);
+  ASSERT_NE(graph, nullptr);
+
+  graph->BuildDominatorTree();
+  graph->TransformToSSA();
+
+  SSAChecker ssa_checker(&allocator, graph);
+  ssa_checker.VisitInsertionOrder();
+  ASSERT_TRUE(ssa_checker.IsValid());
+}
+
+
+TEST(GraphChecker, ReturnVoid) {
+  const uint16_t data[] = ZERO_REGISTER_CODE_ITEM(
+      Instruction::RETURN_VOID);
+
+  TestCode(data);
+}
+
+TEST(GraphChecker, CFG1) {
+  const uint16_t data[] = ZERO_REGISTER_CODE_ITEM(
+      Instruction::GOTO | 0x100,
+      Instruction::RETURN_VOID);
+
+  TestCode(data);
+}
+
+TEST(GraphChecker, CFG2) {
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 3,
+    Instruction::GOTO | 0x100,
+    Instruction::RETURN_VOID);
+
+  TestCode(data);
+}
+
+TEST(GraphChecker, CFG3) {
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 3,
+    Instruction::GOTO | 0x100,
+    Instruction::GOTO | 0xFF00);
+
+  TestCode(data);
+}
+
+// Test case with an invalid graph containing inconsistent
+// predecessor/successor arcs in CFG.
+TEST(GraphChecker, InconsistentPredecessorsAndSuccessors) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+
+  HGraph* graph = CreateSimpleCFG(&allocator);
+  GraphChecker graph_checker(&allocator, graph);
+  graph_checker.VisitInsertionOrder();
+  ASSERT_TRUE(graph_checker.IsValid());
+
+  // Remove the entry block from the exit block's predecessors, to create an
+  // inconsistent successor/predecessor relation.
+  graph->GetExitBlock()->RemovePredecessor(graph->GetEntryBlock());
+  graph_checker.VisitInsertionOrder();
+  ASSERT_FALSE(graph_checker.IsValid());
+}
+
+// Test case with an invalid graph containing a non-branch last
+// instruction in a block.
+TEST(GraphChecker, BlockEndingWithNonBranchInstruction) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+
+  HGraph* graph = CreateSimpleCFG(&allocator);
+  GraphChecker graph_checker(&allocator, graph);
+  graph_checker.VisitInsertionOrder();
+  ASSERT_TRUE(graph_checker.IsValid());
+
+  // Remove the sole instruction of the exit block (composed of a
+  // single Exit instruction) to make it invalid (i.e. not ending by a
+  // branch instruction).
+  HBasicBlock* exit_block = graph->GetExitBlock();
+  HInstruction* last_inst = exit_block->GetLastInstruction();
+  exit_block->RemoveInstruction(last_inst);
+
+  graph_checker.VisitInsertionOrder();
+  ASSERT_FALSE(graph_checker.IsValid());
+}
+
+TEST(SSAChecker, SSAPhi) {
+  // This code creates one Phi function during the conversion to SSA form.
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 3,
+    Instruction::CONST_4 | 4 << 12 | 0,
+    Instruction::RETURN | 0 << 8);
+
+  TestCodeSSA(data);
+}
+
+}  // namespace art
diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc
index f011e85..7f64be4 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -81,6 +81,23 @@
     }
   }
 
+  char GetTypeId(Primitive::Type type) {
+    switch (type) {
+      case Primitive::kPrimBoolean: return 'z';
+      case Primitive::kPrimByte: return 'b';
+      case Primitive::kPrimChar: return 'c';
+      case Primitive::kPrimShort: return 's';
+      case Primitive::kPrimInt: return 'i';
+      case Primitive::kPrimLong: return 'j';
+      case Primitive::kPrimFloat: return 'f';
+      case Primitive::kPrimDouble: return 'd';
+      case Primitive::kPrimNot: return 'l';
+      case Primitive::kPrimVoid: return 'v';
+    }
+    LOG(FATAL) << "Unreachable";
+    return 'v';
+  }
+
   void PrintPredecessors(HBasicBlock* block) {
     AddIndent();
     output_ << "predecessors";
@@ -140,7 +157,7 @@
     if (instruction->InputCount() > 0) {
       output_ << " [ ";
       for (HInputIterator inputs(instruction); !inputs.Done(); inputs.Advance()) {
-        output_ << "v" << inputs.Current()->GetId() << " ";
+        output_ << GetTypeId(inputs.Current()->GetType()) << inputs.Current()->GetId() << " ";
       }
       output_ << "]";
     }
@@ -175,7 +192,8 @@
       HInstruction* instruction = it.Current();
       AddIndent();
       int bci = 0;
-      output_ << bci << " " << instruction->NumberOfUses() << " v" << instruction->GetId() << " ";
+      output_ << bci << " " << instruction->NumberOfUses()
+              << " " << GetTypeId(instruction->GetType()) << instruction->GetId() << " ";
       instruction->Accept(this);
       output_ << kEndInstructionMarker << std::endl;
     }
@@ -214,7 +232,8 @@
     for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
       AddIndent();
       HInstruction* instruction = it.Current();
-      output_ << instruction->GetId() << " v" << instruction->GetId() << "[ ";
+      output_ << instruction->GetId() << " " << GetTypeId(instruction->GetType())
+              << instruction->GetId() << "[ ";
       for (HInputIterator inputs(instruction); !inputs.Done(); inputs.Advance()) {
         output_ << inputs.Current()->GetId() << " ";
       }
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 207c605..376d1af 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -194,6 +194,11 @@
     }
     pre_header->AddSuccessor(header);
   }
+
+  // Make sure the second predecessor of a loop header is the back edge.
+  if (header->GetPredecessors().Get(1) != info->GetBackEdges().Get(0)) {
+    header->SwapPredecessors();
+  }
 }
 
 void HGraph::SimplifyCFG() {
@@ -307,6 +312,14 @@
   instruction->SetId(GetGraph()->GetNextInstructionId());
 }
 
+void HBasicBlock::ReplaceAndRemoveInstructionWith(HInstruction* initial,
+                                                  HInstruction* replacement) {
+  DCHECK(initial->GetBlock() == this);
+  InsertInstructionBefore(replacement, initial);
+  initial->ReplaceWith(replacement);
+  RemoveInstruction(initial);
+}
+
 static void Add(HInstructionList* instruction_list,
                 HBasicBlock* block,
                 HInstruction* instruction) {
@@ -392,6 +405,54 @@
   }
 }
 
+bool HInstructionList::FoundBefore(const HInstruction* instruction1,
+                                   const HInstruction* instruction2) const {
+  DCHECK_EQ(instruction1->GetBlock(), instruction2->GetBlock());
+  for (HInstructionIterator it(*this); !it.Done(); it.Advance()) {
+    if (it.Current() == instruction1) {
+      return true;
+    }
+    if (it.Current() == instruction2) {
+      return false;
+    }
+  }
+  LOG(FATAL) << "Did not find an order between two instructions of the same block.";
+  return true;
+}
+
+bool HInstruction::Dominates(HInstruction* other_instruction) const {
+  HBasicBlock* block = GetBlock();
+  HBasicBlock* other_block = other_instruction->GetBlock();
+  if (block != other_block) {
+    return GetBlock()->Dominates(other_instruction->GetBlock());
+  } else {
+    // If both instructions are in the same block, ensure this
+    // instruction comes before `other_instruction`.
+    if (IsPhi()) {
+      if (!other_instruction->IsPhi()) {
+        // Phis appear before non phi-instructions so this instruction
+        // dominates `other_instruction`.
+        return true;
+      } else {
+        // There is no order among phis.
+        LOG(FATAL) << "There is no dominance between phis of a same block.";
+        return false;
+      }
+    } else {
+      // `this` is not a phi.
+      if (other_instruction->IsPhi()) {
+        // Phis appear before non phi-instructions so this instruction
+        // does not dominate `other_instruction`.
+        return false;
+      } else {
+        // Check whether this instruction comes before
+        // `other_instruction` in the instruction list.
+        return block->GetInstructions().FoundBefore(this, other_instruction);
+      }
+    }
+  }
+}
+
 void HInstruction::ReplaceWith(HInstruction* other) {
   DCHECK(other != nullptr);
   for (HUseIterator<HInstruction> it(GetUses()); !it.Done(); it.Advance()) {
@@ -449,6 +510,18 @@
   }
 }
 
+HConstant* HBinaryOperation::TryStaticEvaluation(ArenaAllocator* allocator) const {
+  if (GetLeft()->IsIntConstant() && GetRight()->IsIntConstant()) {
+    int32_t value = Evaluate(GetLeft()->AsIntConstant()->GetValue(),
+                             GetRight()->AsIntConstant()->GetValue());
+    return new(allocator) HIntConstant(value);
+  } else if (GetLeft()->IsLongConstant() && GetRight()->IsLongConstant()) {
+    int64_t value = Evaluate(GetLeft()->AsLongConstant()->GetValue(),
+                             GetRight()->AsLongConstant()->GetValue());
+    return new(allocator) HLongConstant(value);
+  }
+  return nullptr;
+}
 
 bool HCondition::NeedsMaterialization() const {
   if (!HasOnlyOneUse()) {
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index d6dfeae..d98d2ad 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -56,6 +56,12 @@
   void AddInstruction(HInstruction* instruction);
   void RemoveInstruction(HInstruction* instruction);
 
+  // Return true if `instruction1` is found before `instruction2` in
+  // this instruction list and false otherwise.  Abort if none
+  // of these instructions is found.
+  bool FoundBefore(const HInstruction* instruction1,
+                   const HInstruction* instruction2) const;
+
  private:
   HInstruction* first_instruction_;
   HInstruction* last_instruction_;
@@ -192,7 +198,8 @@
   HLoopInformation(HBasicBlock* header, HGraph* graph)
       : header_(header),
         back_edges_(graph->GetArena(), kDefaultNumberOfBackEdges),
-        blocks_(graph->GetArena(), graph->GetBlocks().Size(), false) {}
+        // Make bit vector growable, as the number of blocks may change.
+        blocks_(graph->GetArena(), graph->GetBlocks().Size(), true) {}
 
   HBasicBlock* GetHeader() const {
     return header_;
@@ -331,6 +338,13 @@
     block->successors_.Add(this);
   }
 
+  void SwapPredecessors() {
+    DCHECK_EQ(predecessors_.Size(), 2u);
+    HBasicBlock* temp = predecessors_.Get(0);
+    predecessors_.Put(0, predecessors_.Get(1));
+    predecessors_.Put(1, temp);
+  }
+
   size_t GetPredecessorIndexOf(HBasicBlock* predecessor) {
     for (size_t i = 0, e = predecessors_.Size(); i < e; ++i) {
       if (predecessors_.Get(i) == predecessor) {
@@ -352,6 +366,9 @@
   void AddInstruction(HInstruction* instruction);
   void RemoveInstruction(HInstruction* instruction);
   void InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor);
+  // Replace instruction `initial` with `replacement` within this block.
+  void ReplaceAndRemoveInstructionWith(HInstruction* initial,
+                                       HInstruction* replacement);
   void AddPhi(HPhi* phi);
   void RemovePhi(HPhi* phi);
 
@@ -448,19 +465,21 @@
 
 #define FOR_EACH_INSTRUCTION(M)                            \
   FOR_EACH_CONCRETE_INSTRUCTION(M)                         \
-  M(Constant)
+  M(Constant)                                              \
+  M(BinaryOperation)
 
 #define FORWARD_DECLARATION(type) class H##type;
 FOR_EACH_INSTRUCTION(FORWARD_DECLARATION)
 #undef FORWARD_DECLARATION
 
-#define DECLARE_INSTRUCTION(type)                          \
-  virtual const char* DebugName() const { return #type; }  \
-  virtual H##type* As##type() { return this; }             \
-  virtual bool InstructionTypeEquals(HInstruction* other) const {     \
-    return other->Is##type();                              \
-  }                                                        \
-  virtual void Accept(HGraphVisitor* visitor)              \
+#define DECLARE_INSTRUCTION(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; }                 \
+  virtual bool InstructionTypeEquals(HInstruction* other) const {       \
+    return other->Is##type();                                           \
+  }                                                                     \
+  virtual void Accept(HGraphVisitor* visitor)
 
 template <typename T>
 class HUseListNode : public ArenaObject {
@@ -502,6 +521,11 @@
     return SideEffects(((1 << count) - 1) << kFlagChangesCount);
   }
 
+  bool HasSideEffects() const {
+    size_t all_bits_set = (1 << kFlagChangesCount) - 1;
+    return (flags_ & all_bits_set) != 0;
+  }
+
  private:
   static constexpr int kFlagChangesSomething = 0;
   static constexpr int kFlagChangesCount = kFlagChangesSomething + 1;
@@ -553,6 +577,7 @@
 
   virtual bool NeedsEnvironment() const { return false; }
   virtual bool IsControlFlow() const { return false; }
+  bool HasSideEffects() const { return side_effects_.HasSideEffects(); }
 
   void AddUseAt(HInstruction* user, size_t index) {
     uses_ = new (block_->GetGraph()->GetArena()) HUseListNode<HInstruction>(user, index, uses_);
@@ -582,6 +607,10 @@
     return result;
   }
 
+  // Does this instruction dominate `other_instruction`?  Aborts if
+  // this instruction and `other_instruction` are both phis.
+  bool Dominates(HInstruction* other_instruction) const;
+
   int GetId() const { return id_; }
   void SetId(int id) { id_ = id; }
 
@@ -607,7 +636,8 @@
   }
 
 #define INSTRUCTION_TYPE_CHECK(type)                                           \
-  bool Is##type() { return (As##type() != nullptr); }                          \
+  bool Is##type() const { return (As##type() != nullptr); }                    \
+  virtual const H##type* As##type() const { return nullptr; }                  \
   virtual H##type* As##type() { return nullptr; }
 
   FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK)
@@ -984,6 +1014,17 @@
   virtual bool CanBeMoved() const { return true; }
   virtual bool InstructionDataEquals(HInstruction* other) const { return true; }
 
+  // Try to statically evaluate `operation` and return an HConstant
+  // containing the result of this evaluation.  If `operation` cannot
+  // be evaluated as a constant, return nullptr.
+  HConstant* TryStaticEvaluation(ArenaAllocator* allocator) const;
+
+  // Apply this operation to `x` and `y`.
+  virtual int32_t Evaluate(int32_t x, int32_t y) const = 0;
+  virtual int64_t Evaluate(int64_t x, int64_t y) const = 0;
+
+  DECLARE_INSTRUCTION(BinaryOperation);
+
  private:
   DISALLOW_COPY_AND_ASSIGN(HBinaryOperation);
 };
@@ -1010,6 +1051,9 @@
   HEqual(HInstruction* first, HInstruction* second)
       : HCondition(first, second) {}
 
+  virtual int32_t Evaluate(int32_t x, int32_t y) const { return x == y; }
+  virtual int64_t Evaluate(int64_t x, int64_t y) const { return x == y; }
+
   DECLARE_INSTRUCTION(Equal);
 
   virtual IfCondition GetCondition() const {
@@ -1025,6 +1069,9 @@
   HNotEqual(HInstruction* first, HInstruction* second)
       : HCondition(first, second) {}
 
+  virtual int32_t Evaluate(int32_t x, int32_t y) const { return x != y; }
+  virtual int64_t Evaluate(int64_t x, int64_t y) const { return x != y; }
+
   DECLARE_INSTRUCTION(NotEqual);
 
   virtual IfCondition GetCondition() const {
@@ -1040,6 +1087,9 @@
   HLessThan(HInstruction* first, HInstruction* second)
       : HCondition(first, second) {}
 
+  virtual int32_t Evaluate(int32_t x, int32_t y) const { return x < y; }
+  virtual int64_t Evaluate(int64_t x, int64_t y) const { return x < y; }
+
   DECLARE_INSTRUCTION(LessThan);
 
   virtual IfCondition GetCondition() const {
@@ -1055,6 +1105,9 @@
   HLessThanOrEqual(HInstruction* first, HInstruction* second)
       : HCondition(first, second) {}
 
+  virtual int32_t Evaluate(int32_t x, int32_t y) const { return x <= y; }
+  virtual int64_t Evaluate(int64_t x, int64_t y) const { return x <= y; }
+
   DECLARE_INSTRUCTION(LessThanOrEqual);
 
   virtual IfCondition GetCondition() const {
@@ -1070,6 +1123,9 @@
   HGreaterThan(HInstruction* first, HInstruction* second)
       : HCondition(first, second) {}
 
+  virtual int32_t Evaluate(int32_t x, int32_t y) const { return x > y; }
+  virtual int64_t Evaluate(int64_t x, int64_t y) const { return x > y; }
+
   DECLARE_INSTRUCTION(GreaterThan);
 
   virtual IfCondition GetCondition() const {
@@ -1085,6 +1141,9 @@
   HGreaterThanOrEqual(HInstruction* first, HInstruction* second)
       : HCondition(first, second) {}
 
+  virtual int32_t Evaluate(int32_t x, int32_t y) const { return x >= y; }
+  virtual int64_t Evaluate(int64_t x, int64_t y) const { return x >= y; }
+
   DECLARE_INSTRUCTION(GreaterThanOrEqual);
 
   virtual IfCondition GetCondition() const {
@@ -1106,6 +1165,19 @@
     DCHECK_EQ(type, second->GetType());
   }
 
+  virtual int32_t Evaluate(int32_t x, int32_t y) const {
+    return
+      x == y ? 0 :
+      x > y ? 1 :
+      -1;
+  }
+  virtual int64_t Evaluate(int64_t x, int64_t y) const {
+    return
+      x == y ? 0 :
+      x > y ? 1 :
+      -1;
+  }
+
   DECLARE_INSTRUCTION(Compare);
 
  private:
@@ -1322,6 +1394,9 @@
 
   virtual bool IsCommutative() { return true; }
 
+  virtual int32_t Evaluate(int32_t x, int32_t y) const { return x + y; }
+  virtual int64_t Evaluate(int64_t x, int64_t y) const { return x + y; }
+
   DECLARE_INSTRUCTION(Add);
 
  private:
@@ -1335,6 +1410,9 @@
 
   virtual bool IsCommutative() { return false; }
 
+  virtual int32_t Evaluate(int32_t x, int32_t y) const { return x + y; }
+  virtual int64_t Evaluate(int64_t x, int64_t y) const { return x + y; }
+
   DECLARE_INSTRUCTION(Sub);
 
  private:
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index a539192..3ce8e77 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -154,11 +154,15 @@
 }
 
 OptimizingCompiler::~OptimizingCompiler() {
-  size_t unoptimized_percent = (unoptimized_compiled_methods_ * 100 / total_compiled_methods_);
-  size_t optimized_percent = (optimized_compiled_methods_ * 100 / total_compiled_methods_);
-  LOG(INFO) << "Compiled " << total_compiled_methods_ << " methods: "
-            << unoptimized_percent << "% (" << unoptimized_compiled_methods_ << ") unoptimized, "
-            << optimized_percent << "% (" << optimized_compiled_methods_ << ") optimized.";
+  if (total_compiled_methods_ == 0) {
+    LOG(INFO) << "Did not compile any method.";
+  } else {
+    size_t unoptimized_percent = (unoptimized_compiled_methods_ * 100 / total_compiled_methods_);
+    size_t optimized_percent = (optimized_compiled_methods_ * 100 / total_compiled_methods_);
+    LOG(INFO) << "Compiled " << total_compiled_methods_ << " methods: "
+              << unoptimized_percent << "% (" << unoptimized_compiled_methods_ << ") unoptimized, "
+              << optimized_percent << "% (" << optimized_compiled_methods_ << ") optimized.";
+  }
 }
 
 bool OptimizingCompiler::CanCompileMethod(uint32_t method_idx, const DexFile& dex_file,
diff --git a/compiler/optimizing/optimizing_unit_test.h b/compiler/optimizing/optimizing_unit_test.h
index c409529..6dd53e5 100644
--- a/compiler/optimizing/optimizing_unit_test.h
+++ b/compiler/optimizing/optimizing_unit_test.h
@@ -17,8 +17,14 @@
 #ifndef ART_COMPILER_OPTIMIZING_OPTIMIZING_UNIT_TEST_H_
 #define ART_COMPILER_OPTIMIZING_OPTIMIZING_UNIT_TEST_H_
 
+#include "nodes.h"
+#include "builder.h"
+#include "dex_file.h"
+#include "dex_instruction.h"
 #include "ssa_liveness_analysis.h"
 
+#include "gtest/gtest.h"
+
 namespace art {
 
 #define NUM_INSTRUCTIONS(...)  \
@@ -61,6 +67,33 @@
   }
 }
 
+// Create a control-flow graph from Dex instructions.
+inline HGraph* CreateCFG(ArenaAllocator* allocator, const uint16_t* data) {
+  HGraphBuilder builder(allocator);
+  const DexFile::CodeItem* item =
+    reinterpret_cast<const DexFile::CodeItem*>(data);
+  HGraph* graph = builder.BuildGraph(*item);
+  return graph;
+}
+
+// Naive string diff data type.
+typedef std::list<std::pair<std::string, std::string>> diff_t;
+
+// An alias for the empty string used to make it clear that a line is
+// removed in a diff.
+static const std::string removed = "";
+
+// Naive patch command: apply a diff to a string.
+inline std::string Patch(const std::string& original, const diff_t& diff) {
+  std::string result = original;
+  for (const auto& p : diff) {
+    std::string::size_type pos = result.find(p.first);
+    EXPECT_NE(pos, std::string::npos);
+    result.replace(pos, p.first.size(), p.second);
+  }
+  return result;
+}
+
 }  // namespace art
 
 #endif  // ART_COMPILER_OPTIMIZING_OPTIMIZING_UNIT_TEST_H_
diff --git a/compiler/optimizing/ssa_phi_elimination.cc b/compiler/optimizing/ssa_phi_elimination.cc
index 65675dc..d541a62 100644
--- a/compiler/optimizing/ssa_phi_elimination.cc
+++ b/compiler/optimizing/ssa_phi_elimination.cc
@@ -83,6 +83,10 @@
   }
 }
 
+static bool LoopPreHeaderIsFirstPredecessor(HBasicBlock* block) {
+  return block->GetPredecessors().Get(0) == block->GetLoopInformation()->GetPreHeader();
+}
+
 void SsaRedundantPhiElimination::Run() {
   // Add all phis in the worklist.
   for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
@@ -102,7 +106,10 @@
 
     // Find if the inputs of the phi are the same instruction.
     HInstruction* candidate = phi->InputAt(0);
-    // A loop phi cannot have itself as the first phi.
+    // A loop phi cannot have itself as the first phi. Note that this
+    // check relies on our simplification pass ensuring the pre-header
+    // block is first in the list of predecessors of the loop header.
+    DCHECK(!phi->IsLoopHeaderPhi() || LoopPreHeaderIsFirstPredecessor(phi->GetBlock()));
     DCHECK_NE(phi, candidate);
 
     for (size_t i = 1; i < phi->InputCount(); ++i) {
diff --git a/compiler/optimizing/ssa_test.cc b/compiler/optimizing/ssa_test.cc
index 99fd9eb..ad3b205 100644
--- a/compiler/optimizing/ssa_test.cc
+++ b/compiler/optimizing/ssa_test.cc
@@ -207,8 +207,8 @@
     "BasicBlock 2, pred: 3, 6, succ: 3\n"
     "  4: Phi(6, 0) [6]\n"
     "  5: Goto\n"
-    "BasicBlock 3, pred: 2, 5, succ: 2\n"
-    "  6: Phi(4, 0) [4]\n"
+    "BasicBlock 3, pred: 5, 2, succ: 2\n"
+    "  6: Phi(0, 4) [4]\n"
     "  7: Goto\n"
     "BasicBlock 4\n"
     // Synthesized blocks to avoid critical edge.
@@ -298,8 +298,8 @@
     "  2: Goto\n"
     "BasicBlock 1, pred: 0, succ: 4\n"
     "  3: Goto\n"
-    "BasicBlock 2, pred: 3, 4, succ: 5, 3\n"
-    "  4: Phi(1, 0) [9, 5, 5]\n"
+    "BasicBlock 2, pred: 4, 3, succ: 5, 3\n"
+    "  4: Phi(0, 1) [9, 5, 5]\n"
     "  5: Equal(4, 4) [6]\n"
     "  6: If(5)\n"
     "BasicBlock 3, pred: 2, succ: 2\n"
@@ -339,8 +339,8 @@
     "  6: Goto\n"
     "BasicBlock 3, pred: 1, succ: 8\n"
     "  7: Goto\n"
-    "BasicBlock 4, pred: 5, 8, succ: 6, 5\n"
-    "  8: Phi(8, 14) [8, 12, 9, 9]\n"
+    "BasicBlock 4, pred: 8, 5, succ: 6, 5\n"
+    "  8: Phi(14, 8) [8, 12, 9, 9]\n"
     "  9: Equal(8, 8) [10]\n"
     "  10: If(9)\n"
     "BasicBlock 5, pred: 4, succ: 4\n"
diff --git a/compiler/optimizing/ssa_type_propagation.cc b/compiler/optimizing/ssa_type_propagation.cc
index 53fa74e..a860cb7 100644
--- a/compiler/optimizing/ssa_type_propagation.cc
+++ b/compiler/optimizing/ssa_type_propagation.cc
@@ -28,7 +28,11 @@
     case Primitive::kPrimNot:
       return existing;
     default:
-      return new_type;
+      // Phis are initialized with a void type, so if we are asked
+      // to merge with a void type, we should use the existing one.
+      return new_type == Primitive::kPrimVoid
+          ? existing
+          : new_type;
   }
 }
 
diff --git a/dex2oat/dex2oat.cc b/dex2oat/dex2oat.cc
index b64390b..afc01dc 100644
--- a/dex2oat/dex2oat.cc
+++ b/dex2oat/dex2oat.cc
@@ -442,6 +442,11 @@
       return nullptr;
     }
 
+    // Flush result to disk. Patching code will re-open the file (mmap), so ensure that our view
+    // of the file already made it there and won't be re-ordered with writes from PatchOat or
+    // image patching.
+    oat_file->Flush();
+
     if (!driver->IsImage() && driver->GetCompilerOptions().GetIncludePatchInformation()) {
       t2.NewTiming("Patching ELF");
       std::string error_msg;
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/base/allocator.h b/runtime/base/allocator.h
index a7adb02..2c3e966 100644
--- a/runtime/base/allocator.h
+++ b/runtime/base/allocator.h
@@ -66,6 +66,7 @@
   kAllocatorTagCompileTimeClassPath,
   kAllocatorTagOatFile,
   kAllocatorTagDexFileVerifier,
+  kAllocatorTagRosAlloc,
   kAllocatorTagCount,  // Must always be last element.
 };
 std::ostream& operator<<(std::ostream& os, const AllocatorTag& tag);
@@ -149,6 +150,10 @@
     Key, T, Compare, TrackingAllocator<std::pair<Key, T>, kTag>> {
 };
 
+template<class Key, AllocatorTag kTag, class Compare = std::less<Key>>
+class AllocationTrackingSet : public std::set<Key, Compare, TrackingAllocator<Key, kTag>> {
+};
+
 }  // namespace art
 
 #endif  // ART_RUNTIME_BASE_ALLOCATOR_H_
diff --git a/runtime/base/mutex.cc b/runtime/base/mutex.cc
index 455680b..2c95ede 100644
--- a/runtime/base/mutex.cc
+++ b/runtime/base/mutex.cc
@@ -884,6 +884,10 @@
     DCHECK(heap_bitmap_lock_ == nullptr);
     heap_bitmap_lock_ = new ReaderWriterMutex("heap bitmap lock", current_lock_level);
 
+    UPDATE_CURRENT_LOCK_LEVEL(kTraceLock);
+    DCHECK(trace_lock_ == nullptr);
+    trace_lock_ = new Mutex("trace lock", current_lock_level);
+
     UPDATE_CURRENT_LOCK_LEVEL(kRuntimeShutdownLock);
     DCHECK(runtime_shutdown_lock_ == nullptr);
     runtime_shutdown_lock_ = new Mutex("runtime shutdown lock", current_lock_level);
@@ -892,10 +896,6 @@
     DCHECK(profiler_lock_ == nullptr);
     profiler_lock_ = new Mutex("profiler lock", current_lock_level);
 
-    UPDATE_CURRENT_LOCK_LEVEL(kTraceLock);
-    DCHECK(trace_lock_ == nullptr);
-    trace_lock_ = new Mutex("trace lock", current_lock_level);
-
     UPDATE_CURRENT_LOCK_LEVEL(kDeoptimizationLock);
     DCHECK(deoptimization_lock_ == nullptr);
     deoptimization_lock_ = new Mutex("Deoptimization lock", current_lock_level);
diff --git a/runtime/base/mutex.h b/runtime/base/mutex.h
index 20f58de..8d2cdce 100644
--- a/runtime/base/mutex.h
+++ b/runtime/base/mutex.h
@@ -92,12 +92,12 @@
   kBreakpointInvokeLock,
   kAllocTrackerLock,
   kDeoptimizationLock,
-  kTraceLock,
   kProfilerLock,
   kJdwpEventListLock,
   kJdwpAttachLock,
   kJdwpStartLock,
   kRuntimeShutdownLock,
+  kTraceLock,
   kHeapBitmapLock,
   kMutatorLock,
   kThreadListSuspendThreadLock,
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 001032c..aced954 100644
--- a/runtime/debugger.cc
+++ b/runtime/debugger.cc
@@ -311,7 +311,7 @@
 static Dbg::HpsgWhen gDdmNhsgWhen = Dbg::HPSG_WHEN_NEVER;
 static Dbg::HpsgWhat gDdmNhsgWhat;
 
-static ObjectRegistry* gRegistry = nullptr;
+ObjectRegistry* Dbg::gRegistry = nullptr;
 
 // Recent allocation tracking.
 AllocRecord* Dbg::recent_allocation_records_ = nullptr;  // TODO: CircularBuffer<AllocRecord>
@@ -401,7 +401,7 @@
 
 static mirror::Array* DecodeNonNullArray(JDWP::RefTypeId id, JDWP::JdwpError* error)
     SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
-  mirror::Object* o = gRegistry->Get<mirror::Object*>(id, error);
+  mirror::Object* o = Dbg::GetObjectRegistry()->Get<mirror::Object*>(id, error);
   if (o == nullptr) {
     *error = JDWP::ERR_INVALID_OBJECT;
     return nullptr;
@@ -416,7 +416,7 @@
 
 static mirror::Class* DecodeClass(JDWP::RefTypeId id, JDWP::JdwpError* error)
     SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
-  mirror::Object* o = gRegistry->Get<mirror::Object*>(id, error);
+  mirror::Object* o = Dbg::GetObjectRegistry()->Get<mirror::Object*>(id, error);
   if (o == nullptr) {
     *error = JDWP::ERR_INVALID_OBJECT;
     return nullptr;
@@ -434,7 +434,7 @@
     EXCLUSIVE_LOCKS_REQUIRED(Locks::thread_list_lock_)
     LOCKS_EXCLUDED(Locks::thread_suspend_count_lock_)
     SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
-  mirror::Object* thread_peer = gRegistry->Get<mirror::Object*>(thread_id, error);
+  mirror::Object* thread_peer = Dbg::GetObjectRegistry()->Get<mirror::Object*>(thread_id, error);
   if (thread_peer == nullptr) {
     // This isn't even an object.
     *error = JDWP::ERR_INVALID_OBJECT;
@@ -511,8 +511,7 @@
  *
  * Null objects are tagged JT_OBJECT.
  */
-static JDWP::JdwpTag TagFromObject(const ScopedObjectAccessUnchecked& soa, mirror::Object* o)
-    SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+JDWP::JdwpTag Dbg::TagFromObject(const ScopedObjectAccessUnchecked& soa, mirror::Object* o) {
   return (o == nullptr) ? JDWP::JT_OBJECT : TagFromClass(soa, o->GetClass());
 }
 
@@ -842,8 +841,13 @@
   if (!o->IsClass()) {
     return StringPrintf("non-class %p", o);  // This is only used for debugging output anyway.
   }
+  return GetClassName(o->AsClass());
+}
+
+std::string Dbg::GetClassName(mirror::Class* klass) {
+  DCHECK(klass != nullptr);
   std::string temp;
-  return DescriptorToName(o->AsClass()->GetDescriptor(&temp));
+  return DescriptorToName(klass->GetDescriptor(&temp));
 }
 
 JDWP::JdwpError Dbg::GetClassObject(JDWP::RefTypeId id, JDWP::ObjectId* class_object_id) {
@@ -1108,8 +1112,7 @@
   gRegistry->DisposeObject(object_id, reference_count);
 }
 
-static JDWP::JdwpTypeTag GetTypeTag(mirror::Class* klass)
-    SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+JDWP::JdwpTypeTag Dbg::GetTypeTag(mirror::Class* klass) {
   DCHECK(klass != nullptr);
   if (klass->IsArrayClass()) {
     return JDWP::TT_ARRAY;
@@ -1422,17 +1425,7 @@
   return JDWP::ERR_NONE;
 }
 
-bool Dbg::MatchType(JDWP::RefTypeId instance_class_id, JDWP::RefTypeId class_id) {
-  JDWP::JdwpError error;
-  mirror::Class* c1 = DecodeClass(instance_class_id, &error);
-  CHECK(c1 != nullptr);
-  mirror::Class* c2 = DecodeClass(class_id, &error);
-  CHECK(c2 != nullptr);
-  return c2->IsAssignableFrom(c1);
-}
-
-static JDWP::FieldId ToFieldId(const mirror::ArtField* f)
-    SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+JDWP::FieldId Dbg::ToFieldId(const mirror::ArtField* f) {
   CHECK(!kMovingFields);
   return static_cast<JDWP::FieldId>(reinterpret_cast<uintptr_t>(f));
 }
@@ -1455,10 +1448,49 @@
   return reinterpret_cast<mirror::ArtMethod*>(static_cast<uintptr_t>(mid));
 }
 
-static void SetLocation(JDWP::JdwpLocation* location, mirror::ArtMethod* m, uint32_t dex_pc)
+bool Dbg::MatchThread(JDWP::ObjectId expected_thread_id, Thread* event_thread) {
+  CHECK(event_thread != nullptr);
+  JDWP::JdwpError error;
+  mirror::Object* expected_thread_peer = gRegistry->Get<mirror::Object*>(expected_thread_id,
+                                                                         &error);
+  return expected_thread_peer == event_thread->GetPeer();
+}
+
+bool Dbg::MatchLocation(const JDWP::JdwpLocation& expected_location,
+                        const JDWP::EventLocation& event_location) {
+  if (expected_location.dex_pc != event_location.dex_pc) {
+    return false;
+  }
+  mirror::ArtMethod* m = FromMethodId(expected_location.method_id);
+  return m == event_location.method;
+}
+
+bool Dbg::MatchType(mirror::Class* event_class, JDWP::RefTypeId class_id) {
+  JDWP::JdwpError error;
+  mirror::Class* expected_class = DecodeClass(class_id, &error);
+  CHECK(expected_class != nullptr);
+  return expected_class->IsAssignableFrom(event_class);
+}
+
+bool Dbg::MatchField(JDWP::RefTypeId expected_type_id, JDWP::FieldId expected_field_id,
+                     mirror::ArtField* event_field) {
+  mirror::ArtField* expected_field = FromFieldId(expected_field_id);
+  if (expected_field != event_field) {
+    return false;
+  }
+  return Dbg::MatchType(event_field->GetDeclaringClass(), expected_type_id);
+}
+
+bool Dbg::MatchInstance(JDWP::ObjectId expected_instance_id, mirror::Object* event_instance) {
+  JDWP::JdwpError error;
+  mirror::Object* modifier_instance = gRegistry->Get<mirror::Object*>(expected_instance_id, &error);
+  return modifier_instance == event_instance;
+}
+
+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);
@@ -1757,7 +1789,7 @@
     return error;
   }
 
-  mirror::Object* o = gRegistry->Get<mirror::Object*>(object_id, &error);
+  mirror::Object* o = Dbg::GetObjectRegistry()->Get<mirror::Object*>(object_id, &error);
   if ((!is_static && o == nullptr) || error != JDWP::ERR_NONE) {
     return JDWP::ERR_INVALID_OBJECT;
   }
@@ -1819,7 +1851,7 @@
                                          uint64_t value, int width, bool is_static)
     SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
   JDWP::JdwpError error;
-  mirror::Object* o = gRegistry->Get<mirror::Object*>(object_id, &error);
+  mirror::Object* o = Dbg::GetObjectRegistry()->Get<mirror::Object*>(object_id, &error);
   if ((!is_static && o == nullptr) || error != JDWP::ERR_NONE) {
     return JDWP::ERR_INVALID_OBJECT;
   }
@@ -1853,7 +1885,7 @@
       f->Set32<false>(o, value);
     }
   } else {
-    mirror::Object* v = gRegistry->Get<mirror::Object*>(value, &error);
+    mirror::Object* v = Dbg::GetObjectRegistry()->Get<mirror::Object*>(value, &error);
     if (error != JDWP::ERR_NONE) {
       return JDWP::ERR_INVALID_OBJECT;
     }
@@ -1886,11 +1918,25 @@
   return SetFieldValueImpl(0, field_id, value, width, true);
 }
 
-std::string Dbg::StringToUtf8(JDWP::ObjectId string_id) {
+JDWP::JdwpError Dbg::StringToUtf8(JDWP::ObjectId string_id, std::string* str) {
   JDWP::JdwpError error;
-  mirror::String* s = gRegistry->Get<mirror::String*>(string_id, &error);
-  CHECK(s != nullptr) << error;
-  return s->ToModifiedUtf8();
+  mirror::Object* obj = gRegistry->Get<mirror::Object*>(string_id, &error);
+  if (error != JDWP::ERR_NONE) {
+    return error;
+  }
+  if (obj == nullptr) {
+    return JDWP::ERR_INVALID_OBJECT;
+  }
+  {
+    ScopedObjectAccessUnchecked soa(Thread::Current());
+    mirror::Class* java_lang_String = soa.Decode<mirror::Class*>(WellKnownClasses::java_lang_String);
+    if (!java_lang_String->IsAssignableFrom(obj->GetClass())) {
+      // This isn't a string.
+      return JDWP::ERR_INVALID_STRING;
+    }
+  }
+  *str = obj->AsString()->ToModifiedUtf8();
+  return JDWP::ERR_NONE;
 }
 
 void Dbg::OutputJValue(JDWP::JdwpTag tag, const JValue* return_value, JDWP::ExpandBuf* pReply) {
@@ -1973,7 +2019,8 @@
 static mirror::Object* DecodeThreadGroup(ScopedObjectAccessUnchecked& soa,
                                          JDWP::ObjectId thread_group_id, JDWP::JdwpError* error)
     SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
-  mirror::Object* thread_group = gRegistry->Get<mirror::Object*>(thread_group_id, error);
+  mirror::Object* thread_group = Dbg::GetObjectRegistry()->Get<mirror::Object*>(thread_group_id,
+                                                                                error);
   if (*error != JDWP::ERR_NONE) {
     return nullptr;
   }
@@ -2048,8 +2095,9 @@
   const int32_t size = size_field->GetInt(groups_array_list);
 
   // Copy the first 'size' elements out of the array into the result.
+  ObjectRegistry* registry = Dbg::GetObjectRegistry();
   for (int32_t i = 0; i < size; ++i) {
-    child_thread_group_ids->push_back(gRegistry->Add(groups_array->Get(i)));
+    child_thread_group_ids->push_back(registry->Add(groups_array->Get(i)));
   }
 }
 
@@ -2282,7 +2330,7 @@
       if (depth_ >= start_frame_) {
         JDWP::FrameId frame_id(GetFrameId());
         JDWP::JdwpLocation location;
-        SetLocation(&location, GetMethod(), GetDexPc());
+        SetJdwpLocation(&location, GetMethod(), GetDexPc());
         VLOG(jdwp) << StringPrintf("    Frame %3zd: id=%3" PRIu64 " ", depth_, frame_id) << location;
         expandBufAdd8BE(buf_, frame_id);
         expandBufAddLocation(buf_, location);
@@ -2314,8 +2362,12 @@
 }
 
 JDWP::ObjectId Dbg::GetThreadSelfId() {
+  return GetThreadId(Thread::Current());
+}
+
+JDWP::ObjectId Dbg::GetThreadId(Thread* thread) {
   ScopedObjectAccessUnchecked soa(Thread::Current());
-  return gRegistry->Add(soa.Self()->GetPeer());
+  return gRegistry->Add(thread->GetPeer());
 }
 
 void Dbg::SuspendVM() {
@@ -2719,16 +2771,15 @@
   return visitor.error_;
 }
 
-JDWP::ObjectId Dbg::GetThisObjectIdForEvent(mirror::Object* this_object) {
-  // If 'this_object' isn't already in the registry, we know that we're not looking for it, so
-  // there's no point adding it to the registry and burning through ids.
-  // When registering an event request with an instance filter, we've been given an existing object
-  // id so it must already be present in the registry when the event fires.
-  JDWP::ObjectId this_id = 0;
-  if (this_object != nullptr && gRegistry->Contains(this_object)) {
-    this_id = gRegistry->Add(this_object);
+static void SetEventLocation(JDWP::EventLocation* location, mirror::ArtMethod* m, uint32_t dex_pc)
+    SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+  DCHECK(location != nullptr);
+  if (m == nullptr) {
+    memset(location, 0, sizeof(*location));
+  } else {
+    location->method = m;
+    location->dex_pc = (m->IsNative() || m->IsProxyMethod()) ? static_cast<uint32_t>(-1) : dex_pc;
   }
-  return this_id;
 }
 
 void Dbg::PostLocationEvent(mirror::ArtMethod* m, int dex_pc, mirror::Object* this_object,
@@ -2738,12 +2789,10 @@
   }
   DCHECK(m != nullptr);
   DCHECK_EQ(m->IsStatic(), this_object == nullptr);
-  JDWP::JdwpLocation location;
-  SetLocation(&location, m, dex_pc);
+  JDWP::EventLocation location;
+  SetEventLocation(&location, m, dex_pc);
 
-  // We need 'this' for InstanceOnly filters only.
-  JDWP::ObjectId this_id = GetThisObjectIdForEvent(this_object);
-  gJdwpState->PostLocationEvent(&location, this_id, event_flags, return_value);
+  gJdwpState->PostLocationEvent(&location, this_object, event_flags, return_value);
 }
 
 void Dbg::PostFieldAccessEvent(mirror::ArtMethod* m, int dex_pc,
@@ -2753,14 +2802,10 @@
   }
   DCHECK(m != nullptr);
   DCHECK(f != nullptr);
-  JDWP::JdwpLocation location;
-  SetLocation(&location, m, dex_pc);
+  JDWP::EventLocation location;
+  SetEventLocation(&location, m, dex_pc);
 
-  JDWP::RefTypeId type_id = gRegistry->AddRefType(f->GetDeclaringClass());
-  JDWP::FieldId field_id = ToFieldId(f);
-  JDWP::ObjectId this_id = gRegistry->Add(this_object);
-
-  gJdwpState->PostFieldEvent(&location, type_id, field_id, this_id, nullptr, false);
+  gJdwpState->PostFieldEvent(&location, f, this_object, nullptr, false);
 }
 
 void Dbg::PostFieldModificationEvent(mirror::ArtMethod* m, int dex_pc,
@@ -2772,14 +2817,10 @@
   DCHECK(m != nullptr);
   DCHECK(f != nullptr);
   DCHECK(field_value != nullptr);
-  JDWP::JdwpLocation location;
-  SetLocation(&location, m, dex_pc);
+  JDWP::EventLocation location;
+  SetEventLocation(&location, m, dex_pc);
 
-  JDWP::RefTypeId type_id = gRegistry->AddRefType(f->GetDeclaringClass());
-  JDWP::FieldId field_id = ToFieldId(f);
-  JDWP::ObjectId this_id = gRegistry->Add(this_object);
-
-  gJdwpState->PostFieldEvent(&location, type_id, field_id, this_id, field_value, true);
+  gJdwpState->PostFieldEvent(&location, f, this_object, field_value, true);
 }
 
 void Dbg::PostException(const ThrowLocation& throw_location,
@@ -2788,33 +2829,20 @@
   if (!IsDebuggerActive()) {
     return;
   }
+  JDWP::EventLocation exception_throw_location;
+  SetEventLocation(&exception_throw_location, throw_location.GetMethod(), throw_location.GetDexPc());
+  JDWP::EventLocation exception_catch_location;
+  SetEventLocation(&exception_catch_location, catch_method, catch_dex_pc);
 
-  JDWP::JdwpLocation jdwp_throw_location;
-  SetLocation(&jdwp_throw_location, throw_location.GetMethod(), throw_location.GetDexPc());
-  JDWP::JdwpLocation catch_location;
-  SetLocation(&catch_location, catch_method, catch_dex_pc);
-
-  // We need 'this' for InstanceOnly filters only.
-  JDWP::ObjectId this_id = GetThisObjectIdForEvent(throw_location.GetThis());
-  JDWP::ObjectId exception_id = gRegistry->Add(exception_object);
-  JDWP::RefTypeId exception_class_id = gRegistry->AddRefType(exception_object->GetClass());
-
-  gJdwpState->PostException(&jdwp_throw_location, exception_id, exception_class_id, &catch_location,
-                            this_id);
+  gJdwpState->PostException(&exception_throw_location, exception_object, &exception_catch_location,
+                            throw_location.GetThis());
 }
 
 void Dbg::PostClassPrepare(mirror::Class* c) {
   if (!IsDebuggerActive()) {
     return;
   }
-
-  // OLD-TODO - we currently always send both "verified" and "prepared" since
-  // debuggers seem to like that.  There might be some advantage to honesty,
-  // since the class may not yet be verified.
-  int state = JDWP::CS_VERIFIED | JDWP::CS_PREPARED;
-  JDWP::JdwpTypeTag tag = GetTypeTag(c);
-  std::string temp;
-  gJdwpState->PostClassPrepare(tag, gRegistry->Add(c), c->GetDescriptor(&temp), state);
+  gJdwpState->PostClassPrepare(c);
 }
 
 void Dbg::UpdateDebugger(Thread* thread, mirror::Object* this_object,
@@ -3231,7 +3259,7 @@
         self_suspend_ = true;
       } else {
         soa.Self()->TransitionFromRunnableToSuspended(kWaitingForDebuggerSuspension);
-        jobject thread_peer = gRegistry->GetJObject(thread_id);
+        jobject thread_peer = Dbg::GetObjectRegistry()->GetJObject(thread_id);
         bool timed_out;
         Thread* suspended_thread;
         {
@@ -3894,9 +3922,7 @@
 
 void Dbg::PostThreadStartOrStop(Thread* t, uint32_t type) {
   if (IsDebuggerActive()) {
-    ScopedObjectAccessUnchecked soa(Thread::Current());
-    JDWP::ObjectId id = gRegistry->Add(t->GetPeer());
-    gJdwpState->PostThreadChange(id, type == CHUNK_TYPE("THCR"));
+    gJdwpState->PostThreadChange(t, type == CHUNK_TYPE("THCR"));
   }
   Dbg::DdmSendThreadNotification(t, type);
 }
@@ -4374,7 +4400,7 @@
       recent_allocation_records_ = new AllocRecord[alloc_record_max_];
       CHECK(recent_allocation_records_ != nullptr);
     }
-    Runtime::Current()->GetInstrumentation()->InstrumentQuickAllocEntryPoints();
+    Runtime::Current()->GetInstrumentation()->InstrumentQuickAllocEntryPoints(false);
   } else {
     {
       ScopedObjectAccess soa(self);  // For type_cache_.Clear();
@@ -4390,7 +4416,7 @@
       type_cache_.Clear();
     }
     // If an allocation comes in before we uninstrument, we will safely drop it on the floor.
-    Runtime::Current()->GetInstrumentation()->UninstrumentQuickAllocEntryPoints();
+    Runtime::Current()->GetInstrumentation()->UninstrumentQuickAllocEntryPoints(false);
   }
 }
 
diff --git a/runtime/debugger.h b/runtime/debugger.h
index ab758ca..97985ec 100644
--- a/runtime/debugger.h
+++ b/runtime/debugger.h
@@ -43,6 +43,8 @@
 class Throwable;
 }  // namespace mirror
 class AllocRecord;
+class ObjectRegistry;
+class ScopedObjectAccessUnchecked;
 class Thread;
 class ThrowLocation;
 
@@ -250,6 +252,8 @@
    */
   static std::string GetClassName(JDWP::RefTypeId id)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  static std::string GetClassName(mirror::Class* klass)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
   static JDWP::JdwpError GetClassObject(JDWP::RefTypeId id, JDWP::ObjectId* class_object_id)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
   static JDWP::JdwpError GetSuperclass(JDWP::RefTypeId id, JDWP::RefTypeId* superclass_id)
@@ -294,7 +298,24 @@
                                            JDWP::ObjectId* new_array)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
-  static bool MatchType(JDWP::RefTypeId instance_class_id, JDWP::RefTypeId class_id)
+  //
+  // Event filtering.
+  //
+  static bool MatchThread(JDWP::ObjectId expected_thread_id, Thread* event_thread)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+
+  static bool MatchLocation(const JDWP::JdwpLocation& expected_location,
+                            const JDWP::EventLocation& event_location)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+
+  static bool MatchType(mirror::Class* event_class, JDWP::RefTypeId class_id)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+
+  static bool MatchField(JDWP::RefTypeId expected_type_id, JDWP::FieldId expected_field_id,
+                         mirror::ArtField* event_field)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+
+  static bool MatchInstance(JDWP::ObjectId expected_instance_id, mirror::Object* event_instance)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
   //
@@ -381,7 +402,7 @@
   static JDWP::JdwpError SetStaticFieldValue(JDWP::FieldId field_id, uint64_t value, int width)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
-  static std::string StringToUtf8(JDWP::ObjectId string_id)
+  static JDWP::JdwpError StringToUtf8(JDWP::ObjectId string_id, std::string* str)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
   static void OutputJValue(JDWP::JdwpTag tag, const JValue* return_value, JDWP::ExpandBuf* pReply)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
@@ -431,8 +452,9 @@
       LOCKS_EXCLUDED(Locks::thread_list_lock_)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
-  static JDWP::ObjectId GetThreadSelfId()
-      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  static JDWP::ObjectId GetThreadSelfId() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  static JDWP::ObjectId GetThreadId(Thread* thread) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+
   static void SuspendVM()
       LOCKS_EXCLUDED(Locks::thread_list_lock_,
                      Locks::thread_suspend_count_lock_);
@@ -602,6 +624,22 @@
   static void DdmSendHeapSegments(bool native)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
+  static ObjectRegistry* GetObjectRegistry() {
+    return gRegistry;
+  }
+
+  static JDWP::JdwpTag TagFromObject(const ScopedObjectAccessUnchecked& soa, mirror::Object* o)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+
+  static JDWP::JdwpTypeTag GetTypeTag(mirror::Class* klass)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+
+  static JDWP::FieldId ToFieldId(const mirror::ArtField* f)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+
+  static void SetJdwpLocation(JDWP::JdwpLocation* location, mirror::ArtMethod* m, uint32_t dex_pc)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+
  private:
   static void DdmBroadcast(bool connect) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
   static void PostThreadStartOrStop(Thread*, uint32_t)
@@ -612,9 +650,6 @@
                                 const JValue* return_value)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
-  static JDWP::ObjectId GetThisObjectIdForEvent(mirror::Object* this_object)
-      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
-
   static void ProcessDeoptimizationRequest(const DeoptimizationRequest& request)
       EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_);
 
@@ -627,6 +662,8 @@
   static size_t alloc_record_head_ GUARDED_BY(Locks::alloc_tracker_lock_);
   static size_t alloc_record_count_ GUARDED_BY(Locks::alloc_tracker_lock_);
 
+  static ObjectRegistry* gRegistry;
+
   // Deoptimization requests to be processed each time the event list is updated. This is used when
   // registering and unregistering events so we do not deoptimize while holding the event list
   // lock.
diff --git a/runtime/gc/allocator/rosalloc.cc b/runtime/gc/allocator/rosalloc.cc
index ad22a2e..a7e5e74 100644
--- a/runtime/gc/allocator/rosalloc.cc
+++ b/runtime/gc/allocator/rosalloc.cc
@@ -569,7 +569,7 @@
 
 RosAlloc::Run* RosAlloc::RefillRun(Thread* self, size_t idx) {
   // Get the lowest address non-full run from the binary tree.
-  std::set<Run*>* const bt = &non_full_runs_[idx];
+  auto* const bt = &non_full_runs_[idx];
   if (!bt->empty()) {
     // If there's one, use it as the current run.
     auto it = bt->begin();
@@ -767,7 +767,7 @@
   }
   // Free the slot in the run.
   run->FreeSlot(ptr);
-  std::set<Run*>* non_full_runs = &non_full_runs_[idx];
+  auto* non_full_runs = &non_full_runs_[idx];
   if (run->IsAllFree()) {
     // It has just become completely free. Free the pages of this run.
     std::set<Run*>::iterator pos = non_full_runs->find(run);
@@ -793,9 +793,8 @@
     // already in the non-full run set (i.e., it was full) insert it
     // into the non-full run set.
     if (run != current_runs_[idx]) {
-      std::unordered_set<Run*, hash_run, eq_run>* full_runs =
-          kIsDebugBuild ? &full_runs_[idx] : NULL;
-      std::set<Run*>::iterator pos = non_full_runs->find(run);
+      auto* full_runs = kIsDebugBuild ? &full_runs_[idx] : NULL;
+      auto pos = non_full_runs->find(run);
       if (pos == non_full_runs->end()) {
         DCHECK(run_was_full);
         DCHECK(full_runs->find(run) != full_runs->end());
@@ -1266,9 +1265,8 @@
       }
       // Check if the run should be moved to non_full_runs_ or
       // free_page_runs_.
-      std::set<Run*>* non_full_runs = &non_full_runs_[idx];
-      std::unordered_set<Run*, hash_run, eq_run>* full_runs =
-          kIsDebugBuild ? &full_runs_[idx] : NULL;
+      auto* non_full_runs = &non_full_runs_[idx];
+      auto* full_runs = kIsDebugBuild ? &full_runs_[idx] : NULL;
       if (run->IsAllFree()) {
         // It has just become completely free. Free the pages of the
         // run.
@@ -2056,7 +2054,7 @@
     // in a run set.
     if (!is_current_run) {
       MutexLock mu(self, rosalloc->lock_);
-      std::set<Run*>& non_full_runs = rosalloc->non_full_runs_[idx];
+      auto& non_full_runs = rosalloc->non_full_runs_[idx];
       // If it's all free, it must be a free page run rather than a run.
       CHECK(!IsAllFree()) << "A free run must be in a free page run set " << Dump();
       if (!IsFull()) {
@@ -2066,7 +2064,7 @@
       } else {
         // If it's full, it must in the full run set (debug build only.)
         if (kIsDebugBuild) {
-          std::unordered_set<Run*, hash_run, eq_run>& full_runs = rosalloc->full_runs_[idx];
+          auto& full_runs = rosalloc->full_runs_[idx];
           CHECK(full_runs.find(this) != full_runs.end())
               << " A full run isn't in the full run set " << Dump();
         }
diff --git a/runtime/gc/allocator/rosalloc.h b/runtime/gc/allocator/rosalloc.h
index b2a5a3c..2fbd97a 100644
--- a/runtime/gc/allocator/rosalloc.h
+++ b/runtime/gc/allocator/rosalloc.h
@@ -26,6 +26,7 @@
 #include <unordered_set>
 #include <vector>
 
+#include "base/allocator.h"
 #include "base/mutex.h"
 #include "base/logging.h"
 #include "globals.h"
@@ -53,7 +54,7 @@
       size_t pm_idx = rosalloc->ToPageMapIndex(fpr_base);
       size_t byte_size = rosalloc->free_page_run_size_map_[pm_idx];
       DCHECK_GE(byte_size, static_cast<size_t>(0));
-      DCHECK_EQ(byte_size % kPageSize, static_cast<size_t>(0));
+      DCHECK_ALIGNED(byte_size, kPageSize);
       return byte_size;
     }
     void SetByteSize(RosAlloc* rosalloc, size_t byte_size)
@@ -403,6 +404,7 @@
 
   // We use thread-local runs for the size Brackets whose indexes
   // are less than this index. We use shared (current) runs for the rest.
+
   static const size_t kNumThreadLocalSizeBrackets = 11;
 
  private:
@@ -423,12 +425,13 @@
 
   // The run sets that hold the runs whose slots are not all
   // full. non_full_runs_[i] is guarded by size_bracket_locks_[i].
-  std::set<Run*> non_full_runs_[kNumOfSizeBrackets];
+  AllocationTrackingSet<Run*, kAllocatorTagRosAlloc> non_full_runs_[kNumOfSizeBrackets];
   // The run sets that hold the runs whose slots are all full. This is
   // debug only. full_runs_[i] is guarded by size_bracket_locks_[i].
-  std::unordered_set<Run*, hash_run, eq_run> full_runs_[kNumOfSizeBrackets];
+  std::unordered_set<Run*, hash_run, eq_run, TrackingAllocator<Run*, kAllocatorTagRosAlloc>>
+      full_runs_[kNumOfSizeBrackets];
   // The set of free pages.
-  std::set<FreePageRun*> free_page_runs_ GUARDED_BY(lock_);
+  AllocationTrackingSet<FreePageRun*, kAllocatorTagRosAlloc> free_page_runs_ GUARDED_BY(lock_);
   // The dedicated full run, it is always full and shared by all threads when revoking happens.
   // This is an optimization since enables us to avoid a null check for revoked runs.
   static Run* dedicated_full_run_;
@@ -460,7 +463,8 @@
   // The table that indicates the size of free page runs. These sizes
   // are stored here to avoid storing in the free page header and
   // release backing pages.
-  std::vector<size_t> free_page_run_size_map_ GUARDED_BY(lock_);
+  std::vector<size_t, TrackingAllocator<size_t, kAllocatorTagRosAlloc>> free_page_run_size_map_
+      GUARDED_BY(lock_);
   // The global lock. Used to guard the page map, the free page set,
   // and the footprint.
   Mutex lock_ DEFAULT_MUTEX_ACQUIRED_AFTER;
diff --git a/runtime/gc/heap.cc b/runtime/gc/heap.cc
index 3e3b964..b744a62 100644
--- a/runtime/gc/heap.cc
+++ b/runtime/gc/heap.cc
@@ -426,7 +426,7 @@
     }
   }
   if (running_on_valgrind_) {
-    Runtime::Current()->GetInstrumentation()->InstrumentQuickAllocEntryPoints();
+    Runtime::Current()->GetInstrumentation()->InstrumentQuickAllocEntryPoints(false);
   }
   if (VLOG_IS_ON(heap) || VLOG_IS_ON(startup)) {
     LOG(INFO) << "Heap() exiting";
@@ -2104,6 +2104,7 @@
   // Back to back GCs can cause 0 ms of wait time in between GC invocations.
   if (LIKELY(ms_delta != 0)) {
     allocation_rate_ = ((gc_start_size - last_gc_size_) * 1000) / ms_delta;
+    ATRACE_INT("Allocation rate KB/s", allocation_rate_ / KB);
     VLOG(heap) << "Allocation rate: " << PrettySize(allocation_rate_) << "/s";
   }
 
diff --git a/runtime/gc/reference_processor.cc b/runtime/gc/reference_processor.cc
index 75de623..bfaa2bb 100644
--- a/runtime/gc/reference_processor.cc
+++ b/runtime/gc/reference_processor.cc
@@ -132,7 +132,6 @@
     if (concurrent) {
       StartPreservingReferences(self);
     }
-
     soft_reference_queue_.ForwardSoftReferences(&PreserveSoftReferenceCallback,
                                                 &process_references_args_);
     process_mark_stack_callback(arg);
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/instrumentation.cc b/runtime/instrumentation.cc
index 0f45b9e..a2e88a6 100644
--- a/runtime/instrumentation.cc
+++ b/runtime/instrumentation.cc
@@ -597,10 +597,13 @@
   thread->ResetQuickAllocEntryPointsForThread();
 }
 
-void Instrumentation::SetEntrypointsInstrumented(bool instrumented) {
+void Instrumentation::SetEntrypointsInstrumented(bool instrumented, bool suspended) {
   Runtime* runtime = Runtime::Current();
   ThreadList* tl = runtime->GetThreadList();
-  if (runtime->IsStarted()) {
+  if (suspended) {
+    Locks::mutator_lock_->AssertExclusiveHeld(Thread::Current());
+  }
+  if (runtime->IsStarted() && !suspended) {
     tl->SuspendAll();
   }
   {
@@ -608,30 +611,30 @@
     SetQuickAllocEntryPointsInstrumented(instrumented);
     ResetQuickAllocEntryPoints();
   }
-  if (runtime->IsStarted()) {
+  if (runtime->IsStarted() && !suspended) {
     tl->ResumeAll();
   }
 }
 
-void Instrumentation::InstrumentQuickAllocEntryPoints() {
+void Instrumentation::InstrumentQuickAllocEntryPoints(bool suspended) {
   // TODO: the read of quick_alloc_entry_points_instrumentation_counter_ is racey and this code
   //       should be guarded by a lock.
   DCHECK_GE(quick_alloc_entry_points_instrumentation_counter_.LoadSequentiallyConsistent(), 0);
   const bool enable_instrumentation =
       quick_alloc_entry_points_instrumentation_counter_.FetchAndAddSequentiallyConsistent(1) == 0;
   if (enable_instrumentation) {
-    SetEntrypointsInstrumented(true);
+    SetEntrypointsInstrumented(true, suspended);
   }
 }
 
-void Instrumentation::UninstrumentQuickAllocEntryPoints() {
+void Instrumentation::UninstrumentQuickAllocEntryPoints(bool suspended) {
   // TODO: the read of quick_alloc_entry_points_instrumentation_counter_ is racey and this code
   //       should be guarded by a lock.
   DCHECK_GT(quick_alloc_entry_points_instrumentation_counter_.LoadSequentiallyConsistent(), 0);
   const bool disable_instrumentation =
       quick_alloc_entry_points_instrumentation_counter_.FetchAndSubSequentiallyConsistent(1) == 1;
   if (disable_instrumentation) {
-    SetEntrypointsInstrumented(false);
+    SetEntrypointsInstrumented(false, suspended);
   }
 }
 
diff --git a/runtime/instrumentation.h b/runtime/instrumentation.h
index d05cee5..3c1c756 100644
--- a/runtime/instrumentation.h
+++ b/runtime/instrumentation.h
@@ -182,10 +182,10 @@
     return interpreter_handler_table_;
   }
 
-  void InstrumentQuickAllocEntryPoints() LOCKS_EXCLUDED(Locks::thread_list_lock_,
-                                                        Locks::runtime_shutdown_lock_);
-  void UninstrumentQuickAllocEntryPoints() LOCKS_EXCLUDED(Locks::thread_list_lock_,
-                                                          Locks::runtime_shutdown_lock_);
+  void InstrumentQuickAllocEntryPoints(bool suspended)
+      LOCKS_EXCLUDED(Locks::thread_list_lock_, Locks::runtime_shutdown_lock_);
+  void UninstrumentQuickAllocEntryPoints(bool suspended)
+      LOCKS_EXCLUDED(Locks::thread_list_lock_, Locks::runtime_shutdown_lock_);
   void ResetQuickAllocEntryPoints() EXCLUSIVE_LOCKS_REQUIRED(Locks::runtime_shutdown_lock_);
 
   // Update the code of a method respecting any installed stubs.
@@ -350,7 +350,7 @@
 
   // No thread safety analysis to get around SetQuickAllocEntryPointsInstrumented requiring
   // exclusive access to mutator lock which you can't get if the runtime isn't started.
-  void SetEntrypointsInstrumented(bool instrumented) NO_THREAD_SAFETY_ANALYSIS;
+  void SetEntrypointsInstrumented(bool instrumented, bool suspended) NO_THREAD_SAFETY_ANALYSIS;
 
   void MethodEnterEventImpl(Thread* thread, mirror::Object* this_object,
                             mirror::ArtMethod* method, uint32_t dex_pc) const
diff --git a/runtime/jdwp/jdwp.h b/runtime/jdwp/jdwp.h
index b5b6298..0c9451c 100644
--- a/runtime/jdwp/jdwp.h
+++ b/runtime/jdwp/jdwp.h
@@ -36,8 +36,13 @@
 class Thread;
 
 namespace mirror {
+  class ArtField;
   class ArtMethod;
+  class Class;
+  class Object;
+  class Throwable;
 }  // namespace mirror
+class Thread;
 
 namespace JDWP {
 
@@ -65,6 +70,11 @@
 static inline void expandBufAddRefTypeId(ExpandBuf* pReply, RefTypeId id) { expandBufAdd8BE(pReply, id); }
 static inline void expandBufAddFrameId(ExpandBuf* pReply, FrameId id) { expandBufAdd8BE(pReply, id); }
 
+struct EventLocation {
+  mirror::ArtMethod* method;
+  uint32_t dex_pc;
+};
+
 /*
  * Holds a JDWP "location".
  */
@@ -178,7 +188,7 @@
    * The VM has finished initializing.  Only called when the debugger is
    * connected at the time initialization completes.
    */
-  bool PostVMStart() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  bool PostVMStart() LOCKS_EXCLUDED(event_list_lock_) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
   /*
    * A location of interest has been reached.  This is used for breakpoints,
@@ -192,8 +202,9 @@
    *
    * "returnValue" is non-null for MethodExit events only.
    */
-  bool PostLocationEvent(const JdwpLocation* pLoc, ObjectId thisPtr, int eventFlags,
+  bool PostLocationEvent(const EventLocation* pLoc, mirror::Object* thisPtr, int eventFlags,
                          const JValue* returnValue)
+     LOCKS_EXCLUDED(event_list_lock_)
      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
   /*
@@ -203,8 +214,9 @@
    * "fieldValue" is non-null for field modification events only.
    * "is_modification" is true for field modification, false for field access.
    */
-  bool PostFieldEvent(const JdwpLocation* pLoc, RefTypeId typeId, FieldId fieldId,
-                      ObjectId thisPtr, const JValue* fieldValue, bool is_modification)
+  bool PostFieldEvent(const EventLocation* pLoc, mirror::ArtField* field, mirror::Object* thisPtr,
+                      const JValue* fieldValue, bool is_modification)
+      LOCKS_EXCLUDED(event_list_lock_)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
   /*
@@ -212,21 +224,23 @@
    *
    * Pass in a zeroed-out "*pCatchLoc" if the exception wasn't caught.
    */
-  bool PostException(const JdwpLocation* pThrowLoc, ObjectId excepId, RefTypeId excepClassId,
-                     const JdwpLocation* pCatchLoc, ObjectId thisPtr)
+  bool PostException(const EventLocation* pThrowLoc, mirror::Throwable* exception_object,
+                     const EventLocation* pCatchLoc, mirror::Object* thisPtr)
+      LOCKS_EXCLUDED(event_list_lock_)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
   /*
    * A thread has started or stopped.
    */
-  bool PostThreadChange(ObjectId threadId, bool start)
+  bool PostThreadChange(Thread* thread, bool start)
+      LOCKS_EXCLUDED(event_list_lock_)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
   /*
    * Class has been prepared.
    */
-  bool PostClassPrepare(JdwpTypeTag tag, RefTypeId refTypeId, const std::string& signature,
-                        int status)
+  bool PostClassPrepare(mirror::Class* klass)
+      LOCKS_EXCLUDED(event_list_lock_)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
   /*
diff --git a/runtime/jdwp/jdwp_event.cc b/runtime/jdwp/jdwp_event.cc
index fc39cc4..d61660b 100644
--- a/runtime/jdwp/jdwp_event.cc
+++ b/runtime/jdwp/jdwp_event.cc
@@ -27,6 +27,9 @@
 #include "jdwp/jdwp_constants.h"
 #include "jdwp/jdwp_expand_buf.h"
 #include "jdwp/jdwp_priv.h"
+#include "jdwp/object_registry.h"
+#include "mirror/art_field-inl.h"
+#include "scoped_thread_state_change.h"
 #include "thread-inl.h"
 
 /*
@@ -107,18 +110,17 @@
  * The rest will be zeroed.
  */
 struct ModBasket {
-  ModBasket() : pLoc(NULL), threadId(0), classId(0), excepClassId(0),
-                caught(false), fieldTypeID(0), fieldId(0), thisPtr(0) { }
+  ModBasket() : pLoc(nullptr), thread(nullptr), locationClass(nullptr), exceptionClass(nullptr),
+                caught(false), field(nullptr), thisPtr(nullptr) { }
 
-  const JdwpLocation* pLoc;           /* LocationOnly */
-  std::string         className;      /* ClassMatch/ClassExclude */
-  ObjectId            threadId;       /* ThreadOnly */
-  RefTypeId           classId;        /* ClassOnly */
-  RefTypeId           excepClassId;   /* ExceptionOnly */
-  bool                caught;         /* ExceptionOnly */
-  RefTypeId           fieldTypeID;    /* FieldOnly */
-  FieldId             fieldId;        /* FieldOnly */
-  ObjectId            thisPtr;        /* InstanceOnly */
+  const EventLocation*  pLoc;             /* LocationOnly */
+  std::string           className;        /* ClassMatch/ClassExclude */
+  Thread*               thread;           /* ThreadOnly */
+  mirror::Class*        locationClass;    /* ClassOnly */
+  mirror::Class*        exceptionClass;   /* ExceptionOnly */
+  bool                  caught;           /* ExceptionOnly */
+  mirror::ArtField*     field;            /* FieldOnly */
+  mirror::Object*       thisPtr;          /* InstanceOnly */
   /* nothing for StepOnly -- handled differently */
 };
 
@@ -295,9 +297,6 @@
 /*
  * Remove the event with the given ID from the list.
  *
- * Failure to find the event isn't really an error, but it is a little
- * weird.  (It looks like Eclipse will try to be extra careful and will
- * explicitly remove one-off single-step events.)
  */
 void JdwpState::UnregisterEventById(uint32_t requestId) {
   bool found = false;
@@ -317,7 +316,11 @@
   if (found) {
     Dbg::ManageDeoptimization();
   } else {
-    LOG(WARNING) << StringPrintf("Odd: no match when removing event reqId=0x%04x", requestId);
+    // Failure to find the event isn't really an error. For instance, it looks like Eclipse will
+    // try to be extra careful and will explicitly remove one-off single-step events (using a
+    // 'count' event modifier of 1). So the event may have already been removed as part of the
+    // event notification (see JdwpState::CleanupMatchList).
+    VLOG(jdwp) << StringPrintf("No match when removing event reqId=0x%04x", requestId);
   }
 }
 
@@ -463,12 +466,12 @@
       CHECK(false);  // should not be getting these
       break;
     case MK_THREAD_ONLY:
-      if (pMod->threadOnly.threadId != basket.threadId) {
+      if (!Dbg::MatchThread(pMod->threadOnly.threadId, basket.thread)) {
         return false;
       }
       break;
     case MK_CLASS_ONLY:
-      if (!Dbg::MatchType(basket.classId, pMod->classOnly.refTypeId)) {
+      if (!Dbg::MatchType(basket.locationClass, pMod->classOnly.refTypeId)) {
         return false;
       }
       break;
@@ -483,33 +486,32 @@
       }
       break;
     case MK_LOCATION_ONLY:
-      if (pMod->locationOnly.loc != *basket.pLoc) {
+      if (!Dbg::MatchLocation(pMod->locationOnly.loc, *basket.pLoc)) {
         return false;
       }
       break;
     case MK_EXCEPTION_ONLY:
-      if (pMod->exceptionOnly.refTypeId != 0 && !Dbg::MatchType(basket.excepClassId, pMod->exceptionOnly.refTypeId)) {
+      if (pMod->exceptionOnly.refTypeId != 0 &&
+          !Dbg::MatchType(basket.exceptionClass, pMod->exceptionOnly.refTypeId)) {
         return false;
       }
-      if ((basket.caught && !pMod->exceptionOnly.caught) || (!basket.caught && !pMod->exceptionOnly.uncaught)) {
+      if ((basket.caught && !pMod->exceptionOnly.caught) ||
+          (!basket.caught && !pMod->exceptionOnly.uncaught)) {
         return false;
       }
       break;
     case MK_FIELD_ONLY:
-      if (pMod->fieldOnly.fieldId != basket.fieldId) {
-        return false;
-      }
-      if (!Dbg::MatchType(basket.fieldTypeID, pMod->fieldOnly.refTypeId)) {
+      if (!Dbg::MatchField(pMod->fieldOnly.refTypeId, pMod->fieldOnly.fieldId, basket.field)) {
         return false;
       }
       break;
     case MK_STEP:
-      if (pMod->step.threadId != basket.threadId) {
+      if (!Dbg::MatchThread(pMod->step.threadId, basket.thread)) {
         return false;
       }
       break;
     case MK_INSTANCE_ONLY:
-      if (pMod->instanceOnly.objectId != basket.thisPtr) {
+      if (!Dbg::MatchInstance(pMod->instanceOnly.objectId, basket.thisPtr)) {
         return false;
       }
       break;
@@ -773,7 +775,7 @@
 }
 
 static void LogMatchingEventsAndThread(JdwpEvent** match_list, size_t match_count,
-                                       const ModBasket& basket)
+                                       ObjectId thread_id)
     SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
   for (size_t i = 0; i < match_count; ++i) {
     JdwpEvent* pEvent = match_list[i];
@@ -781,11 +783,19 @@
                << StringPrintf(" (requestId=%#" PRIx32 ")", pEvent->requestId);
   }
   std::string thread_name;
-  JdwpError error = Dbg::GetThreadName(basket.threadId, &thread_name);
+  JdwpError error = Dbg::GetThreadName(thread_id, &thread_name);
   if (error != JDWP::ERR_NONE) {
     thread_name = "<unknown>";
   }
-  VLOG(jdwp) << StringPrintf("  thread=%#" PRIx64, basket.threadId) << " " << thread_name;
+  VLOG(jdwp) << StringPrintf("  thread=%#" PRIx64, thread_id) << " " << thread_name;
+}
+
+static void SetJdwpLocationFromEventLocation(const JDWP::EventLocation* event_location,
+                                             JDWP::JdwpLocation* jdwp_location)
+    SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+  DCHECK(event_location != nullptr);
+  DCHECK(jdwp_location != nullptr);
+  Dbg::SetJdwpLocation(jdwp_location, event_location->method, event_location->dex_pc);
 }
 
 /*
@@ -809,14 +819,18 @@
  *  - Single-step to a line with a breakpoint.  Should get a single
  *    event message with both events in it.
  */
-bool JdwpState::PostLocationEvent(const JdwpLocation* pLoc, ObjectId thisPtr, int eventFlags,
-                                  const JValue* returnValue) {
+bool JdwpState::PostLocationEvent(const EventLocation* pLoc, mirror::Object* thisPtr,
+                                  int eventFlags, const JValue* returnValue) {
+  DCHECK(pLoc != nullptr);
+  DCHECK(pLoc->method != nullptr);
+  DCHECK_EQ(pLoc->method->IsStatic(), thisPtr == nullptr);
+
   ModBasket basket;
   basket.pLoc = pLoc;
-  basket.classId = pLoc->class_id;
+  basket.locationClass = pLoc->method->GetDeclaringClass();
   basket.thisPtr = thisPtr;
-  basket.threadId = Dbg::GetThreadSelfId();
-  basket.className = Dbg::GetClassName(pLoc->class_id);
+  basket.thread = Thread::Current();
+  basket.className = Dbg::GetClassName(basket.locationClass);
 
   /*
    * On rare occasions we may need to execute interpreted code in the VM
@@ -824,7 +838,7 @@
    * while doing so.  (I don't think we currently do this at all, so
    * this is mostly paranoia.)
    */
-  if (basket.threadId == debug_thread_id_) {
+  if (basket.thread == GetDebugThread()) {
     VLOG(jdwp) << "Ignoring location event in JDWP thread";
     return false;
   }
@@ -846,29 +860,36 @@
   size_t match_count = 0;
   ExpandBuf* pReq = NULL;
   JdwpSuspendPolicy suspend_policy = SP_NONE;
+  JdwpEvent** match_list = nullptr;
+  ObjectId thread_id = 0;
   {
-    MutexLock mu(Thread::Current(), event_list_lock_);
-    JdwpEvent** match_list = AllocMatchList(event_list_size_);
-    if ((eventFlags & Dbg::kBreakpoint) != 0) {
-      FindMatchingEvents(EK_BREAKPOINT, basket, match_list, &match_count);
-    }
-    if ((eventFlags & Dbg::kSingleStep) != 0) {
-      FindMatchingEvents(EK_SINGLE_STEP, basket, match_list, &match_count);
-    }
-    if ((eventFlags & Dbg::kMethodEntry) != 0) {
-      FindMatchingEvents(EK_METHOD_ENTRY, basket, match_list, &match_count);
-    }
-    if ((eventFlags & Dbg::kMethodExit) != 0) {
-      FindMatchingEvents(EK_METHOD_EXIT, basket, match_list, &match_count);
-      FindMatchingEvents(EK_METHOD_EXIT_WITH_RETURN_VALUE, basket, match_list, &match_count);
+    {
+      MutexLock mu(Thread::Current(), event_list_lock_);
+      match_list = AllocMatchList(event_list_size_);
+      if ((eventFlags & Dbg::kBreakpoint) != 0) {
+        FindMatchingEvents(EK_BREAKPOINT, basket, match_list, &match_count);
+      }
+      if ((eventFlags & Dbg::kSingleStep) != 0) {
+        FindMatchingEvents(EK_SINGLE_STEP, basket, match_list, &match_count);
+      }
+      if ((eventFlags & Dbg::kMethodEntry) != 0) {
+        FindMatchingEvents(EK_METHOD_ENTRY, basket, match_list, &match_count);
+      }
+      if ((eventFlags & Dbg::kMethodExit) != 0) {
+        FindMatchingEvents(EK_METHOD_EXIT, basket, match_list, &match_count);
+        FindMatchingEvents(EK_METHOD_EXIT_WITH_RETURN_VALUE, basket, match_list, &match_count);
+      }
     }
     if (match_count != 0) {
       suspend_policy = scanSuspendPolicy(match_list, match_count);
 
+      thread_id = Dbg::GetThreadId(basket.thread);
+      JDWP::JdwpLocation jdwp_location;
+      SetJdwpLocationFromEventLocation(pLoc, &jdwp_location);
+
       if (VLOG_IS_ON(jdwp)) {
-        LogMatchingEventsAndThread(match_list, match_count, basket);
-        VLOG(jdwp) << "  location=" << *pLoc;
-        VLOG(jdwp) << StringPrintf("  this=%#" PRIx64, basket.thisPtr);
+        LogMatchingEventsAndThread(match_list, match_count, thread_id);
+        VLOG(jdwp) << "  location=" << jdwp_location;
         VLOG(jdwp) << "  suspend_policy=" << suspend_policy;
       }
 
@@ -879,79 +900,81 @@
       for (size_t i = 0; i < match_count; i++) {
         expandBufAdd1(pReq, match_list[i]->eventKind);
         expandBufAdd4BE(pReq, match_list[i]->requestId);
-        expandBufAdd8BE(pReq, basket.threadId);
-        expandBufAddLocation(pReq, *pLoc);
+        expandBufAdd8BE(pReq, thread_id);
+        expandBufAddLocation(pReq, jdwp_location);
         if (match_list[i]->eventKind == EK_METHOD_EXIT_WITH_RETURN_VALUE) {
-          Dbg::OutputMethodReturnValue(pLoc->method_id, returnValue, pReq);
+          Dbg::OutputMethodReturnValue(jdwp_location.method_id, returnValue, pReq);
         }
       }
     }
 
-    CleanupMatchList(match_list, match_count);
+    {
+      MutexLock mu(Thread::Current(), event_list_lock_);
+      CleanupMatchList(match_list, match_count);
+    }
   }
 
   Dbg::ManageDeoptimization();
 
-  SendRequestAndPossiblySuspend(pReq, suspend_policy, basket.threadId);
+  SendRequestAndPossiblySuspend(pReq, suspend_policy, thread_id);
   return match_count != 0;
 }
 
-bool JdwpState::PostFieldEvent(const JdwpLocation* pLoc, RefTypeId typeId, FieldId fieldId,
-                               ObjectId thisPtr, const JValue* fieldValue, bool is_modification) {
+bool JdwpState::PostFieldEvent(const EventLocation* pLoc, mirror::ArtField* field,
+                               mirror::Object* this_object, const JValue* fieldValue,
+                               bool is_modification) {
+  DCHECK(pLoc != nullptr);
+  DCHECK(field != nullptr);
+  DCHECK_EQ(fieldValue != nullptr, is_modification);
+  DCHECK_EQ(field->IsStatic(), this_object == nullptr);
+
   ModBasket basket;
   basket.pLoc = pLoc;
-  basket.classId = pLoc->class_id;
-  basket.thisPtr = thisPtr;
-  basket.threadId = Dbg::GetThreadSelfId();
-  basket.className = Dbg::GetClassName(pLoc->class_id);
-  basket.fieldTypeID = typeId;
-  basket.fieldId = fieldId;
-
-  DCHECK_EQ(fieldValue != nullptr, is_modification);
+  basket.locationClass = pLoc->method->GetDeclaringClass();
+  basket.thisPtr = this_object;
+  basket.thread = Thread::Current();
+  basket.className = Dbg::GetClassName(basket.locationClass);
+  basket.field = field;
 
   if (InvokeInProgress()) {
     VLOG(jdwp) << "Not posting field event during invoke";
     return false;
   }
 
-  // Get field's reference type tag.
-  JDWP::JdwpTypeTag type_tag;
-  uint32_t class_status;  // unused here.
-  JdwpError error = Dbg::GetClassInfo(typeId, &type_tag, &class_status, NULL);
-  if (error != ERR_NONE) {
-    return false;
-  }
-
-  // Get instance type tag.
-  uint8_t tag;
-  error = Dbg::GetObjectTag(thisPtr, &tag);
-  if (error != ERR_NONE) {
-    return false;
-  }
-
   size_t match_count = 0;
   ExpandBuf* pReq = NULL;
   JdwpSuspendPolicy suspend_policy = SP_NONE;
+  JdwpEvent** match_list = nullptr;
+  ObjectId thread_id = 0;
   {
-    MutexLock mu(Thread::Current(), event_list_lock_);
-    JdwpEvent** match_list = AllocMatchList(event_list_size_);
-
-    if (is_modification) {
-      FindMatchingEvents(EK_FIELD_MODIFICATION, basket, match_list, &match_count);
-    } else {
-      FindMatchingEvents(EK_FIELD_ACCESS, basket, match_list, &match_count);
+    {
+      MutexLock mu(Thread::Current(), event_list_lock_);
+      match_list = AllocMatchList(event_list_size_);
+      if (is_modification) {
+        FindMatchingEvents(EK_FIELD_MODIFICATION, basket, match_list, &match_count);
+      } else {
+        FindMatchingEvents(EK_FIELD_ACCESS, basket, match_list, &match_count);
+      }
     }
     if (match_count != 0) {
       suspend_policy = scanSuspendPolicy(match_list, match_count);
 
+      thread_id = Dbg::GetThreadId(basket.thread);
+      ObjectRegistry* registry = Dbg::GetObjectRegistry();
+      ObjectId instance_id = registry->Add(basket.thisPtr);
+      RefTypeId field_type_id = registry->AddRefType(field->GetDeclaringClass());
+      FieldId field_id = Dbg::ToFieldId(field);
+      JDWP::JdwpLocation jdwp_location;
+      SetJdwpLocationFromEventLocation(pLoc, &jdwp_location);
+
       if (VLOG_IS_ON(jdwp)) {
-        LogMatchingEventsAndThread(match_list, match_count, basket);
-        VLOG(jdwp) << "  location=" << *pLoc;
-        VLOG(jdwp) << StringPrintf("  this=%#" PRIx64, basket.thisPtr);
-        VLOG(jdwp) << StringPrintf("  type=%#" PRIx64, basket.fieldTypeID) << " "
-                   << Dbg::GetClassName(basket.fieldTypeID);
-        VLOG(jdwp) << StringPrintf("  field=%#" PRIx32, basket.fieldId) << " "
-                   << Dbg::GetFieldName(basket.fieldId);
+        LogMatchingEventsAndThread(match_list, match_count, thread_id);
+        VLOG(jdwp) << "  location=" << jdwp_location;
+        VLOG(jdwp) << StringPrintf("  this=%#" PRIx64, instance_id);
+        VLOG(jdwp) << StringPrintf("  type=%#" PRIx64, field_type_id) << " "
+                   << Dbg::GetClassName(field_id);
+        VLOG(jdwp) << StringPrintf("  field=%#" PRIx32, field_id) << " "
+                   << Dbg::GetFieldName(field_id);
         VLOG(jdwp) << "  suspend_policy=" << suspend_policy;
       }
 
@@ -959,28 +982,41 @@
       expandBufAdd1(pReq, suspend_policy);
       expandBufAdd4BE(pReq, match_count);
 
+      // Get field's reference type tag.
+      JDWP::JdwpTypeTag type_tag = Dbg::GetTypeTag(field->GetDeclaringClass());
+
+      // Get instance type tag.
+      uint8_t tag;
+      {
+        ScopedObjectAccessUnchecked soa(Thread::Current());
+        tag = Dbg::TagFromObject(soa, basket.thisPtr);
+      }
+
       for (size_t i = 0; i < match_count; i++) {
         expandBufAdd1(pReq, match_list[i]->eventKind);
         expandBufAdd4BE(pReq, match_list[i]->requestId);
-        expandBufAdd8BE(pReq, basket.threadId);
-        expandBufAddLocation(pReq, *pLoc);
+        expandBufAdd8BE(pReq, thread_id);
+        expandBufAddLocation(pReq, jdwp_location);
         expandBufAdd1(pReq, type_tag);
-        expandBufAddRefTypeId(pReq, typeId);
-        expandBufAddFieldId(pReq, fieldId);
+        expandBufAddRefTypeId(pReq, field_type_id);
+        expandBufAddFieldId(pReq, field_id);
         expandBufAdd1(pReq, tag);
-        expandBufAddObjectId(pReq, thisPtr);
+        expandBufAddObjectId(pReq, instance_id);
         if (is_modification) {
-          Dbg::OutputFieldValue(fieldId, fieldValue, pReq);
+          Dbg::OutputFieldValue(field_id, fieldValue, pReq);
         }
       }
     }
 
-    CleanupMatchList(match_list, match_count);
+    {
+      MutexLock mu(Thread::Current(), event_list_lock_);
+      CleanupMatchList(match_list, match_count);
+    }
   }
 
   Dbg::ManageDeoptimization();
 
-  SendRequestAndPossiblySuspend(pReq, suspend_policy, basket.threadId);
+  SendRequestAndPossiblySuspend(pReq, suspend_policy, thread_id);
   return match_count != 0;
 }
 
@@ -990,8 +1026,8 @@
  * Valid mods:
  *  Count, ThreadOnly
  */
-bool JdwpState::PostThreadChange(ObjectId threadId, bool start) {
-  CHECK_EQ(threadId, Dbg::GetThreadSelfId());
+bool JdwpState::PostThreadChange(Thread* thread, bool start) {
+  CHECK_EQ(thread, Thread::Current());
 
   /*
    * I don't think this can happen.
@@ -1002,27 +1038,32 @@
   }
 
   ModBasket basket;
-  basket.threadId = threadId;
+  basket.thread = thread;
 
   ExpandBuf* pReq = NULL;
   JdwpSuspendPolicy suspend_policy = SP_NONE;
+  JdwpEvent** match_list = nullptr;
   size_t match_count = 0;
+  ObjectId thread_id = 0;
   {
-    // Don't allow the list to be updated while we scan it.
-    MutexLock mu(Thread::Current(), event_list_lock_);
-    JdwpEvent** match_list = AllocMatchList(event_list_size_);
-
-    if (start) {
-      FindMatchingEvents(EK_THREAD_START, basket, match_list, &match_count);
-    } else {
-      FindMatchingEvents(EK_THREAD_DEATH, basket, match_list, &match_count);
+    {
+      // Don't allow the list to be updated while we scan it.
+      MutexLock mu(Thread::Current(), event_list_lock_);
+      match_list = AllocMatchList(event_list_size_);
+      if (start) {
+        FindMatchingEvents(EK_THREAD_START, basket, match_list, &match_count);
+      } else {
+        FindMatchingEvents(EK_THREAD_DEATH, basket, match_list, &match_count);
+      }
     }
 
     if (match_count != 0) {
       suspend_policy = scanSuspendPolicy(match_list, match_count);
 
+      thread_id = Dbg::GetThreadId(basket.thread);
+
       if (VLOG_IS_ON(jdwp)) {
-        LogMatchingEventsAndThread(match_list, match_count, basket);
+        LogMatchingEventsAndThread(match_list, match_count, thread_id);
         VLOG(jdwp) << "  suspend_policy=" << suspend_policy;
       }
 
@@ -1033,16 +1074,19 @@
       for (size_t i = 0; i < match_count; i++) {
         expandBufAdd1(pReq, match_list[i]->eventKind);
         expandBufAdd4BE(pReq, match_list[i]->requestId);
-        expandBufAdd8BE(pReq, basket.threadId);
+        expandBufAdd8BE(pReq, thread_id);
       }
     }
 
-    CleanupMatchList(match_list, match_count);
+    {
+      MutexLock mu(Thread::Current(), event_list_lock_);
+      CleanupMatchList(match_list, match_count);
+    }
   }
 
   Dbg::ManageDeoptimization();
 
-  SendRequestAndPossiblySuspend(pReq, suspend_policy, basket.threadId);
+  SendRequestAndPossiblySuspend(pReq, suspend_policy, thread_id);
 
   return match_count != 0;
 }
@@ -1076,17 +1120,21 @@
  * because there's a pretty good chance that we're not going to send it
  * up the debugger.
  */
-bool JdwpState::PostException(const JdwpLocation* pThrowLoc,
-                              ObjectId exceptionId, RefTypeId exceptionClassId,
-                              const JdwpLocation* pCatchLoc, ObjectId thisPtr) {
-  ModBasket basket;
+bool JdwpState::PostException(const EventLocation* pThrowLoc, mirror::Throwable* exception_object,
+                              const EventLocation* pCatchLoc, mirror::Object* thisPtr) {
+  DCHECK(exception_object != nullptr);
+  DCHECK(pThrowLoc != nullptr);
+  DCHECK(pCatchLoc != nullptr);
+  DCHECK(pThrowLoc->method != nullptr);
+  DCHECK_EQ(pThrowLoc->method->IsStatic(), thisPtr == nullptr);
 
+  ModBasket basket;
   basket.pLoc = pThrowLoc;
-  basket.classId = pThrowLoc->class_id;
-  basket.threadId = Dbg::GetThreadSelfId();
-  basket.className = Dbg::GetClassName(basket.classId);
-  basket.excepClassId = exceptionClassId;
-  basket.caught = (pCatchLoc->class_id != 0);
+  basket.locationClass = pThrowLoc->method->GetDeclaringClass();
+  basket.thread = Thread::Current();
+  basket.className = Dbg::GetClassName(basket.locationClass);
+  basket.exceptionClass = exception_object->GetClass();
+  basket.caught = (pCatchLoc->method != 0);
   basket.thisPtr = thisPtr;
 
   /* don't try to post an exception caused by the debugger */
@@ -1098,24 +1146,37 @@
   size_t match_count = 0;
   ExpandBuf* pReq = NULL;
   JdwpSuspendPolicy suspend_policy = SP_NONE;
+  JdwpEvent** match_list = nullptr;
+  ObjectId thread_id = 0;
   {
-    MutexLock mu(Thread::Current(), event_list_lock_);
-    JdwpEvent** match_list = AllocMatchList(event_list_size_);
-    FindMatchingEvents(EK_EXCEPTION, basket, match_list, &match_count);
+    {
+      MutexLock mu(Thread::Current(), event_list_lock_);
+      match_list = AllocMatchList(event_list_size_);
+      FindMatchingEvents(EK_EXCEPTION, basket, match_list, &match_count);
+    }
     if (match_count != 0) {
       suspend_policy = scanSuspendPolicy(match_list, match_count);
 
+      thread_id = Dbg::GetThreadId(basket.thread);
+      ObjectRegistry* registry = Dbg::GetObjectRegistry();
+      ObjectId exceptionId = registry->Add(exception_object);
+      JDWP::JdwpLocation jdwp_throw_location;
+      JDWP::JdwpLocation jdwp_catch_location;
+      SetJdwpLocationFromEventLocation(pThrowLoc, &jdwp_throw_location);
+      SetJdwpLocationFromEventLocation(pCatchLoc, &jdwp_catch_location);
+
       if (VLOG_IS_ON(jdwp)) {
-        LogMatchingEventsAndThread(match_list, match_count, basket);
-        VLOG(jdwp) << "  throwLocation=" << *pThrowLoc;
-        if (pCatchLoc->class_id == 0) {
+        std::string exceptionClassName(PrettyDescriptor(exception_object->GetClass()));
+
+        LogMatchingEventsAndThread(match_list, match_count, thread_id);
+        VLOG(jdwp) << "  throwLocation=" << jdwp_throw_location;
+        if (jdwp_catch_location.class_id == 0) {
           VLOG(jdwp) << "  catchLocation=uncaught";
         } else {
-          VLOG(jdwp) << "  catchLocation=" << *pCatchLoc;
+          VLOG(jdwp) << "  catchLocation=" << jdwp_catch_location;
         }
-        VLOG(jdwp) << StringPrintf("  this=%#" PRIx64, basket.thisPtr);
-        VLOG(jdwp) << StringPrintf("  exceptionClass=%#" PRIx64, basket.excepClassId) << " "
-                   << Dbg::GetClassName(basket.excepClassId);
+        VLOG(jdwp) << StringPrintf("  exception=%#" PRIx64, exceptionId) << " "
+                   << exceptionClassName;
         VLOG(jdwp) << "  suspend_policy=" << suspend_policy;
       }
 
@@ -1126,21 +1187,23 @@
       for (size_t i = 0; i < match_count; i++) {
         expandBufAdd1(pReq, match_list[i]->eventKind);
         expandBufAdd4BE(pReq, match_list[i]->requestId);
-        expandBufAdd8BE(pReq, basket.threadId);
-
-        expandBufAddLocation(pReq, *pThrowLoc);
+        expandBufAdd8BE(pReq, thread_id);
+        expandBufAddLocation(pReq, jdwp_throw_location);
         expandBufAdd1(pReq, JT_OBJECT);
         expandBufAdd8BE(pReq, exceptionId);
-        expandBufAddLocation(pReq, *pCatchLoc);
+        expandBufAddLocation(pReq, jdwp_catch_location);
       }
     }
 
-    CleanupMatchList(match_list, match_count);
+    {
+      MutexLock mu(Thread::Current(), event_list_lock_);
+      CleanupMatchList(match_list, match_count);
+    }
   }
 
   Dbg::ManageDeoptimization();
 
-  SendRequestAndPossiblySuspend(pReq, suspend_policy, basket.threadId);
+  SendRequestAndPossiblySuspend(pReq, suspend_policy, thread_id);
 
   return match_count != 0;
 }
@@ -1151,13 +1214,13 @@
  * Valid mods:
  *  Count, ThreadOnly, ClassOnly, ClassMatch, ClassExclude
  */
-bool JdwpState::PostClassPrepare(JdwpTypeTag tag, RefTypeId refTypeId, const std::string& signature,
-                                 int status) {
-  ModBasket basket;
+bool JdwpState::PostClassPrepare(mirror::Class* klass) {
+  DCHECK(klass != nullptr);
 
-  basket.classId = refTypeId;
-  basket.threadId = Dbg::GetThreadSelfId();
-  basket.className = Dbg::GetClassName(basket.classId);
+  ModBasket basket;
+  basket.locationClass = klass;
+  basket.thread = Thread::Current();
+  basket.className = Dbg::GetClassName(basket.locationClass);
 
   /* suppress class prep caused by debugger */
   if (InvokeInProgress()) {
@@ -1167,28 +1230,44 @@
 
   ExpandBuf* pReq = NULL;
   JdwpSuspendPolicy suspend_policy = SP_NONE;
+  JdwpEvent** match_list = nullptr;
   size_t match_count = 0;
+  ObjectId thread_id = 0;
   {
-    MutexLock mu(Thread::Current(), event_list_lock_);
-    JdwpEvent** match_list = AllocMatchList(event_list_size_);
-    FindMatchingEvents(EK_CLASS_PREPARE, basket, match_list, &match_count);
+    {
+      MutexLock mu(Thread::Current(), event_list_lock_);
+      match_list = AllocMatchList(event_list_size_);
+      FindMatchingEvents(EK_CLASS_PREPARE, basket, match_list, &match_count);
+    }
     if (match_count != 0) {
       suspend_policy = scanSuspendPolicy(match_list, match_count);
 
+      thread_id = Dbg::GetThreadId(basket.thread);
+      ObjectRegistry* registry = Dbg::GetObjectRegistry();
+      RefTypeId class_id = registry->AddRefType(basket.locationClass);
+
+      // OLD-TODO - we currently always send both "verified" and "prepared" since
+      // debuggers seem to like that.  There might be some advantage to honesty,
+      // since the class may not yet be verified.
+      int status = JDWP::CS_VERIFIED | JDWP::CS_PREPARED;
+      JDWP::JdwpTypeTag tag = Dbg::GetTypeTag(basket.locationClass);
+      std::string temp;
+      std::string signature(basket.locationClass->GetDescriptor(&temp));
+
       if (VLOG_IS_ON(jdwp)) {
-        LogMatchingEventsAndThread(match_list, match_count, basket);
-        VLOG(jdwp) << StringPrintf("  type=%#" PRIx64, basket.classId)<< " " << signature;
+        LogMatchingEventsAndThread(match_list, match_count, thread_id);
+        VLOG(jdwp) << StringPrintf("  type=%#" PRIx64, class_id) << " " << signature;
         VLOG(jdwp) << "  suspend_policy=" << suspend_policy;
       }
 
-      if (basket.threadId == debug_thread_id_) {
+      if (thread_id == debug_thread_id_) {
         /*
          * JDWP says that, for a class prep in the debugger thread, we
-         * should set threadId to null and if any threads were supposed
+         * should set thread to null and if any threads were supposed
          * to be suspended then we suspend all other threads.
          */
         VLOG(jdwp) << "  NOTE: class prepare in debugger thread!";
-        basket.threadId = 0;
+        thread_id = 0;
         if (suspend_policy == SP_EVENT_THREAD) {
           suspend_policy = SP_ALL;
         }
@@ -1201,20 +1280,23 @@
       for (size_t i = 0; i < match_count; i++) {
         expandBufAdd1(pReq, match_list[i]->eventKind);
         expandBufAdd4BE(pReq, match_list[i]->requestId);
-        expandBufAdd8BE(pReq, basket.threadId);
-
+        expandBufAdd8BE(pReq, thread_id);
         expandBufAdd1(pReq, tag);
-        expandBufAdd8BE(pReq, refTypeId);
+        expandBufAdd8BE(pReq, class_id);
         expandBufAddUtf8String(pReq, signature);
         expandBufAdd4BE(pReq, status);
       }
     }
-    CleanupMatchList(match_list, match_count);
+
+    {
+      MutexLock mu(Thread::Current(), event_list_lock_);
+      CleanupMatchList(match_list, match_count);
+    }
   }
 
   Dbg::ManageDeoptimization();
 
-  SendRequestAndPossiblySuspend(pReq, suspend_policy, basket.threadId);
+  SendRequestAndPossiblySuspend(pReq, suspend_policy, thread_id);
 
   return match_count != 0;
 }
diff --git a/runtime/jdwp/jdwp_handler.cc b/runtime/jdwp/jdwp_handler.cc
index 8560cb5..e0a83f6 100644
--- a/runtime/jdwp/jdwp_handler.cc
+++ b/runtime/jdwp/jdwp_handler.cc
@@ -151,7 +151,12 @@
     /* show detailed debug output */
     if (resultTag == JT_STRING && exceptObjId == 0) {
       if (resultValue != 0) {
-        VLOG(jdwp) << "      string '" << Dbg::StringToUtf8(resultValue) << "'";
+        if (VLOG_IS_ON(jdwp)) {
+          std::string result_string;
+          JDWP::JdwpError error = Dbg::StringToUtf8(resultValue, &result_string);
+          CHECK_EQ(error, JDWP::ERR_NONE);
+          VLOG(jdwp) << "      string '" << result_string << "'";
+        }
       } else {
         VLOG(jdwp) << "      string (null)";
       }
@@ -919,7 +924,11 @@
 static JdwpError SR_Value(JdwpState*, Request* request, ExpandBuf* pReply)
     SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
   ObjectId stringObject = request->ReadObjectId();
-  std::string str(Dbg::StringToUtf8(stringObject));
+  std::string str;
+  JDWP::JdwpError error = Dbg::StringToUtf8(stringObject, &str);
+  if (error != JDWP::ERR_NONE) {
+    return error;
+  }
 
   VLOG(jdwp) << StringPrintf("    --> %s", PrintableString(str.c_str()).c_str());
 
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/native/dalvik_system_VMDebug.cc b/runtime/native/dalvik_system_VMDebug.cc
index ceff206..d8a537f 100644
--- a/runtime/native/dalvik_system_VMDebug.cc
+++ b/runtime/native/dalvik_system_VMDebug.cc
@@ -60,11 +60,11 @@
 }
 
 static void VMDebug_startAllocCounting(JNIEnv*, jclass) {
-  Runtime::Current()->SetStatsEnabled(true);
+  Runtime::Current()->SetStatsEnabled(true, false);
 }
 
 static void VMDebug_stopAllocCounting(JNIEnv*, jclass) {
-  Runtime::Current()->SetStatsEnabled(false);
+  Runtime::Current()->SetStatsEnabled(false, false);
 }
 
 static jint VMDebug_getAllocCount(JNIEnv*, jclass, jint kind) {
diff --git a/runtime/parsed_options.cc b/runtime/parsed_options.cc
index 6b4f764..2bd994d 100644
--- a/runtime/parsed_options.cc
+++ b/runtime/parsed_options.cc
@@ -80,7 +80,7 @@
     gc::kCollectorTypeCMS),
 #error "ART default GC type must be set"
 #endif
-    background_collector_type_(gc::kCollectorTypeHomogeneousSpaceCompact),
+    background_collector_type_(gc::kCollectorTypeNone),
                                                     // If background_collector_type_ is
                                                     // kCollectorTypeNone, it defaults to the
                                                     // collector_type_ after parsing options. If
@@ -696,6 +696,12 @@
       return false;
     }
   }
+  // If not set, background collector type defaults to homogeneous compaction
+  // if not low memory mode, semispace otherwise.
+  if (background_collector_type_ == gc::kCollectorTypeNone) {
+    background_collector_type_ = low_memory_mode_ ?
+        gc::kCollectorTypeSS : gc::kCollectorTypeHomogeneousSpaceCompact;
+  }
 
   // If a reference to the dalvik core.jar snuck in, replace it with
   // the art specific version. This can happen with on device
diff --git a/runtime/runtime.cc b/runtime/runtime.cc
index 9b24bec..8386cc0 100644
--- a/runtime/runtime.cc
+++ b/runtime/runtime.cc
@@ -72,6 +72,7 @@
 #include "reflection.h"
 #include "ScopedLocalRef.h"
 #include "scoped_thread_state_change.h"
+#include "sigchain.h"
 #include "signal_catcher.h"
 #include "signal_set.h"
 #include "handle_scope-inl.h"
@@ -563,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;
@@ -736,6 +739,11 @@
       break;
   }
 
+  // Always initialize the signal chain so that any calls to sigaction get
+  // correctly routed to the next in the chain regardless of whether we
+  // have claimed the signal or not.
+  InitializeSignalChain();
+
   if (implicit_null_checks_ || implicit_so_checks_ || implicit_suspend_checks_) {
     fault_manager.Init();
 
@@ -998,14 +1006,14 @@
   }
 }
 
-void Runtime::SetStatsEnabled(bool new_state) {
+void Runtime::SetStatsEnabled(bool new_state, bool suspended) {
   if (new_state == true) {
     GetStats()->Clear(~0);
     // TODO: wouldn't it make more sense to clear _all_ threads' stats?
     Thread::Current()->GetStats()->Clear(~0);
-    GetInstrumentation()->InstrumentQuickAllocEntryPoints();
+    GetInstrumentation()->InstrumentQuickAllocEntryPoints(suspended);
   } else {
-    GetInstrumentation()->UninstrumentQuickAllocEntryPoints();
+    GetInstrumentation()->UninstrumentQuickAllocEntryPoints(suspended);
   }
   stats_enabled_ = new_state;
 }
diff --git a/runtime/runtime.h b/runtime/runtime.h
index cfb1abc..f9c017b 100644
--- a/runtime/runtime.h
+++ b/runtime/runtime.h
@@ -390,7 +390,7 @@
 
   void ResetStats(int kinds);
 
-  void SetStatsEnabled(bool new_state);
+  void SetStatsEnabled(bool new_state, bool suspended);
 
   enum class NativeBridgeAction {  // private
     kUnload,
diff --git a/runtime/thread.cc b/runtime/thread.cc
index c54bebe..650b0f9 100644
--- a/runtime/thread.cc
+++ b/runtime/thread.cc
@@ -961,7 +961,7 @@
     // If we're currently in native code, dump that stack before dumping the managed stack.
     if (dump_for_abort || ShouldShowNativeStack(this)) {
       DumpKernelStack(os, GetTid(), "  kernel: ", false);
-      DumpNativeStack(os, GetTid(), "  native: ", GetCurrentMethod(nullptr));
+      DumpNativeStack(os, GetTid(), "  native: ", GetCurrentMethod(nullptr, !dump_for_abort));
     }
     DumpJavaStack(os);
   } else {
diff --git a/runtime/thread_list.cc b/runtime/thread_list.cc
index 2dbfb3e..ec5b775 100644
--- a/runtime/thread_list.cc
+++ b/runtime/thread_list.cc
@@ -728,11 +728,14 @@
       Thread::resume_cond_->Wait(self);
       if (self->GetSuspendCount() != 0) {
         // The condition was signaled but we're still suspended. This
-        // can happen if the debugger lets go while a SIGQUIT thread
+        // can happen when we suspend then resume all threads to
+        // update instrumentation or compute monitor info. This can
+        // also happen if the debugger lets go while a SIGQUIT thread
         // dump event is pending (assuming SignalCatcher was resumed for
         // just long enough to try to grab the thread-suspend lock).
-        LOG(WARNING) << *self << " still suspended after undo "
-                   << "(suspend count=" << self->GetSuspendCount() << ")";
+        VLOG(jdwp) << *self << " still suspended after undo "
+                   << "(suspend count=" << self->GetSuspendCount() << ", "
+                   << "debug suspend count=" << self->GetDebugSuspendCount() << ")";
       }
     }
     CHECK_EQ(self->GetSuspendCount(), 0);
@@ -872,14 +875,21 @@
     // thread_suspend_count_lock_ so that the unregistering thread cannot be suspended.
     // Note: deliberately not using MutexLock that could hold a stale self pointer.
     Locks::thread_list_lock_->ExclusiveLock(self);
-    CHECK(Contains(self));
-    Locks::thread_suspend_count_lock_->ExclusiveLock(self);
-    bool removed = false;
-    if (!self->IsSuspended()) {
-      list_.remove(self);
-      removed = true;
+    bool removed = true;
+    if (!Contains(self)) {
+      std::ostringstream os;
+      DumpNativeStack(os, GetTid(), "  native: ", nullptr);
+      LOG(ERROR) << "Request to unregister unattached thread\n" << os.str();
+    } else {
+      Locks::thread_suspend_count_lock_->ExclusiveLock(self);
+      if (!self->IsSuspended()) {
+        list_.remove(self);
+      } else {
+        // We failed to remove the thread due to a suspend request, loop and try again.
+        removed = false;
+      }
+      Locks::thread_suspend_count_lock_->ExclusiveUnlock(self);
     }
-    Locks::thread_suspend_count_lock_->ExclusiveUnlock(self);
     Locks::thread_list_lock_->ExclusiveUnlock(self);
     if (removed) {
       delete self;
diff --git a/runtime/trace.cc b/runtime/trace.cc
index 6dcc5fe..b32e042 100644
--- a/runtime/trace.cc
+++ b/runtime/trace.cc
@@ -373,11 +373,9 @@
 
       // Enable count of allocs if specified in the flags.
       if ((flags && kTraceCountAllocs) != 0) {
-        runtime->SetStatsEnabled(true);
+        runtime->SetStatsEnabled(true, true);
       }
 
-
-
       if (sampling_enabled) {
         CHECK_PTHREAD_CALL(pthread_create, (&sampling_pthread_, NULL, &RunSamplingThread,
                                             reinterpret_cast<void*>(interval_us)),
@@ -492,7 +490,7 @@
   size_t final_offset = cur_offset_.LoadRelaxed();
 
   if ((flags_ & kTraceCountAllocs) != 0) {
-    Runtime::Current()->SetStatsEnabled(false);
+    Runtime::Current()->SetStatsEnabled(false, true);
   }
 
   std::set<mirror::ArtMethod*> visited_methods;
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.
diff --git a/runtime/verifier/reg_type_cache.h b/runtime/verifier/reg_type_cache.h
index 29933cf..ff7b1f3 100644
--- a/runtime/verifier/reg_type_cache.h
+++ b/runtime/verifier/reg_type_cache.h
@@ -80,34 +80,34 @@
   const BooleanType& Boolean() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
     return *BooleanType::GetInstance();
   }
-  const RegType& Byte() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+  const ByteType& Byte() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
     return *ByteType::GetInstance();
   }
-  const RegType& Char() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+  const CharType& Char() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
     return *CharType::GetInstance();
   }
-  const RegType& Short() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+  const ShortType& Short() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
     return *ShortType::GetInstance();
   }
-  const RegType& Integer() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+  const IntegerType& Integer() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
     return *IntegerType::GetInstance();
   }
-  const RegType& Float() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+  const FloatType& Float() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
     return *FloatType::GetInstance();
   }
-  const RegType& LongLo() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+  const LongLoType& LongLo() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
     return *LongLoType::GetInstance();
   }
-  const RegType& LongHi() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+  const LongHiType& LongHi() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
     return *LongHiType::GetInstance();
   }
-  const RegType& DoubleLo() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+  const DoubleLoType& DoubleLo() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
     return *DoubleLoType::GetInstance();
   }
-  const RegType& DoubleHi() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+  const DoubleHiType& DoubleHi() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
     return *DoubleHiType::GetInstance();
   }
-  const RegType& Undefined() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+  const UndefinedType& Undefined() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
     return *UndefinedType::GetInstance();
   }
   const ConflictType& Conflict() {
diff --git a/sigchainlib/sigchain.cc b/sigchainlib/sigchain.cc
index 7539990..74bfb7e 100644
--- a/sigchainlib/sigchain.cc
+++ b/sigchainlib/sigchain.cc
@@ -26,6 +26,8 @@
 #include <stdio.h>
 #include <stdlib.h>
 
+#include "sigchain.h"
+
 #if defined(__APPLE__)
 #define _NSIG NSIG
 #define sighandler_t sig_t
@@ -81,6 +83,9 @@
 
 // User's signal handlers
 static SignalAction user_sigactions[_NSIG];
+static bool initialized;
+static void* linked_sigaction_sym;
+static void* linked_sigprocmask_sym;
 
 static void log(const char* format, ...) {
   char buf[256];
@@ -102,6 +107,7 @@
   }
 }
 
+
 // Claim a signal chain for a particular signal.
 void ClaimSignalChain(int signal, struct sigaction* oldaction) {
   CheckSignalValid(signal);
@@ -163,14 +169,17 @@
   // Will only get here if the signal chain has not been claimed.  We want
   // to pass the sigaction on to the kernel via the real sigaction in libc.
 
-  void* linked_sigaction_sym = dlsym(RTLD_NEXT, "sigaction");
   if (linked_sigaction_sym == nullptr) {
-    linked_sigaction_sym = dlsym(RTLD_DEFAULT, "sigaction");
-    if (linked_sigaction_sym == nullptr ||
-        linked_sigaction_sym == reinterpret_cast<void*>(sigaction)) {
-      log("Unable to find next sigaction in signal chain");
-      abort();
-    }
+    // Perform lazy initialization.
+    // This will only occur outside of a signal context since we have
+    // not been initialized and therefore cannot be within the ART
+    // runtime.
+    InitializeSignalChain();
+  }
+
+  if (linked_sigaction_sym == nullptr) {
+    log("Unable to find next sigaction in signal chain");
+    abort();
   }
 
   typedef int (*SigAction)(int, const struct sigaction*, struct sigaction*);
@@ -198,14 +207,14 @@
   // Will only get here if the signal chain has not been claimed.  We want
   // to pass the sigaction on to the kernel via the real sigaction in libc.
 
-  void* linked_sigaction_sym = dlsym(RTLD_NEXT, "sigaction");
   if (linked_sigaction_sym == nullptr) {
-    linked_sigaction_sym = dlsym(RTLD_DEFAULT, "sigaction");
-    if (linked_sigaction_sym == nullptr ||
-        linked_sigaction_sym == reinterpret_cast<void*>(sigaction)) {
-      log("Unable to find next sigaction in signal chain");
-      abort();
-    }
+    // Perform lazy initialization.
+    InitializeSignalChain();
+  }
+
+  if (linked_sigaction_sym == nullptr) {
+    log("Unable to find next sigaction in signal chain");
+    abort();
   }
 
   typedef int (*SigAction)(int, const struct sigaction*, struct sigaction*);
@@ -235,14 +244,14 @@
     new_set_ptr = &tmpset;
   }
 
-  void* linked_sigprocmask_sym = dlsym(RTLD_NEXT, "sigprocmask");
   if (linked_sigprocmask_sym == nullptr) {
-    linked_sigprocmask_sym = dlsym(RTLD_DEFAULT, "sigprocmask");
-    if (linked_sigprocmask_sym == nullptr ||
-        linked_sigprocmask_sym == reinterpret_cast<void*>(sigprocmask)) {
-      log("Unable to find next sigprocmask in signal chain");
-      abort();
-    }
+    // Perform lazy initialization.
+    InitializeSignalChain();
+  }
+
+  if (linked_sigprocmask_sym == nullptr) {
+    log("Unable to find next sigprocmask in signal chain");
+    abort();
   }
 
   typedef int (*SigProcMask)(int how, const sigset_t*, sigset_t*);
@@ -250,5 +259,36 @@
   return linked_sigprocmask(how, new_set_ptr, bionic_old_set);
 }
 }   // extern "C"
+
+void InitializeSignalChain() {
+  // Warning.
+  // Don't call this from within a signal context as it makes calls to
+  // dlsym.  Calling into the dynamic linker will result in locks being
+  // taken and if it so happens that a signal occurs while one of these
+  // locks is already taken, dlsym will block trying to reenter a
+  // mutex and we will never get out of it.
+  if (initialized) {
+    // Don't initialize twice.
+    return;
+  }
+  linked_sigaction_sym = dlsym(RTLD_NEXT, "sigaction");
+  if (linked_sigaction_sym == nullptr) {
+    linked_sigaction_sym = dlsym(RTLD_DEFAULT, "sigaction");
+    if (linked_sigaction_sym == nullptr ||
+      linked_sigaction_sym == reinterpret_cast<void*>(sigaction)) {
+        linked_sigaction_sym = nullptr;
+    }
+  }
+
+  linked_sigprocmask_sym = dlsym(RTLD_NEXT, "sigprocmask");
+  if (linked_sigprocmask_sym == nullptr) {
+    linked_sigprocmask_sym = dlsym(RTLD_DEFAULT, "sigprocmask");
+    if (linked_sigprocmask_sym == nullptr ||
+        linked_sigprocmask_sym == reinterpret_cast<void*>(sigprocmask)) {
+         linked_sigprocmask_sym = nullptr;
+    }
+  }
+  initialized = true;
+}
 }   // namespace art
 
diff --git a/sigchainlib/sigchain.h b/sigchainlib/sigchain.h
index a4ce81c..5bc4026 100644
--- a/sigchainlib/sigchain.h
+++ b/sigchainlib/sigchain.h
@@ -21,6 +21,8 @@
 
 namespace art {
 
+void InitializeSignalChain();
+
 void ClaimSignalChain(int signal, struct sigaction* oldaction);
 
 void UnclaimSignalChain(int signal);