diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index 1691dbb..d59d8f6 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -86,6 +86,7 @@
 
 ART_GTEST_atomic_method_ref_map_test_DEX_DEPS := Interfaces
 ART_GTEST_class_linker_test_DEX_DEPS := Interfaces MethodTypes MultiDex MyClass Nested Statics StaticsFromCode
+ART_GTEST_class_table_test_DEX_DEPS := XandY
 ART_GTEST_compiler_driver_test_DEX_DEPS := AbstractMethod StaticLeafMethods ProfileTestMultiDex
 ART_GTEST_dex_cache_test_DEX_DEPS := Main Packages MethodTypes
 ART_GTEST_dex_file_test_DEX_DEPS := GetMethodSignature Main Nested
@@ -598,6 +599,7 @@
 ART_TEST_TARGET_VALGRIND_GTEST_RULES :=
 ART_GTEST_TARGET_ANDROID_ROOT :=
 ART_GTEST_class_linker_test_DEX_DEPS :=
+ART_GTEST_class_table_test_DEX_DEPS :=
 ART_GTEST_compiler_driver_test_DEX_DEPS :=
 ART_GTEST_dex_file_test_DEX_DEPS :=
 ART_GTEST_exception_test_DEX_DEPS :=
diff --git a/cmdline/cmdline_types.h b/cmdline/cmdline_types.h
index 156ca9e..e41d9bd 100644
--- a/cmdline/cmdline_types.h
+++ b/cmdline/cmdline_types.h
@@ -22,6 +22,8 @@
 #include "detail/cmdline_debug_detail.h"
 #include "cmdline_type_parser.h"
 
+#include "android-base/strings.h"
+
 // Includes for the types that are being specialized
 #include <string>
 #include "base/logging.h"
@@ -447,7 +449,7 @@
   }
 
   std::string Join() const {
-    return art::Join(list_, Separator);
+    return android::base::Join(list_, Separator);
   }
 
   static ParseStringList<Separator> Split(const std::string& str) {
@@ -709,43 +711,43 @@
     // The rest of these options are always the wildcard from '-Xps-*'
     std::string suffix = RemovePrefix(option);
 
-    if (StartsWith(option, "min-save-period-ms:")) {
+    if (android::base::StartsWith(option, "min-save-period-ms:")) {
       CmdlineType<unsigned int> type_parser;
       return ParseInto(existing,
              &ProfileSaverOptions::min_save_period_ms_,
              type_parser.Parse(suffix));
     }
-    if (StartsWith(option, "save-resolved-classes-delay-ms:")) {
+    if (android::base::StartsWith(option, "save-resolved-classes-delay-ms:")) {
       CmdlineType<unsigned int> type_parser;
       return ParseInto(existing,
              &ProfileSaverOptions::save_resolved_classes_delay_ms_,
              type_parser.Parse(suffix));
     }
-    if (StartsWith(option, "startup-method-samples:")) {
+    if (android::base::StartsWith(option, "startup-method-samples:")) {
       CmdlineType<unsigned int> type_parser;
       return ParseInto(existing,
              &ProfileSaverOptions::startup_method_samples_,
              type_parser.Parse(suffix));
     }
-    if (StartsWith(option, "min-methods-to-save:")) {
+    if (android::base::StartsWith(option, "min-methods-to-save:")) {
       CmdlineType<unsigned int> type_parser;
       return ParseInto(existing,
              &ProfileSaverOptions::min_methods_to_save_,
              type_parser.Parse(suffix));
     }
-    if (StartsWith(option, "min-classes-to-save:")) {
+    if (android::base::StartsWith(option, "min-classes-to-save:")) {
       CmdlineType<unsigned int> type_parser;
       return ParseInto(existing,
              &ProfileSaverOptions::min_classes_to_save_,
              type_parser.Parse(suffix));
     }
-    if (StartsWith(option, "min-notification-before-wake:")) {
+    if (android::base::StartsWith(option, "min-notification-before-wake:")) {
       CmdlineType<unsigned int> type_parser;
       return ParseInto(existing,
              &ProfileSaverOptions::min_notification_before_wake_,
              type_parser.Parse(suffix));
     }
-    if (StartsWith(option, "max-notification-before-wake:")) {
+    if (android::base::StartsWith(option, "max-notification-before-wake:")) {
       CmdlineType<unsigned int> type_parser;
       return ParseInto(existing,
              &ProfileSaverOptions::max_notification_before_wake_,
diff --git a/cmdline/detail/cmdline_parse_argument_detail.h b/cmdline/detail/cmdline_parse_argument_detail.h
index 14eac30..da03c21 100644
--- a/cmdline/detail/cmdline_parse_argument_detail.h
+++ b/cmdline/detail/cmdline_parse_argument_detail.h
@@ -25,6 +25,8 @@
 #include <numeric>
 #include <memory>
 
+#include "android-base/strings.h"
+
 #include "cmdline_parse_result.h"
 #include "cmdline_types.h"
 #include "token_range.h"
@@ -399,7 +401,7 @@
             allowed_values.push_back(name);
           }
 
-          std::string allowed_values_flat = Join(allowed_values, ',');
+          std::string allowed_values_flat = android::base::Join(allowed_values, ',');
           return CmdlineResult(CmdlineResult::kFailure,
                                "Argument value '" + argument + "' does not match any of known valid"
                                 "values: {" + allowed_values_flat + "}");
@@ -426,7 +428,7 @@
             allowed_values.push_back(arg_name);
           }
 
-          std::string allowed_values_flat = Join(allowed_values, ',');
+          std::string allowed_values_flat = android::base::Join(allowed_values, ',');
           return CmdlineResult(CmdlineResult::kFailure,
                                "Argument value '" + argument + "' does not match any of known valid"
                                 "values: {" + allowed_values_flat + "}");
diff --git a/cmdline/token_range.h b/cmdline/token_range.h
index 3358067..c22d6c8 100644
--- a/cmdline/token_range.h
+++ b/cmdline/token_range.h
@@ -23,6 +23,8 @@
 #include <algorithm>
 #include <memory>
 
+#include "android-base/strings.h"
+
 namespace art {
 // A range of tokens to make token matching algorithms easier.
 //
@@ -374,7 +376,7 @@
   // e.g. ["hello", "world"].join('$') == "hello$world"
   std::string Join(char separator) const {
     TokenList tmp(begin(), end());
-    return art::Join(tmp, separator);
+    return android::base::Join(tmp, separator);
     // TODO: Join should probably take an offset or iterators
   }
 
diff --git a/compiler/Android.bp b/compiler/Android.bp
index db55ea0..2eb6fba 100644
--- a/compiler/Android.bp
+++ b/compiler/Android.bp
@@ -145,6 +145,7 @@
         mips64: {
             srcs: [
                 "jni/quick/mips64/calling_convention_mips64.cc",
+                "linker/mips64/relative_patcher_mips64.cc",
                 "optimizing/code_generator_mips64.cc",
                 "optimizing/intrinsics_mips64.cc",
                 "utils/mips64/assembler_mips64.cc",
@@ -381,6 +382,11 @@
                 "linker/mips/relative_patcher_mips32r6_test.cc",
             ],
         },
+        mips64: {
+            srcs: [
+                "linker/mips64/relative_patcher_mips64_test.cc",
+            ],
+        },
         x86: {
             srcs: [
                 "linker/x86/relative_patcher_x86_test.cc",
diff --git a/compiler/dex/verified_method.cc b/compiler/dex/verified_method.cc
index 1bdace9..a5979cc 100644
--- a/compiler/dex/verified_method.cc
+++ b/compiler/dex/verified_method.cc
@@ -218,35 +218,18 @@
 
   for (; inst < end; inst = inst->Next()) {
     Instruction::Code code = inst->Opcode();
-    if ((code == Instruction::CHECK_CAST) || (code == Instruction::APUT_OBJECT)) {
+    if (code == Instruction::CHECK_CAST) {
       uint32_t dex_pc = inst->GetDexPc(code_item->insns_);
       if (!method_verifier->GetInstructionFlags(dex_pc).IsVisited()) {
         // Do not attempt to quicken this instruction, it's unreachable anyway.
         continue;
       }
       const verifier::RegisterLine* line = method_verifier->GetRegLine(dex_pc);
-      bool is_safe_cast = false;
-      if (code == Instruction::CHECK_CAST) {
-        const verifier::RegType& reg_type(line->GetRegisterType(method_verifier,
-                                                                inst->VRegA_21c()));
-        const verifier::RegType& cast_type =
-            method_verifier->ResolveCheckedClass(dex::TypeIndex(inst->VRegB_21c()));
-        is_safe_cast = cast_type.IsStrictlyAssignableFrom(reg_type, method_verifier);
-      } else {
-        const verifier::RegType& array_type(line->GetRegisterType(method_verifier,
-                                                                  inst->VRegB_23x()));
-        // We only know its safe to assign to an array if the array type is precise. For example,
-        // an Object[] can have any type of object stored in it, but it may also be assigned a
-        // String[] in which case the stores need to be of Strings.
-        if (array_type.IsPreciseReference()) {
-          const verifier::RegType& value_type(line->GetRegisterType(method_verifier,
-                                                                    inst->VRegA_23x()));
-          const verifier::RegType& component_type = method_verifier->GetRegTypeCache()
-              ->GetComponentType(array_type, method_verifier->GetClassLoader());
-          is_safe_cast = component_type.IsStrictlyAssignableFrom(value_type, method_verifier);
-        }
-      }
-      if (is_safe_cast) {
+      const verifier::RegType& reg_type(line->GetRegisterType(method_verifier,
+                                                              inst->VRegA_21c()));
+      const verifier::RegType& cast_type =
+          method_verifier->ResolveCheckedClass(dex::TypeIndex(inst->VRegB_21c()));
+      if (cast_type.IsStrictlyAssignableFrom(reg_type, method_verifier)) {
         // Verify ordering for push_back() to the sorted vector.
         DCHECK(safe_cast_set_.empty() || safe_cast_set_.back() < dex_pc);
         safe_cast_set_.push_back(dex_pc);
diff --git a/compiler/driver/compiler_driver.cc b/compiler/driver/compiler_driver.cc
index e62bdb5..1b1de78 100644
--- a/compiler/driver/compiler_driver.cc
+++ b/compiler/driver/compiler_driver.cc
@@ -299,7 +299,7 @@
       dump_passes_(dump_passes),
       timings_logger_(timer),
       compiler_context_(nullptr),
-      support_boot_image_fixup_(instruction_set != kMips64),
+      support_boot_image_fixup_(true),
       dex_files_for_oat_file_(nullptr),
       compiled_method_storage_(swap_fd),
       profile_compilation_info_(profile_compilation_info),
diff --git a/compiler/image_writer.cc b/compiler/image_writer.cc
index a47e711..b22ca47 100644
--- a/compiler/image_writer.cc
+++ b/compiler/image_writer.cc
@@ -803,6 +803,13 @@
   result = result || PruneAppImageClassInternal(klass->GetSuperClass(),
                                                 &my_early_exit,
                                                 visited);
+  // Remove the class if the dex file is not in the set of dex files. This happens for classes that
+  // are from uses library if there is no profile. b/30688277
+  mirror::DexCache* dex_cache = klass->GetDexCache();
+  if (dex_cache != nullptr) {
+    result = result ||
+        dex_file_oat_index_map_.find(dex_cache->GetDexFile()) == dex_file_oat_index_map_.end();
+  }
   // Erase the element we stored earlier since we are exiting the function.
   auto it = visited->find(klass);
   DCHECK(it != visited->end());
diff --git a/compiler/linker/mips/relative_patcher_mips32r6_test.cc b/compiler/linker/mips/relative_patcher_mips32r6_test.cc
index a16aaca..4f9a3a0 100644
--- a/compiler/linker/mips/relative_patcher_mips32r6_test.cc
+++ b/compiler/linker/mips/relative_patcher_mips32r6_test.cc
@@ -29,10 +29,10 @@
   Mips32r6RelativePatcherTest() : RelativePatcherTest(kMips, "mips32r6") {}
 
  protected:
-  static const uint8_t UnpatchedPcRelativeRawCode[];
-  static const uint32_t LiteralOffset;
-  static const uint32_t AnchorOffset;
-  static const ArrayRef<const uint8_t> UnpatchedPcRelativeCode;
+  static const uint8_t kUnpatchedPcRelativeRawCode[];
+  static const uint32_t kLiteralOffset;
+  static const uint32_t kAnchorOffset;
+  static const ArrayRef<const uint8_t> kUnpatchedPcRelativeCode;
 
   uint32_t GetMethodOffset(uint32_t method_idx) {
     auto result = method_offset_map_.FindMethodOffset(MethodRef(method_idx));
@@ -45,24 +45,25 @@
   void TestStringReference(uint32_t string_offset);
 };
 
-const uint8_t Mips32r6RelativePatcherTest::UnpatchedPcRelativeRawCode[] = {
+const uint8_t Mips32r6RelativePatcherTest::kUnpatchedPcRelativeRawCode[] = {
     0x34, 0x12, 0x5E, 0xEE,  // auipc s2, high(diff); placeholder = 0x1234
     0x78, 0x56, 0x52, 0x26,  // addiu s2, s2, low(diff); placeholder = 0x5678
 };
-const uint32_t Mips32r6RelativePatcherTest::LiteralOffset = 0;  // At auipc (where patching starts).
-const uint32_t Mips32r6RelativePatcherTest::AnchorOffset = 0;  // At auipc (where PC+0 points).
-const ArrayRef<const uint8_t> Mips32r6RelativePatcherTest::UnpatchedPcRelativeCode(
-    UnpatchedPcRelativeRawCode);
+const uint32_t Mips32r6RelativePatcherTest::kLiteralOffset = 0;  // At auipc (where
+                                                                 // patching starts).
+const uint32_t Mips32r6RelativePatcherTest::kAnchorOffset = 0;  // At auipc (where PC+0 points).
+const ArrayRef<const uint8_t> Mips32r6RelativePatcherTest::kUnpatchedPcRelativeCode(
+    kUnpatchedPcRelativeRawCode);
 
 void Mips32r6RelativePatcherTest::CheckPcRelativePatch(const ArrayRef<const LinkerPatch>& patches,
                                                        uint32_t target_offset) {
-  AddCompiledMethod(MethodRef(1u), UnpatchedPcRelativeCode, ArrayRef<const LinkerPatch>(patches));
+  AddCompiledMethod(MethodRef(1u), kUnpatchedPcRelativeCode, ArrayRef<const LinkerPatch>(patches));
   Link();
 
   auto result = method_offset_map_.FindMethodOffset(MethodRef(1u));
   ASSERT_TRUE(result.first);
 
-  uint32_t diff = target_offset - (result.second + AnchorOffset);
+  uint32_t diff = target_offset - (result.second + kAnchorOffset);
   if (patches[0].GetType() == LinkerPatch::Type::kDexCacheArray) {
     diff += kDexCacheArrayLwOffset;
   }
@@ -79,7 +80,7 @@
                                                         uint32_t element_offset) {
   dex_cache_arrays_begin_ = dex_cache_arrays_begin;
   LinkerPatch patches[] = {
-      LinkerPatch::DexCacheArrayPatch(LiteralOffset, nullptr, AnchorOffset, element_offset)
+      LinkerPatch::DexCacheArrayPatch(kLiteralOffset, nullptr, kAnchorOffset, element_offset)
   };
   CheckPcRelativePatch(ArrayRef<const LinkerPatch>(patches),
                        dex_cache_arrays_begin_ + element_offset);
@@ -89,7 +90,7 @@
   constexpr uint32_t kStringIndex = 1u;
   string_index_to_offset_map_.Put(kStringIndex, string_offset);
   LinkerPatch patches[] = {
-      LinkerPatch::RelativeStringPatch(LiteralOffset, nullptr, AnchorOffset, kStringIndex)
+      LinkerPatch::RelativeStringPatch(kLiteralOffset, nullptr, kAnchorOffset, kStringIndex)
   };
   CheckPcRelativePatch(ArrayRef<const LinkerPatch>(patches), string_offset);
 }
diff --git a/compiler/linker/mips/relative_patcher_mips_test.cc b/compiler/linker/mips/relative_patcher_mips_test.cc
index 335ce2e..faeb92a 100644
--- a/compiler/linker/mips/relative_patcher_mips_test.cc
+++ b/compiler/linker/mips/relative_patcher_mips_test.cc
@@ -29,10 +29,10 @@
   MipsRelativePatcherTest() : RelativePatcherTest(kMips, "mips32r2") {}
 
  protected:
-  static const uint8_t UnpatchedPcRelativeRawCode[];
-  static const uint32_t LiteralOffset;
-  static const uint32_t AnchorOffset;
-  static const ArrayRef<const uint8_t> UnpatchedPcRelativeCode;
+  static const uint8_t kUnpatchedPcRelativeRawCode[];
+  static const uint32_t kLiteralOffset;
+  static const uint32_t kAnchorOffset;
+  static const ArrayRef<const uint8_t> kUnpatchedPcRelativeCode;
 
   uint32_t GetMethodOffset(uint32_t method_idx) {
     auto result = method_offset_map_.FindMethodOffset(MethodRef(method_idx));
@@ -45,26 +45,26 @@
   void TestStringReference(uint32_t string_offset);
 };
 
-const uint8_t MipsRelativePatcherTest::UnpatchedPcRelativeRawCode[] = {
+const uint8_t MipsRelativePatcherTest::kUnpatchedPcRelativeRawCode[] = {
     0x00, 0x00, 0x10, 0x04,  // nal
     0x34, 0x12, 0x12, 0x3C,  // lui  s2, high(diff); placeholder = 0x1234
     0x78, 0x56, 0x52, 0x36,  // ori  s2, s2, low(diff); placeholder = 0x5678
     0x21, 0x90, 0x5F, 0x02,  // addu s2, s2, ra
 };
-const uint32_t MipsRelativePatcherTest::LiteralOffset = 4;  // At lui (where patching starts).
-const uint32_t MipsRelativePatcherTest::AnchorOffset = 8;  // At ori (where PC+0 points).
-const ArrayRef<const uint8_t> MipsRelativePatcherTest::UnpatchedPcRelativeCode(
-    UnpatchedPcRelativeRawCode);
+const uint32_t MipsRelativePatcherTest::kLiteralOffset = 4;  // At lui (where patching starts).
+const uint32_t MipsRelativePatcherTest::kAnchorOffset = 8;  // At ori (where PC+0 points).
+const ArrayRef<const uint8_t> MipsRelativePatcherTest::kUnpatchedPcRelativeCode(
+    kUnpatchedPcRelativeRawCode);
 
 void MipsRelativePatcherTest::CheckPcRelativePatch(const ArrayRef<const LinkerPatch>& patches,
                                                    uint32_t target_offset) {
-  AddCompiledMethod(MethodRef(1u), UnpatchedPcRelativeCode, ArrayRef<const LinkerPatch>(patches));
+  AddCompiledMethod(MethodRef(1u), kUnpatchedPcRelativeCode, ArrayRef<const LinkerPatch>(patches));
   Link();
 
   auto result = method_offset_map_.FindMethodOffset(MethodRef(1u));
   ASSERT_TRUE(result.first);
 
-  uint32_t diff = target_offset - (result.second + AnchorOffset);
+  uint32_t diff = target_offset - (result.second + kAnchorOffset);
   if (patches[0].GetType() == LinkerPatch::Type::kDexCacheArray) {
     diff += kDexCacheArrayLwOffset;
   }
@@ -82,7 +82,7 @@
                                                     uint32_t element_offset) {
   dex_cache_arrays_begin_ = dex_cache_arrays_begin;
   LinkerPatch patches[] = {
-      LinkerPatch::DexCacheArrayPatch(LiteralOffset, nullptr, AnchorOffset, element_offset)
+      LinkerPatch::DexCacheArrayPatch(kLiteralOffset, nullptr, kAnchorOffset, element_offset)
   };
   CheckPcRelativePatch(ArrayRef<const LinkerPatch>(patches),
                        dex_cache_arrays_begin_ + element_offset);
@@ -92,7 +92,7 @@
   constexpr uint32_t kStringIndex = 1u;
   string_index_to_offset_map_.Put(kStringIndex, string_offset);
   LinkerPatch patches[] = {
-      LinkerPatch::RelativeStringPatch(LiteralOffset, nullptr, AnchorOffset, kStringIndex)
+      LinkerPatch::RelativeStringPatch(kLiteralOffset, nullptr, kAnchorOffset, kStringIndex)
   };
   CheckPcRelativePatch(ArrayRef<const LinkerPatch>(patches), string_offset);
 }
diff --git a/compiler/linker/mips64/relative_patcher_mips64.cc b/compiler/linker/mips64/relative_patcher_mips64.cc
new file mode 100644
index 0000000..c479716
--- /dev/null
+++ b/compiler/linker/mips64/relative_patcher_mips64.cc
@@ -0,0 +1,111 @@
+/*
+ * Copyright (C) 2016 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 "linker/mips64/relative_patcher_mips64.h"
+
+#include "compiled_method.h"
+
+namespace art {
+namespace linker {
+
+uint32_t Mips64RelativePatcher::ReserveSpace(
+    uint32_t offset,
+    const CompiledMethod* compiled_method ATTRIBUTE_UNUSED,
+    MethodReference method_ref ATTRIBUTE_UNUSED) {
+  return offset;  // No space reserved; no limit on relative call distance.
+}
+
+uint32_t Mips64RelativePatcher::ReserveSpaceEnd(uint32_t offset) {
+  return offset;  // No space reserved; no limit on relative call distance.
+}
+
+uint32_t Mips64RelativePatcher::WriteThunks(OutputStream* out ATTRIBUTE_UNUSED, uint32_t offset) {
+  return offset;  // No thunks added; no limit on relative call distance.
+}
+
+void Mips64RelativePatcher::PatchCall(std::vector<uint8_t>* code,
+                                      uint32_t literal_offset,
+                                      uint32_t patch_offset,
+                                      uint32_t target_offset) {
+  // Basic sanity checks.
+  DCHECK_GE(code->size(), 8u);
+  DCHECK_LE(literal_offset, code->size() - 8u);
+  // auipc reg, offset_high
+  DCHECK_EQ((*code)[literal_offset + 0], 0x34);
+  DCHECK_EQ((*code)[literal_offset + 1], 0x12);
+  DCHECK_EQ(((*code)[literal_offset + 2] & 0x1F), 0x1E);
+  DCHECK_EQ(((*code)[literal_offset + 3] & 0xFC), 0xEC);
+  // jialc reg, offset_low
+  DCHECK_EQ((*code)[literal_offset + 4], 0x78);
+  DCHECK_EQ((*code)[literal_offset + 5], 0x56);
+  DCHECK_EQ(((*code)[literal_offset + 6] & 0xE0), 0x00);
+  DCHECK_EQ((*code)[literal_offset + 7], 0xF8);
+
+  // Apply patch.
+  uint32_t diff = target_offset - patch_offset;
+  // Note that a combination of auipc with an instruction that adds a sign-extended
+  // 16-bit immediate operand (e.g. jialc) provides a PC-relative range of
+  // PC-0x80000000 to PC+0x7FFF7FFF on MIPS64, that is, short of 2GB on one end
+  // by 32KB.
+  diff += (diff & 0x8000) << 1;  // Account for sign extension in jialc.
+
+  // auipc reg, offset_high
+  (*code)[literal_offset + 0] = static_cast<uint8_t>(diff >> 16);
+  (*code)[literal_offset + 1] = static_cast<uint8_t>(diff >> 24);
+  // jialc reg, offset_low
+  (*code)[literal_offset + 4] = static_cast<uint8_t>(diff >> 0);
+  (*code)[literal_offset + 5] = static_cast<uint8_t>(diff >> 8);
+}
+
+void Mips64RelativePatcher::PatchPcRelativeReference(std::vector<uint8_t>* code,
+                                                     const LinkerPatch& patch,
+                                                     uint32_t patch_offset,
+                                                     uint32_t target_offset) {
+  uint32_t anchor_literal_offset = patch.PcInsnOffset();
+  uint32_t literal_offset = patch.LiteralOffset();
+
+  // Basic sanity checks.
+  DCHECK_GE(code->size(), 8u);
+  DCHECK_LE(literal_offset, code->size() - 8u);
+  DCHECK_EQ(literal_offset, anchor_literal_offset);
+  // auipc reg, offset_high
+  DCHECK_EQ((*code)[literal_offset + 0], 0x34);
+  DCHECK_EQ((*code)[literal_offset + 1], 0x12);
+  DCHECK_EQ(((*code)[literal_offset + 2] & 0x1F), 0x1E);
+  DCHECK_EQ(((*code)[literal_offset + 3] & 0xFC), 0xEC);
+  // instr reg(s), offset_low
+  DCHECK_EQ((*code)[literal_offset + 4], 0x78);
+  DCHECK_EQ((*code)[literal_offset + 5], 0x56);
+
+  // Apply patch.
+  uint32_t anchor_offset = patch_offset - literal_offset + anchor_literal_offset;
+  uint32_t diff = target_offset - anchor_offset;
+  // Note that a combination of auipc with an instruction that adds a sign-extended
+  // 16-bit immediate operand (e.g. ld) provides a PC-relative range of
+  // PC-0x80000000 to PC+0x7FFF7FFF on MIPS64, that is, short of 2GB on one end
+  // by 32KB.
+  diff += (diff & 0x8000) << 1;  // Account for sign extension in instruction following auipc.
+
+  // auipc reg, offset_high
+  (*code)[literal_offset + 0] = static_cast<uint8_t>(diff >> 16);
+  (*code)[literal_offset + 1] = static_cast<uint8_t>(diff >> 24);
+  // instr reg(s), offset_low
+  (*code)[literal_offset + 4] = static_cast<uint8_t>(diff >> 0);
+  (*code)[literal_offset + 5] = static_cast<uint8_t>(diff >> 8);
+}
+
+}  // namespace linker
+}  // namespace art
diff --git a/compiler/linker/mips64/relative_patcher_mips64.h b/compiler/linker/mips64/relative_patcher_mips64.h
new file mode 100644
index 0000000..8ef8ceb
--- /dev/null
+++ b/compiler/linker/mips64/relative_patcher_mips64.h
@@ -0,0 +1,50 @@
+/*
+ * Copyright (C) 2016 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_LINKER_MIPS64_RELATIVE_PATCHER_MIPS64_H_
+#define ART_COMPILER_LINKER_MIPS64_RELATIVE_PATCHER_MIPS64_H_
+
+#include "linker/relative_patcher.h"
+
+namespace art {
+namespace linker {
+
+class Mips64RelativePatcher FINAL : public RelativePatcher {
+ public:
+  explicit Mips64RelativePatcher() {}
+
+  uint32_t ReserveSpace(uint32_t offset,
+                        const CompiledMethod* compiled_method,
+                        MethodReference method_ref) OVERRIDE;
+  uint32_t ReserveSpaceEnd(uint32_t offset) OVERRIDE;
+  uint32_t WriteThunks(OutputStream* out, uint32_t offset) OVERRIDE;
+  void PatchCall(std::vector<uint8_t>* code,
+                 uint32_t literal_offset,
+                 uint32_t patch_offset,
+                 uint32_t target_offset) OVERRIDE;
+  void PatchPcRelativeReference(std::vector<uint8_t>* code,
+                                const LinkerPatch& patch,
+                                uint32_t patch_offset,
+                                uint32_t target_offset) OVERRIDE;
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(Mips64RelativePatcher);
+};
+
+}  // namespace linker
+}  // namespace art
+
+#endif  // ART_COMPILER_LINKER_MIPS64_RELATIVE_PATCHER_MIPS64_H_
diff --git a/compiler/linker/mips64/relative_patcher_mips64_test.cc b/compiler/linker/mips64/relative_patcher_mips64_test.cc
new file mode 100644
index 0000000..9e37f6b
--- /dev/null
+++ b/compiler/linker/mips64/relative_patcher_mips64_test.cc
@@ -0,0 +1,127 @@
+/*
+ * Copyright (C) 2016 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 "linker/relative_patcher_test.h"
+#include "linker/mips64/relative_patcher_mips64.h"
+
+namespace art {
+namespace linker {
+
+class Mips64RelativePatcherTest : public RelativePatcherTest {
+ public:
+  Mips64RelativePatcherTest() : RelativePatcherTest(kMips64, "default") {}
+
+ protected:
+  static const uint8_t kUnpatchedPcRelativeRawCode[];
+  static const uint8_t kUnpatchedPcRelativeCallRawCode[];
+  static const uint32_t kLiteralOffset;
+  static const uint32_t kAnchorOffset;
+  static const ArrayRef<const uint8_t> kUnpatchedPcRelativeCode;
+  static const ArrayRef<const uint8_t> kUnpatchedPcRelativeCallCode;
+
+  uint32_t GetMethodOffset(uint32_t method_idx) {
+    auto result = method_offset_map_.FindMethodOffset(MethodRef(method_idx));
+    CHECK(result.first);
+    return result.second;
+  }
+
+  void CheckPcRelativePatch(const ArrayRef<const LinkerPatch>& patches, uint32_t target_offset);
+  void TestDexCacheReference(uint32_t dex_cache_arrays_begin, uint32_t element_offset);
+  void TestStringReference(uint32_t string_offset);
+};
+
+const uint8_t Mips64RelativePatcherTest::kUnpatchedPcRelativeRawCode[] = {
+    0x34, 0x12, 0x5E, 0xEE,  // auipc s2, high(diff); placeholder = 0x1234
+    0x78, 0x56, 0x52, 0x26,  // addiu s2, s2, low(diff); placeholder = 0x5678
+};
+const uint8_t Mips64RelativePatcherTest::kUnpatchedPcRelativeCallRawCode[] = {
+    0x34, 0x12, 0x3E, 0xEC,  // auipc at, high(diff); placeholder = 0x1234
+    0x78, 0x56, 0x01, 0xF8,  // jialc at, low(diff); placeholder = 0x5678
+};
+const uint32_t Mips64RelativePatcherTest::kLiteralOffset = 0;  // At auipc (where patching starts).
+const uint32_t Mips64RelativePatcherTest::kAnchorOffset = 0;  // At auipc (where PC+0 points).
+const ArrayRef<const uint8_t> Mips64RelativePatcherTest::kUnpatchedPcRelativeCode(
+    kUnpatchedPcRelativeRawCode);
+const ArrayRef<const uint8_t> Mips64RelativePatcherTest::kUnpatchedPcRelativeCallCode(
+    kUnpatchedPcRelativeCallRawCode);
+
+void Mips64RelativePatcherTest::CheckPcRelativePatch(const ArrayRef<const LinkerPatch>& patches,
+                                                     uint32_t target_offset) {
+  AddCompiledMethod(MethodRef(1u), kUnpatchedPcRelativeCode, ArrayRef<const LinkerPatch>(patches));
+  Link();
+
+  auto result = method_offset_map_.FindMethodOffset(MethodRef(1u));
+  ASSERT_TRUE(result.first);
+
+  uint32_t diff = target_offset - (result.second + kAnchorOffset);
+  diff += (diff & 0x8000) << 1;  // Account for sign extension in instruction following auipc.
+
+  const uint8_t expected_code[] = {
+      static_cast<uint8_t>(diff >> 16), static_cast<uint8_t>(diff >> 24), 0x5E, 0xEE,
+      static_cast<uint8_t>(diff), static_cast<uint8_t>(diff >> 8), 0x52, 0x26,
+  };
+  EXPECT_TRUE(CheckLinkedMethod(MethodRef(1u), ArrayRef<const uint8_t>(expected_code)));
+}
+
+void Mips64RelativePatcherTest::TestDexCacheReference(uint32_t dex_cache_arrays_begin,
+                                                      uint32_t element_offset) {
+  dex_cache_arrays_begin_ = dex_cache_arrays_begin;
+  LinkerPatch patches[] = {
+      LinkerPatch::DexCacheArrayPatch(kLiteralOffset, nullptr, kAnchorOffset, element_offset)
+  };
+  CheckPcRelativePatch(ArrayRef<const LinkerPatch>(patches),
+                       dex_cache_arrays_begin_ + element_offset);
+}
+
+TEST_F(Mips64RelativePatcherTest, DexCacheReference) {
+  TestDexCacheReference(/* dex_cache_arrays_begin */ 0x12345678, /* element_offset */ 0x1234);
+}
+
+TEST_F(Mips64RelativePatcherTest, CallOther) {
+  LinkerPatch method1_patches[] = {
+      LinkerPatch::RelativeCodePatch(kLiteralOffset, nullptr, 2u),
+  };
+  AddCompiledMethod(MethodRef(1u),
+                    kUnpatchedPcRelativeCallCode,
+                    ArrayRef<const LinkerPatch>(method1_patches));
+  LinkerPatch method2_patches[] = {
+      LinkerPatch::RelativeCodePatch(kLiteralOffset, nullptr, 1u),
+  };
+  AddCompiledMethod(MethodRef(2u),
+                    kUnpatchedPcRelativeCallCode,
+                    ArrayRef<const LinkerPatch>(method2_patches));
+  Link();
+
+  uint32_t method1_offset = GetMethodOffset(1u);
+  uint32_t method2_offset = GetMethodOffset(2u);
+  uint32_t diff_after = method2_offset - (method1_offset + kAnchorOffset /* PC adjustment */);
+  diff_after += (diff_after & 0x8000) << 1;  // Account for sign extension in jialc.
+  static const uint8_t method1_expected_code[] = {
+      static_cast<uint8_t>(diff_after >> 16), static_cast<uint8_t>(diff_after >> 24), 0x3E, 0xEC,
+      static_cast<uint8_t>(diff_after), static_cast<uint8_t>(diff_after >> 8), 0x01, 0xF8,
+  };
+  EXPECT_TRUE(CheckLinkedMethod(MethodRef(1u), ArrayRef<const uint8_t>(method1_expected_code)));
+  uint32_t diff_before = method1_offset - (method2_offset + kAnchorOffset /* PC adjustment */);
+  diff_before += (diff_before & 0x8000) << 1;  // Account for sign extension in jialc.
+  static const uint8_t method2_expected_code[] = {
+      static_cast<uint8_t>(diff_before >> 16), static_cast<uint8_t>(diff_before >> 24), 0x3E, 0xEC,
+      static_cast<uint8_t>(diff_before), static_cast<uint8_t>(diff_before >> 8), 0x01, 0xF8,
+  };
+  EXPECT_TRUE(CheckLinkedMethod(MethodRef(2u), ArrayRef<const uint8_t>(method2_expected_code)));
+}
+
+}  // namespace linker
+}  // namespace art
diff --git a/compiler/linker/relative_patcher.cc b/compiler/linker/relative_patcher.cc
index 7765594..f1538b1 100644
--- a/compiler/linker/relative_patcher.cc
+++ b/compiler/linker/relative_patcher.cc
@@ -25,6 +25,9 @@
 #ifdef ART_ENABLE_CODEGEN_mips
 #include "linker/mips/relative_patcher_mips.h"
 #endif
+#ifdef ART_ENABLE_CODEGEN_mips64
+#include "linker/mips64/relative_patcher_mips64.h"
+#endif
 #ifdef ART_ENABLE_CODEGEN_x86
 #include "linker/x86/relative_patcher_x86.h"
 #endif
@@ -103,6 +106,10 @@
       return std::unique_ptr<RelativePatcher>(
           new MipsRelativePatcher(features->AsMipsInstructionSetFeatures()));
 #endif
+#ifdef ART_ENABLE_CODEGEN_mips64
+    case kMips64:
+      return std::unique_ptr<RelativePatcher>(new Mips64RelativePatcher());
+#endif
     default:
       return std::unique_ptr<RelativePatcher>(new RelativePatcherNone);
   }
diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc
index 866f2c5..8104613 100644
--- a/compiler/optimizing/code_generator_arm.cc
+++ b/compiler/optimizing/code_generator_arm.cc
@@ -7370,10 +7370,6 @@
   return DeduplicateUint32Literal(dchecked_integral_cast<uint32_t>(address), map);
 }
 
-Literal* CodeGeneratorARM::DeduplicateDexCacheAddressLiteral(uint32_t address) {
-  return DeduplicateUint32Literal(address, &uint32_literals_);
-}
-
 Literal* CodeGeneratorARM::DeduplicateJitStringLiteral(const DexFile& dex_file,
                                                        dex::StringIndex string_index) {
   jit_string_roots_.Overwrite(StringReference(&dex_file, string_index), /* placeholder */ 0u);
diff --git a/compiler/optimizing/code_generator_arm.h b/compiler/optimizing/code_generator_arm.h
index b929172..605169d 100644
--- a/compiler/optimizing/code_generator_arm.h
+++ b/compiler/optimizing/code_generator_arm.h
@@ -489,7 +489,6 @@
                                              dex::StringIndex string_index);
   Literal* DeduplicateBootImageTypeLiteral(const DexFile& dex_file, dex::TypeIndex type_index);
   Literal* DeduplicateBootImageAddressLiteral(uint32_t address);
-  Literal* DeduplicateDexCacheAddressLiteral(uint32_t address);
   Literal* DeduplicateJitStringLiteral(const DexFile& dex_file, dex::StringIndex string_index);
   Literal* DeduplicateJitClassLiteral(const DexFile& dex_file,
                                       dex::TypeIndex type_index,
diff --git a/compiler/optimizing/code_generator_arm64.cc b/compiler/optimizing/code_generator_arm64.cc
index 89e5d9e..5cff303 100644
--- a/compiler/optimizing/code_generator_arm64.cc
+++ b/compiler/optimizing/code_generator_arm64.cc
@@ -4171,11 +4171,6 @@
   return DeduplicateUint32Literal(dchecked_integral_cast<uint32_t>(address), map);
 }
 
-vixl::aarch64::Literal<uint64_t>* CodeGeneratorARM64::DeduplicateDexCacheAddressLiteral(
-    uint64_t address) {
-  return DeduplicateUint64Literal(address);
-}
-
 vixl::aarch64::Literal<uint32_t>* CodeGeneratorARM64::DeduplicateJitStringLiteral(
     const DexFile& dex_file, dex::StringIndex string_index) {
   jit_string_roots_.Overwrite(StringReference(&dex_file, string_index), /* placeholder */ 0u);
diff --git a/compiler/optimizing/code_generator_arm64.h b/compiler/optimizing/code_generator_arm64.h
index 50bbc99..85b6f9f 100644
--- a/compiler/optimizing/code_generator_arm64.h
+++ b/compiler/optimizing/code_generator_arm64.h
@@ -566,7 +566,6 @@
   vixl::aarch64::Literal<uint32_t>* DeduplicateBootImageTypeLiteral(const DexFile& dex_file,
                                                                     dex::TypeIndex type_index);
   vixl::aarch64::Literal<uint32_t>* DeduplicateBootImageAddressLiteral(uint64_t address);
-  vixl::aarch64::Literal<uint64_t>* DeduplicateDexCacheAddressLiteral(uint64_t address);
   vixl::aarch64::Literal<uint32_t>* DeduplicateJitStringLiteral(const DexFile& dex_file,
                                                                 dex::StringIndex string_index);
   vixl::aarch64::Literal<uint32_t>* DeduplicateJitClassLiteral(const DexFile& dex_file,
@@ -736,8 +735,7 @@
 
   // Deduplication map for 32-bit literals, used for non-patchable boot image addresses.
   Uint32ToLiteralMap uint32_literals_;
-  // Deduplication map for 64-bit literals, used for non-patchable method address, method code
-  // or string dex cache address.
+  // Deduplication map for 64-bit literals, used for non-patchable method address or method code.
   Uint64ToLiteralMap uint64_literals_;
   // Method patch info, map MethodReference to a literal for method address and method code.
   MethodToLiteralMap method_patches_;
diff --git a/compiler/optimizing/code_generator_mips.cc b/compiler/optimizing/code_generator_mips.cc
index cae4161..456c5c6 100644
--- a/compiler/optimizing/code_generator_mips.cc
+++ b/compiler/optimizing/code_generator_mips.cc
@@ -757,6 +757,11 @@
   if (RequiresCurrentMethod()) {
     __ StoreToOffset(kStoreWord, kMethodRegisterArgument, SP, kCurrentMethodStackOffset);
   }
+
+  if (GetGraph()->HasShouldDeoptimizeFlag()) {
+    // Initialize should deoptimize flag to 0.
+    __ StoreToOffset(kStoreWord, ZERO, SP, GetStackOffsetOfShouldDeoptimizeFlag());
+  }
 }
 
 void CodeGeneratorMIPS::GenerateFrameExit() {
@@ -4689,14 +4694,17 @@
   }
 }
 
-void LocationsBuilderMIPS::VisitShouldDeoptimizeFlag(
-    HShouldDeoptimizeFlag* flag ATTRIBUTE_UNUSED) {
-  // TODO: to be implemented.
+void LocationsBuilderMIPS::VisitShouldDeoptimizeFlag(HShouldDeoptimizeFlag* flag) {
+  LocationSummary* locations = new (GetGraph()->GetArena())
+      LocationSummary(flag, LocationSummary::kNoCall);
+  locations->SetOut(Location::RequiresRegister());
 }
 
-void InstructionCodeGeneratorMIPS::VisitShouldDeoptimizeFlag(
-    HShouldDeoptimizeFlag* flag ATTRIBUTE_UNUSED) {
-  // TODO: to be implemented.
+void InstructionCodeGeneratorMIPS::VisitShouldDeoptimizeFlag(HShouldDeoptimizeFlag* flag) {
+  __ LoadFromOffset(kLoadWord,
+                    flag->GetLocations()->Out().AsRegister<Register>(),
+                    SP,
+                    codegen_->GetStackOffsetOfShouldDeoptimizeFlag());
 }
 
 void LocationsBuilderMIPS::VisitSelect(HSelect* select) {
diff --git a/compiler/optimizing/code_generator_mips64.cc b/compiler/optimizing/code_generator_mips64.cc
index b1f9b1d..44d3759 100644
--- a/compiler/optimizing/code_generator_mips64.cc
+++ b/compiler/optimizing/code_generator_mips64.cc
@@ -18,6 +18,7 @@
 
 #include "art_method.h"
 #include "code_generator_utils.h"
+#include "compiled_method.h"
 #include "entrypoints/quick/quick_entrypoints.h"
 #include "entrypoints/quick/quick_entrypoints_enum.h"
 #include "gc/accounting/card_table.h"
@@ -399,7 +400,15 @@
       instruction_visitor_(graph, this),
       move_resolver_(graph->GetArena(), this),
       assembler_(graph->GetArena()),
-      isa_features_(isa_features) {
+      isa_features_(isa_features),
+      uint64_literals_(std::less<uint64_t>(),
+                       graph->GetArena()->Adapter(kArenaAllocCodeGenerator)),
+      method_patches_(MethodReferenceComparator(),
+                      graph->GetArena()->Adapter(kArenaAllocCodeGenerator)),
+      call_patches_(MethodReferenceComparator(),
+                    graph->GetArena()->Adapter(kArenaAllocCodeGenerator)),
+      pc_relative_dex_cache_patches_(graph->GetArena()->Adapter(kArenaAllocCodeGenerator)),
+      relative_call_patches_(graph->GetArena()->Adapter(kArenaAllocCodeGenerator)) {
   // Save RA (containing the return address) to mimic Quick.
   AddAllocatedRegister(Location::RegisterLocation(RA));
 }
@@ -510,8 +519,6 @@
     RecordPcInfo(nullptr, 0);
   }
 
-  // TODO: anything related to T9/GP/GOT/PIC/.so's?
-
   if (HasEmptyFrame()) {
     return;
   }
@@ -562,13 +569,16 @@
                   "kCurrentMethodStackOffset must fit into int16_t");
     __ Sd(kMethodRegisterArgument, SP, kCurrentMethodStackOffset);
   }
+
+  if (GetGraph()->HasShouldDeoptimizeFlag()) {
+    // Initialize should_deoptimize flag to 0.
+    __ StoreToOffset(kStoreWord, ZERO, SP, GetStackOffsetOfShouldDeoptimizeFlag());
+  }
 }
 
 void CodeGeneratorMIPS64::GenerateFrameExit() {
   __ cfi().RememberState();
 
-  // TODO: anything related to T9/GP/GOT/PIC/.so's?
-
   if (!HasEmptyFrame()) {
     // Deallocate the rest of the frame.
 
@@ -878,6 +888,103 @@
   }
 }
 
+template <LinkerPatch (*Factory)(size_t, const DexFile*, uint32_t, uint32_t)>
+inline void CodeGeneratorMIPS64::EmitPcRelativeLinkerPatches(
+    const ArenaDeque<PcRelativePatchInfo>& infos,
+    ArenaVector<LinkerPatch>* linker_patches) {
+  for (const PcRelativePatchInfo& info : infos) {
+    const DexFile& dex_file = info.target_dex_file;
+    size_t offset_or_index = info.offset_or_index;
+    DCHECK(info.pc_rel_label.IsBound());
+    uint32_t pc_rel_offset = __ GetLabelLocation(&info.pc_rel_label);
+    linker_patches->push_back(Factory(pc_rel_offset, &dex_file, pc_rel_offset, offset_or_index));
+  }
+}
+
+void CodeGeneratorMIPS64::EmitLinkerPatches(ArenaVector<LinkerPatch>* linker_patches) {
+  DCHECK(linker_patches->empty());
+  size_t size =
+      method_patches_.size() +
+      call_patches_.size() +
+      pc_relative_dex_cache_patches_.size() +
+      relative_call_patches_.size();
+  linker_patches->reserve(size);
+  for (const auto& entry : method_patches_) {
+    const MethodReference& target_method = entry.first;
+    Literal* literal = entry.second;
+    DCHECK(literal->GetLabel()->IsBound());
+    uint32_t literal_offset = __ GetLabelLocation(literal->GetLabel());
+    linker_patches->push_back(LinkerPatch::MethodPatch(literal_offset,
+                                                       target_method.dex_file,
+                                                       target_method.dex_method_index));
+  }
+  for (const auto& entry : call_patches_) {
+    const MethodReference& target_method = entry.first;
+    Literal* literal = entry.second;
+    DCHECK(literal->GetLabel()->IsBound());
+    uint32_t literal_offset = __ GetLabelLocation(literal->GetLabel());
+    linker_patches->push_back(LinkerPatch::CodePatch(literal_offset,
+                                                     target_method.dex_file,
+                                                     target_method.dex_method_index));
+  }
+  EmitPcRelativeLinkerPatches<LinkerPatch::DexCacheArrayPatch>(pc_relative_dex_cache_patches_,
+                                                               linker_patches);
+  for (const PcRelativePatchInfo& info : relative_call_patches_) {
+    const DexFile& dex_file = info.target_dex_file;
+    uint32_t method_index = info.offset_or_index;
+    DCHECK(info.pc_rel_label.IsBound());
+    uint32_t pc_rel_offset = __ GetLabelLocation(&info.pc_rel_label);
+    linker_patches->push_back(
+        LinkerPatch::RelativeCodePatch(pc_rel_offset, &dex_file, method_index));
+  }
+}
+
+CodeGeneratorMIPS64::PcRelativePatchInfo* CodeGeneratorMIPS64::NewPcRelativeDexCacheArrayPatch(
+    const DexFile& dex_file, uint32_t element_offset) {
+  return NewPcRelativePatch(dex_file, element_offset, &pc_relative_dex_cache_patches_);
+}
+
+CodeGeneratorMIPS64::PcRelativePatchInfo* CodeGeneratorMIPS64::NewPcRelativeCallPatch(
+    const DexFile& dex_file, uint32_t method_index) {
+  return NewPcRelativePatch(dex_file, method_index, &relative_call_patches_);
+}
+
+CodeGeneratorMIPS64::PcRelativePatchInfo* CodeGeneratorMIPS64::NewPcRelativePatch(
+    const DexFile& dex_file, uint32_t offset_or_index, ArenaDeque<PcRelativePatchInfo>* patches) {
+  patches->emplace_back(dex_file, offset_or_index);
+  return &patches->back();
+}
+
+Literal* CodeGeneratorMIPS64::DeduplicateUint64Literal(uint64_t value) {
+  return uint64_literals_.GetOrCreate(
+      value,
+      [this, value]() { return __ NewLiteral<uint64_t>(value); });
+}
+
+Literal* CodeGeneratorMIPS64::DeduplicateMethodLiteral(MethodReference target_method,
+                                                       MethodToLiteralMap* map) {
+  return map->GetOrCreate(
+      target_method,
+      [this]() { return __ NewLiteral<uint32_t>(/* placeholder */ 0u); });
+}
+
+Literal* CodeGeneratorMIPS64::DeduplicateMethodAddressLiteral(MethodReference target_method) {
+  return DeduplicateMethodLiteral(target_method, &method_patches_);
+}
+
+Literal* CodeGeneratorMIPS64::DeduplicateMethodCodeLiteral(MethodReference target_method) {
+  return DeduplicateMethodLiteral(target_method, &call_patches_);
+}
+
+void CodeGeneratorMIPS64::EmitPcRelativeAddressPlaceholderHigh(PcRelativePatchInfo* info,
+                                                               GpuRegister out) {
+  __ Bind(&info->pc_rel_label);
+  // Add the high half of a 32-bit offset to PC.
+  __ Auipc(out, /* placeholder */ 0x1234);
+  // The immediately following instruction will add the sign-extended low half of the 32-bit
+  // offset to `out` (e.g. ld, jialc, addiu).
+}
+
 void CodeGeneratorMIPS64::SetupBlockedRegisters() const {
   // ZERO, K0, K1, GP, SP, RA are always reserved and can't be allocated.
   blocked_core_registers_[ZERO] = true;
@@ -946,7 +1053,6 @@
                                         uint32_t dex_pc,
                                         SlowPathCode* slow_path) {
   ValidateInvokeRuntime(entrypoint, instruction, slow_path);
-  // TODO: anything related to T9/GP/GOT/PIC/.so's?
   __ LoadFromOffset(kLoadDoubleword,
                     T9,
                     TR,
@@ -2636,14 +2742,17 @@
                         /* false_target */ nullptr);
 }
 
-void LocationsBuilderMIPS64::VisitShouldDeoptimizeFlag(
-    HShouldDeoptimizeFlag* flag ATTRIBUTE_UNUSED) {
-  // TODO: to be implemented.
+void LocationsBuilderMIPS64::VisitShouldDeoptimizeFlag(HShouldDeoptimizeFlag* flag) {
+  LocationSummary* locations = new (GetGraph()->GetArena())
+      LocationSummary(flag, LocationSummary::kNoCall);
+  locations->SetOut(Location::RequiresRegister());
 }
 
-void InstructionCodeGeneratorMIPS64::VisitShouldDeoptimizeFlag(
-    HShouldDeoptimizeFlag* flag ATTRIBUTE_UNUSED) {
-  // TODO: to be implemented.
+void InstructionCodeGeneratorMIPS64::VisitShouldDeoptimizeFlag(HShouldDeoptimizeFlag* flag) {
+  __ LoadFromOffset(kLoadWord,
+                    flag->GetLocations()->Out().AsRegister<GpuRegister>(),
+                    SP,
+                    codegen_->GetStackOffsetOfShouldDeoptimizeFlag());
 }
 
 void LocationsBuilderMIPS64::VisitSelect(HSelect* select) {
@@ -2986,39 +3095,33 @@
 HInvokeStaticOrDirect::DispatchInfo CodeGeneratorMIPS64::GetSupportedInvokeStaticOrDirectDispatch(
       const HInvokeStaticOrDirect::DispatchInfo& desired_dispatch_info,
       HInvokeStaticOrDirect* invoke ATTRIBUTE_UNUSED) {
-  switch (desired_dispatch_info.method_load_kind) {
-    case HInvokeStaticOrDirect::MethodLoadKind::kDirectAddressWithFixup:
-    case HInvokeStaticOrDirect::MethodLoadKind::kDexCachePcRelative:
-      // TODO: Implement these types. For the moment, we fall back to kDexCacheViaMethod.
-      return HInvokeStaticOrDirect::DispatchInfo {
-        HInvokeStaticOrDirect::MethodLoadKind::kDexCacheViaMethod,
-        HInvokeStaticOrDirect::CodePtrLocation::kCallArtMethod,
-        0u,
-        0u
-      };
-    default:
-      break;
-  }
-  switch (desired_dispatch_info.code_ptr_location) {
-    case HInvokeStaticOrDirect::CodePtrLocation::kCallDirectWithFixup:
-    case HInvokeStaticOrDirect::CodePtrLocation::kCallPCRelative:
-      // TODO: Implement these types. For the moment, we fall back to kCallArtMethod.
-      return HInvokeStaticOrDirect::DispatchInfo {
-        desired_dispatch_info.method_load_kind,
-        HInvokeStaticOrDirect::CodePtrLocation::kCallArtMethod,
-        desired_dispatch_info.method_load_data,
-        0u
-      };
-    default:
-      return desired_dispatch_info;
-  }
+  // On MIPS64 we support all dispatch types.
+  return desired_dispatch_info;
 }
 
 void CodeGeneratorMIPS64::GenerateStaticOrDirectCall(HInvokeStaticOrDirect* invoke, Location temp) {
   // All registers are assumed to be correctly set up per the calling convention.
-
   Location callee_method = temp;  // For all kinds except kRecursive, callee will be in temp.
-  switch (invoke->GetMethodLoadKind()) {
+  HInvokeStaticOrDirect::MethodLoadKind method_load_kind = invoke->GetMethodLoadKind();
+  HInvokeStaticOrDirect::CodePtrLocation code_ptr_location = invoke->GetCodePtrLocation();
+
+  // For better instruction scheduling we load the direct code pointer before the method pointer.
+  switch (code_ptr_location) {
+    case HInvokeStaticOrDirect::CodePtrLocation::kCallDirect:
+      // T9 = invoke->GetDirectCodePtr();
+      __ LoadLiteral(T9, kLoadDoubleword, DeduplicateUint64Literal(invoke->GetDirectCodePtr()));
+      break;
+    case HInvokeStaticOrDirect::CodePtrLocation::kCallDirectWithFixup:
+      // T9 = code address from literal pool with link-time patch.
+      __ LoadLiteral(T9,
+                     kLoadUnsignedWord,
+                     DeduplicateMethodCodeLiteral(invoke->GetTargetMethod()));
+      break;
+    default:
+      break;
+  }
+
+  switch (method_load_kind) {
     case HInvokeStaticOrDirect::MethodLoadKind::kStringInit: {
       // temp = thread->string_init_entrypoint
       uint32_t offset =
@@ -3033,14 +3136,23 @@
       callee_method = invoke->GetLocations()->InAt(invoke->GetSpecialInputIndex());
       break;
     case HInvokeStaticOrDirect::MethodLoadKind::kDirectAddress:
-      __ LoadConst64(temp.AsRegister<GpuRegister>(), invoke->GetMethodAddress());
+      __ LoadLiteral(temp.AsRegister<GpuRegister>(),
+                     kLoadDoubleword,
+                     DeduplicateUint64Literal(invoke->GetMethodAddress()));
       break;
     case HInvokeStaticOrDirect::MethodLoadKind::kDirectAddressWithFixup:
-    case HInvokeStaticOrDirect::MethodLoadKind::kDexCachePcRelative:
-      // TODO: Implement these types.
-      // Currently filtered out by GetSupportedInvokeStaticOrDirectDispatch().
-      LOG(FATAL) << "Unsupported";
-      UNREACHABLE();
+      __ LoadLiteral(temp.AsRegister<GpuRegister>(),
+                     kLoadUnsignedWord,
+                     DeduplicateMethodAddressLiteral(invoke->GetTargetMethod()));
+      break;
+    case HInvokeStaticOrDirect::MethodLoadKind::kDexCachePcRelative: {
+      uint32_t offset = invoke->GetDexCacheArrayOffset();
+      CodeGeneratorMIPS64::PcRelativePatchInfo* info =
+          NewPcRelativeDexCacheArrayPatch(invoke->GetDexFile(), offset);
+      EmitPcRelativeAddressPlaceholderHigh(info, AT);
+      __ Ld(temp.AsRegister<GpuRegister>(), AT, /* placeholder */ 0x5678);
+      break;
+    }
     case HInvokeStaticOrDirect::MethodLoadKind::kDexCacheViaMethod: {
       Location current_method = invoke->GetLocations()->InAt(invoke->GetSpecialInputIndex());
       GpuRegister reg = temp.AsRegister<GpuRegister>();
@@ -3071,23 +3183,25 @@
     }
   }
 
-  switch (invoke->GetCodePtrLocation()) {
+  switch (code_ptr_location) {
     case HInvokeStaticOrDirect::CodePtrLocation::kCallSelf:
-      __ Jialc(&frame_entry_label_, T9);
+      __ Balc(&frame_entry_label_);
       break;
     case HInvokeStaticOrDirect::CodePtrLocation::kCallDirect:
-      // LR = invoke->GetDirectCodePtr();
-      __ LoadConst64(T9, invoke->GetDirectCodePtr());
-      // LR()
+    case HInvokeStaticOrDirect::CodePtrLocation::kCallDirectWithFixup:
+      // T9 prepared above for better instruction scheduling.
+      // T9()
       __ Jalr(T9);
       __ Nop();
       break;
-    case HInvokeStaticOrDirect::CodePtrLocation::kCallDirectWithFixup:
-    case HInvokeStaticOrDirect::CodePtrLocation::kCallPCRelative:
-      // TODO: Implement these types.
-      // Currently filtered out by GetSupportedInvokeStaticOrDirectDispatch().
-      LOG(FATAL) << "Unsupported";
-      UNREACHABLE();
+    case HInvokeStaticOrDirect::CodePtrLocation::kCallPCRelative: {
+      CodeGeneratorMIPS64::PcRelativePatchInfo* info =
+          NewPcRelativeCallPatch(*invoke->GetTargetMethod().dex_file,
+                                 invoke->GetTargetMethod().dex_method_index);
+      EmitPcRelativeAddressPlaceholderHigh(info, AT);
+      __ Jialc(AT, /* placeholder */ 0x5678);
+      break;
+    }
     case HInvokeStaticOrDirect::CodePtrLocation::kCallArtMethod:
       // T9 = callee_method->entry_point_from_quick_compiled_code_;
       __ LoadFromOffset(kLoadDoubleword,
diff --git a/compiler/optimizing/code_generator_mips64.h b/compiler/optimizing/code_generator_mips64.h
index 690eccb..067c1f9 100644
--- a/compiler/optimizing/code_generator_mips64.h
+++ b/compiler/optimizing/code_generator_mips64.h
@@ -279,6 +279,9 @@
   Mips64Assembler* GetAssembler() OVERRIDE { return &assembler_; }
   const Mips64Assembler& GetAssembler() const OVERRIDE { return assembler_; }
 
+  // Emit linker patches.
+  void EmitLinkerPatches(ArenaVector<LinkerPatch>* linker_patches) OVERRIDE;
+
   void MarkGCCard(GpuRegister object, GpuRegister value, bool value_can_be_null);
 
   // Register allocation.
@@ -357,7 +360,44 @@
   void GenerateImplicitNullCheck(HNullCheck* instruction) OVERRIDE;
   void GenerateExplicitNullCheck(HNullCheck* instruction) OVERRIDE;
 
+  // The PcRelativePatchInfo is used for PC-relative addressing of dex cache arrays,
+  // boot image strings and method calls. The only difference is the interpretation of
+  // the offset_or_index.
+  struct PcRelativePatchInfo {
+    PcRelativePatchInfo(const DexFile& dex_file, uint32_t off_or_idx)
+        : target_dex_file(dex_file), offset_or_index(off_or_idx) { }
+    PcRelativePatchInfo(PcRelativePatchInfo&& other) = default;
+
+    const DexFile& target_dex_file;
+    // Either the dex cache array element offset or the string/type/method index.
+    uint32_t offset_or_index;
+    // Label for the auipc instruction.
+    Mips64Label pc_rel_label;
+  };
+
+  PcRelativePatchInfo* NewPcRelativeDexCacheArrayPatch(const DexFile& dex_file,
+                                                       uint32_t element_offset);
+  PcRelativePatchInfo* NewPcRelativeCallPatch(const DexFile& dex_file,
+                                              uint32_t method_index);
+
+  void EmitPcRelativeAddressPlaceholderHigh(PcRelativePatchInfo* info, GpuRegister out);
+
  private:
+  using Uint64ToLiteralMap = ArenaSafeMap<uint64_t, Literal*>;
+  using MethodToLiteralMap = ArenaSafeMap<MethodReference, Literal*, MethodReferenceComparator>;
+  Literal* DeduplicateUint64Literal(uint64_t value);
+  Literal* DeduplicateMethodLiteral(MethodReference target_method, MethodToLiteralMap* map);
+  Literal* DeduplicateMethodAddressLiteral(MethodReference target_method);
+  Literal* DeduplicateMethodCodeLiteral(MethodReference target_method);
+
+  PcRelativePatchInfo* NewPcRelativePatch(const DexFile& dex_file,
+                                          uint32_t offset_or_index,
+                                          ArenaDeque<PcRelativePatchInfo>* patches);
+
+  template <LinkerPatch (*Factory)(size_t, const DexFile*, uint32_t, uint32_t)>
+  void EmitPcRelativeLinkerPatches(const ArenaDeque<PcRelativePatchInfo>& infos,
+                                   ArenaVector<LinkerPatch>* linker_patches);
+
   // Labels for each block that will be compiled.
   Mips64Label* block_labels_;  // Indexed by block id.
   Mips64Label frame_entry_label_;
@@ -367,6 +407,16 @@
   Mips64Assembler assembler_;
   const Mips64InstructionSetFeatures& isa_features_;
 
+  // Deduplication map for 64-bit literals, used for non-patchable method address or method code
+  // address.
+  Uint64ToLiteralMap uint64_literals_;
+  // Method patch info, map MethodReference to a literal for method address and method code.
+  MethodToLiteralMap method_patches_;
+  MethodToLiteralMap call_patches_;
+  // PC-relative patch info.
+  ArenaDeque<PcRelativePatchInfo> pc_relative_dex_cache_patches_;
+  ArenaDeque<PcRelativePatchInfo> relative_call_patches_;
+
   DISALLOW_COPY_AND_ASSIGN(CodeGeneratorMIPS64);
 };
 
diff --git a/compiler/optimizing/code_generator_utils.h b/compiler/optimizing/code_generator_utils.h
index 7efed8c..a6b41c0 100644
--- a/compiler/optimizing/code_generator_utils.h
+++ b/compiler/optimizing/code_generator_utils.h
@@ -18,6 +18,8 @@
 #define ART_COMPILER_OPTIMIZING_CODE_GENERATOR_UTILS_H_
 
 #include <cstdint>
+#include <cstdlib>
+#include <limits>
 
 namespace art {
 
@@ -32,6 +34,12 @@
 // that it has been previously visited by the InstructionCodeGenerator.
 bool IsBooleanValueOrMaterializedCondition(HInstruction* cond_input);
 
+template <typename T> T AbsOrMin(T value) {
+  return (value == std::numeric_limits<T>::min())
+      ? value
+      : std::abs(value);
+}
+
 }  // namespace art
 
 #endif  // ART_COMPILER_OPTIMIZING_CODE_GENERATOR_UTILS_H_
diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc
index 658b804..c615df1 100644
--- a/compiler/optimizing/instruction_simplifier.cc
+++ b/compiler/optimizing/instruction_simplifier.cc
@@ -1185,6 +1185,18 @@
   RecordSimplification();
 }
 
+// Return whether x / divisor == x * (1.0f / divisor), for every float x.
+static constexpr bool CanDivideByReciprocalMultiplyFloat(int32_t divisor) {
+  // True, if the most significant bits of divisor are 0.
+  return ((divisor & 0x7fffff) == 0);
+}
+
+// Return whether x / divisor == x * (1.0 / divisor), for every double x.
+static constexpr bool CanDivideByReciprocalMultiplyDouble(int64_t divisor) {
+  // True, if the most significant bits of divisor are 0.
+  return ((divisor & ((UINT64_C(1) << 52) - 1)) == 0);
+}
+
 void InstructionSimplifierVisitor::VisitDiv(HDiv* instruction) {
   HConstant* input_cst = instruction->GetConstantRight();
   HInstruction* input_other = instruction->GetLeastConstantLeft();
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 925d4f1..1e946d6 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -2440,6 +2440,17 @@
   }
 }
 
+// Helper for InstructionDataEquals to fetch the mirror Class out
+// from a kJitTableAddress LoadClass kind.
+// NO_THREAD_SAFETY_ANALYSIS because even though we're accessing
+// mirrors, they are stored in a variable size handle scope which is always
+// visited during a pause. Also, the only caller of this helper
+// only uses the mirror for pointer comparison.
+static inline mirror::Class* AsMirrorInternal(uint64_t address)
+    NO_THREAD_SAFETY_ANALYSIS {
+  return reinterpret_cast<StackReference<mirror::Class>*>(address)->AsMirrorPtr();
+}
+
 bool HLoadClass::InstructionDataEquals(const HInstruction* other) const {
   const HLoadClass* other_load_class = other->AsLoadClass();
   // TODO: To allow GVN for HLoadClass from different dex files, we should compare the type
@@ -2448,16 +2459,14 @@
       GetPackedFields() != other_load_class->GetPackedFields()) {
     return false;
   }
-  LoadKind load_kind = GetLoadKind();
-  if (HasAddress(load_kind)) {
-    return GetAddress() == other_load_class->GetAddress();
-  } else if (HasTypeReference(load_kind)) {
-    return IsSameDexFile(GetDexFile(), other_load_class->GetDexFile());
-  } else {
-    DCHECK(HasDexCacheReference(load_kind)) << load_kind;
-    // If the type indexes and dex files are the same, dex cache element offsets
-    // must also be the same, so we don't need to compare them.
-    return IsSameDexFile(GetDexFile(), other_load_class->GetDexFile());
+  switch (GetLoadKind()) {
+    case LoadKind::kBootImageAddress:
+      return GetAddress() == other_load_class->GetAddress();
+    case LoadKind::kJitTableAddress:
+      return AsMirrorInternal(GetAddress()) == AsMirrorInternal(other_load_class->GetAddress());
+    default:
+      DCHECK(HasTypeReference(GetLoadKind()) || HasDexCacheReference(GetLoadKind()));
+      return IsSameDexFile(GetDexFile(), other_load_class->GetDexFile());
   }
 }
 
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 659cdda..4a8cfcb 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -125,6 +125,11 @@
   kAnalysisSuccess,
 };
 
+template <typename T>
+static inline typename std::make_unsigned<T>::type MakeUnsigned(T x) {
+  return static_cast<typename std::make_unsigned<T>::type>(x);
+}
+
 class HInstructionList : public ValueObject {
  public:
   HInstructionList() : first_instruction_(nullptr), last_instruction_(nullptr) {}
diff --git a/compiler/optimizing/optimizing_cfi_test.cc b/compiler/optimizing/optimizing_cfi_test.cc
index 013e110..0e02311 100644
--- a/compiler/optimizing/optimizing_cfi_test.cc
+++ b/compiler/optimizing/optimizing_cfi_test.cc
@@ -24,12 +24,22 @@
 #include "optimizing/code_generator.h"
 #include "optimizing/optimizing_unit_test.h"
 #include "utils/assembler.h"
+#ifdef ART_USE_VIXL_ARM_BACKEND
+#include "utils/arm/assembler_arm_vixl.h"
+#else
 #include "utils/arm/assembler_thumb2.h"
+#endif
 #include "utils/mips/assembler_mips.h"
 #include "utils/mips64/assembler_mips64.h"
 
 #include "optimizing/optimizing_cfi_test_expected.inc"
 
+#ifdef ART_USE_VIXL_ARM_BACKEND
+namespace vixl32 = vixl::aarch32;
+
+using vixl32::r0;
+#endif
+
 namespace art {
 
 // Run the tests only on host.
@@ -158,8 +168,7 @@
     TestImpl(isa, #isa, expected_asm, expected_cfi);          \
   }
 
-// TODO(VIXL): Support this test for the VIXL backend.
-#if defined(ART_ENABLE_CODEGEN_arm) && !defined(ART_USE_VIXL_ARM_BACKEND)
+#ifdef ART_ENABLE_CODEGEN_arm
 TEST_ISA(kThumb2)
 #endif
 #ifdef ART_ENABLE_CODEGEN_arm64
@@ -178,8 +187,7 @@
 TEST_ISA(kMips64)
 #endif
 
-// TODO(VIXL): Support this test for the VIXL backend.
-#if defined(ART_ENABLE_CODEGEN_arm) && !defined(ART_USE_VIXL_ARM_BACKEND)
+#ifdef ART_ENABLE_CODEGEN_arm
 TEST_F(OptimizingCFITest, kThumb2Adjust) {
   std::vector<uint8_t> expected_asm(
       expected_asm_kThumb2_adjust,
@@ -188,6 +196,16 @@
       expected_cfi_kThumb2_adjust,
       expected_cfi_kThumb2_adjust + arraysize(expected_cfi_kThumb2_adjust));
   SetUpFrame(kThumb2);
+#ifdef ART_USE_VIXL_ARM_BACKEND
+#define __ down_cast<arm::ArmVIXLAssembler*>(GetCodeGenerator() \
+    ->GetAssembler())->GetVIXLAssembler()->
+  vixl32::Label target;
+  __ CompareAndBranchIfZero(r0, &target);
+  // Push the target out of range of CBZ.
+  for (size_t i = 0; i != 65; ++i) {
+    __ Ldr(r0, vixl32::MemOperand(r0));
+  }
+#else
 #define __ down_cast<arm::Thumb2Assembler*>(GetCodeGenerator()->GetAssembler())->
   Label target;
   __ CompareAndBranchIfZero(arm::R0, &target);
@@ -195,6 +213,7 @@
   for (size_t i = 0; i != 65; ++i) {
     __ ldr(arm::R0, arm::Address(arm::R0));
   }
+#endif
   __ Bind(&target);
 #undef __
   Finish();
diff --git a/compiler/optimizing/optimizing_cfi_test_expected.inc b/compiler/optimizing/optimizing_cfi_test_expected.inc
index f735dc8..82670c3 100644
--- a/compiler/optimizing/optimizing_cfi_test_expected.inc
+++ b/compiler/optimizing/optimizing_cfi_test_expected.inc
@@ -223,8 +223,16 @@
 // 0x00000040: .cfi_def_cfa_offset: 64
 
 static constexpr uint8_t expected_asm_kThumb2_adjust[] = {
+#ifdef ART_USE_VIXL_ARM_BACKEND
+    // VIXL emits an extra 2 bytes here for a 32-bit beq as there is no
+    // optimistic 16-bit emit and subsequent fixup for out of reach targets
+    // as with the current assembler.
+    0x60, 0xB5, 0x2D, 0xED, 0x02, 0x8A, 0x8B, 0xB0, 0x00, 0x28, 0x00, 0xF0,
+    0x41, 0x80, 0x00, 0x68, 0x00, 0x68, 0x00, 0x68, 0x00, 0x68, 0x00, 0x68,
+#else
     0x60, 0xB5, 0x2D, 0xED, 0x02, 0x8A, 0x8B, 0xB0, 0x00, 0x28,
     0x40, 0xD0, 0x00, 0x68, 0x00, 0x68, 0x00, 0x68, 0x00, 0x68, 0x00, 0x68,
+#endif
     0x00, 0x68, 0x00, 0x68, 0x00, 0x68, 0x00, 0x68, 0x00, 0x68, 0x00, 0x68,
     0x00, 0x68, 0x00, 0x68, 0x00, 0x68, 0x00, 0x68, 0x00, 0x68, 0x00, 0x68,
     0x00, 0x68, 0x00, 0x68, 0x00, 0x68, 0x00, 0x68, 0x00, 0x68, 0x00, 0x68,
@@ -239,7 +247,11 @@
 };
 static constexpr uint8_t expected_cfi_kThumb2_adjust[] = {
     0x42, 0x0E, 0x0C, 0x85, 0x03, 0x86, 0x02, 0x8E, 0x01, 0x44, 0x0E, 0x14,
+#ifdef ART_USE_VIXL_ARM_BACKEND
+    0x05, 0x50, 0x05, 0x05, 0x51, 0x04, 0x42, 0x0E, 0x40, 0x02, 0x88, 0x0A,
+#else
     0x05, 0x50, 0x05, 0x05, 0x51, 0x04, 0x42, 0x0E, 0x40, 0x02, 0x86, 0x0A,
+#endif
     0x42, 0x0E, 0x14, 0x44, 0x0E, 0x0C, 0x06, 0x50, 0x06, 0x51, 0x42, 0x0B,
     0x0E, 0x40,
 };
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 64c87dc..ba7012a 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -22,6 +22,8 @@
 
 #include <stdint.h>
 
+#include "android-base/strings.h"
+
 #ifdef ART_ENABLE_CODEGEN_arm
 #include "dex_cache_array_fixups_arm.h"
 #endif
@@ -1115,7 +1117,8 @@
 bool IsCompilingWithCoreImage() {
   const std::string& image = Runtime::Current()->GetImageLocation();
   // TODO: This is under-approximating...
-  if (EndsWith(image, "core.art") || EndsWith(image, "core-optimizing.art")) {
+  if (android::base::EndsWith(image, "core.art") ||
+      android::base::EndsWith(image, "core-optimizing.art")) {
     return true;
   }
   return false;
diff --git a/compiler/optimizing/sharpening.cc b/compiler/optimizing/sharpening.cc
index bbbb1a1..91efb80 100644
--- a/compiler/optimizing/sharpening.cc
+++ b/compiler/optimizing/sharpening.cc
@@ -197,7 +197,9 @@
           // out which class loader to use.
           address = reinterpret_cast<uint64_t>(handles_->NewHandle(klass).GetReference());
         } else {
-          // Class not loaded yet. Fallback to the dex cache.
+          // Class not loaded yet. This happens when the dex code requesting
+          // this `HLoadClass` hasn't been executed in the interpreter.
+          // Fallback to the dex cache.
           // TODO(ngeoffray): Generate HDeoptimize instead.
           desired_load_kind = HLoadClass::LoadKind::kDexCacheViaMethod;
         }
diff --git a/compiler/utils/assembler_test_base.h b/compiler/utils/assembler_test_base.h
index ac24ee9..e7edf96 100644
--- a/compiler/utils/assembler_test_base.h
+++ b/compiler/utils/assembler_test_base.h
@@ -23,6 +23,8 @@
 #include <iterator>
 #include <sys/stat.h>
 
+#include "android-base/strings.h"
+
 #include "common_runtime_test.h"  // For ScratchFile
 #include "utils.h"
 
@@ -221,7 +223,7 @@
     args.push_back("-o");
     args.push_back(to_file);
     args.push_back(from_file);
-    std::string cmd = Join(args, ' ');
+    std::string cmd = android::base::Join(args, ' ');
 
     args.clear();
     args.push_back("/bin/sh");
@@ -257,7 +259,7 @@
     args.push_back(file);
     args.push_back(">");
     args.push_back(file+".dump");
-    std::string cmd = Join(args, ' ');
+    std::string cmd = android::base::Join(args, ' ');
 
     args.clear();
     args.push_back("/bin/sh");
@@ -338,7 +340,7 @@
     args.push_back("| sed -n \'/<.data>/,$p\' | sed -e \'s/.*://\'");
     args.push_back(">");
     args.push_back(file+".dis");
-    std::string cmd = Join(args, ' ');
+    std::string cmd = android::base::Join(args, ' ');
 
     args.clear();
     args.push_back("/bin/sh");
@@ -500,7 +502,7 @@
     std::string tmp_file = GetTmpnam();
     args.push_back(">");
     args.push_back(tmp_file);
-    std::string sh_args = Join(args, ' ');
+    std::string sh_args = android::base::Join(args, ' ');
 
     args.clear();
     args.push_back("/bin/sh");
@@ -541,7 +543,7 @@
     args.push_back("sort");
     args.push_back(">");
     args.push_back(tmp_file);
-    std::string sh_args = Join(args, ' ');
+    std::string sh_args = android::base::Join(args, ' ');
 
     args.clear();
     args.push_back("/bin/sh");
diff --git a/compiler/utils/mips64/assembler_mips64.cc b/compiler/utils/mips64/assembler_mips64.cc
index 1a21df9..84280b9 100644
--- a/compiler/utils/mips64/assembler_mips64.cc
+++ b/compiler/utils/mips64/assembler_mips64.cc
@@ -35,6 +35,7 @@
   for (auto& exception_block : exception_blocks_) {
     EmitExceptionPoll(&exception_block);
   }
+  EmitLiterals();
   PromoteBranches();
 }
 
@@ -450,6 +451,21 @@
   EmitI(0x27, rs, rt, imm16);
 }
 
+void Mips64Assembler::Lwpc(GpuRegister rs, uint32_t imm19) {
+  CHECK(IsUint<19>(imm19)) << imm19;
+  EmitI21(0x3B, rs, (0x01 << 19) | imm19);
+}
+
+void Mips64Assembler::Lwupc(GpuRegister rs, uint32_t imm19) {
+  CHECK(IsUint<19>(imm19)) << imm19;
+  EmitI21(0x3B, rs, (0x02 << 19) | imm19);
+}
+
+void Mips64Assembler::Ldpc(GpuRegister rs, uint32_t imm18) {
+  CHECK(IsUint<18>(imm18)) << imm18;
+  EmitI21(0x3B, rs, (0x06 << 18) | imm18);
+}
+
 void Mips64Assembler::Lui(GpuRegister rt, uint16_t imm16) {
   EmitI(0xf, static_cast<GpuRegister>(0), rt, imm16);
 }
@@ -548,6 +564,10 @@
   EmitI26(0x32, imm26);
 }
 
+void Mips64Assembler::Balc(uint32_t imm26) {
+  EmitI26(0x3A, imm26);
+}
+
 void Mips64Assembler::Jic(GpuRegister rt, uint16_t imm16) {
   EmitI(0x36, static_cast<GpuRegister>(0), rt, imm16);
 }
@@ -1064,19 +1084,37 @@
   type_ = (offset_size <= branch_info_[short_type].offset_size) ? short_type : long_type;
 }
 
-void Mips64Assembler::Branch::InitializeType(bool is_call) {
+void Mips64Assembler::Branch::InitializeType(Type initial_type) {
   OffsetBits offset_size = GetOffsetSizeNeeded(location_, target_);
-  if (is_call) {
-    InitShortOrLong(offset_size, kCall, kLongCall);
-  } else if (condition_ == kUncond) {
-    InitShortOrLong(offset_size, kUncondBranch, kLongUncondBranch);
-  } else {
-    if (condition_ == kCondEQZ || condition_ == kCondNEZ) {
-      // Special case for beqzc/bnezc with longer offset than in other b<cond>c instructions.
-      type_ = (offset_size <= kOffset23) ? kCondBranch : kLongCondBranch;
-    } else {
-      InitShortOrLong(offset_size, kCondBranch, kLongCondBranch);
-    }
+  switch (initial_type) {
+    case kLabel:
+    case kLiteral:
+    case kLiteralUnsigned:
+    case kLiteralLong:
+      CHECK(!IsResolved());
+      type_ = initial_type;
+      break;
+    case kCall:
+      InitShortOrLong(offset_size, kCall, kLongCall);
+      break;
+    case kCondBranch:
+      switch (condition_) {
+        case kUncond:
+          InitShortOrLong(offset_size, kUncondBranch, kLongUncondBranch);
+          break;
+        case kCondEQZ:
+        case kCondNEZ:
+          // Special case for beqzc/bnezc with longer offset than in other b<cond>c instructions.
+          type_ = (offset_size <= kOffset23) ? kCondBranch : kLongCondBranch;
+          break;
+        default:
+          InitShortOrLong(offset_size, kCondBranch, kLongCondBranch);
+          break;
+      }
+      break;
+    default:
+      LOG(FATAL) << "Unexpected branch type " << initial_type;
+      UNREACHABLE();
   }
   old_type_ = type_;
 }
@@ -1109,14 +1147,14 @@
   }
 }
 
-Mips64Assembler::Branch::Branch(uint32_t location, uint32_t target)
+Mips64Assembler::Branch::Branch(uint32_t location, uint32_t target, bool is_call)
     : old_location_(location),
       location_(location),
       target_(target),
       lhs_reg_(ZERO),
       rhs_reg_(ZERO),
       condition_(kUncond) {
-  InitializeType(false);
+  InitializeType(is_call ? kCall : kCondBranch);
 }
 
 Mips64Assembler::Branch::Branch(uint32_t location,
@@ -1164,19 +1202,18 @@
     // Branch condition is always true, make the branch unconditional.
     condition_ = kUncond;
   }
-  InitializeType(false);
+  InitializeType(kCondBranch);
 }
 
-Mips64Assembler::Branch::Branch(uint32_t location, uint32_t target, GpuRegister indirect_reg)
+Mips64Assembler::Branch::Branch(uint32_t location, GpuRegister dest_reg, Type label_or_literal_type)
     : old_location_(location),
       location_(location),
-      target_(target),
-      lhs_reg_(indirect_reg),
+      target_(kUnresolved),
+      lhs_reg_(dest_reg),
       rhs_reg_(ZERO),
       condition_(kUncond) {
-  CHECK_NE(indirect_reg, ZERO);
-  CHECK_NE(indirect_reg, AT);
-  InitializeType(true);
+  CHECK_NE(dest_reg, ZERO);
+  InitializeType(label_or_literal_type);
 }
 
 Mips64Assembler::BranchCondition Mips64Assembler::Branch::OppositeCondition(
@@ -1278,11 +1315,23 @@
     case kUncondBranch:
     case kCondBranch:
     case kCall:
+    // Near label.
+    case kLabel:
+    // Near literals.
+    case kLiteral:
+    case kLiteralUnsigned:
+    case kLiteralLong:
       return false;
     // Long branches.
     case kLongUncondBranch:
     case kLongCondBranch:
     case kLongCall:
+    // Far label.
+    case kFarLabel:
+    // Far literals.
+    case kFarLiteral:
+    case kFarLiteralUnsigned:
+    case kFarLiteralLong:
       return true;
   }
   UNREACHABLE();
@@ -1351,6 +1400,20 @@
     case kCall:
       type_ = kLongCall;
       break;
+    // Near label.
+    case kLabel:
+      type_ = kFarLabel;
+      break;
+    // Near literals.
+    case kLiteral:
+      type_ = kFarLiteral;
+      break;
+    case kLiteralUnsigned:
+      type_ = kFarLiteralUnsigned;
+      break;
+    case kLiteralLong:
+      type_ = kFarLiteralLong;
+      break;
     default:
       // Note: 'type_' is already long.
       break;
@@ -1397,7 +1460,15 @@
   uint32_t ofs_mask = 0xFFFFFFFF >> (32 - GetOffsetSize());
   // Calculate the byte distance between instructions and also account for
   // different PC-relative origins.
-  uint32_t offset = target_ - GetOffsetLocation() - branch_info_[type_].pc_org * sizeof(uint32_t);
+  uint32_t offset_location = GetOffsetLocation();
+  if (type_ == kLiteralLong) {
+    // Special case for the ldpc instruction, whose address (PC) is rounded down to
+    // a multiple of 8 before adding the offset.
+    // Note, branch promotion has already taken care of aligning `target_` to an
+    // address that's a multiple of 8.
+    offset_location = RoundDown(offset_location, sizeof(uint64_t));
+  }
+  uint32_t offset = target_ - offset_location - branch_info_[type_].pc_org * sizeof(uint32_t);
   // Prepare the offset for encoding into the instruction(s).
   offset = (offset & ofs_mask) >> branch_info_[type_].offset_shift;
   return offset;
@@ -1444,7 +1515,7 @@
   label->BindTo(bound_pc);
 }
 
-uint32_t Mips64Assembler::GetLabelLocation(Mips64Label* label) const {
+uint32_t Mips64Assembler::GetLabelLocation(const Mips64Label* label) const {
   CHECK(label->IsBound());
   uint32_t target = label->Position();
   if (label->prev_branch_id_plus_one_) {
@@ -1500,7 +1571,7 @@
 
 void Mips64Assembler::Buncond(Mips64Label* label) {
   uint32_t target = label->IsBound() ? GetLabelLocation(label) : Branch::kUnresolved;
-  branches_.emplace_back(buffer_.Size(), target);
+  branches_.emplace_back(buffer_.Size(), target, /* is_call */ false);
   FinalizeLabeledBranch(label);
 }
 
@@ -1517,12 +1588,87 @@
   FinalizeLabeledBranch(label);
 }
 
-void Mips64Assembler::Call(Mips64Label* label, GpuRegister indirect_reg) {
+void Mips64Assembler::Call(Mips64Label* label) {
   uint32_t target = label->IsBound() ? GetLabelLocation(label) : Branch::kUnresolved;
-  branches_.emplace_back(buffer_.Size(), target, indirect_reg);
+  branches_.emplace_back(buffer_.Size(), target, /* is_call */ true);
   FinalizeLabeledBranch(label);
 }
 
+void Mips64Assembler::LoadLabelAddress(GpuRegister dest_reg, Mips64Label* label) {
+  // Label address loads are treated as pseudo branches since they require very similar handling.
+  DCHECK(!label->IsBound());
+  branches_.emplace_back(buffer_.Size(), dest_reg, Branch::kLabel);
+  FinalizeLabeledBranch(label);
+}
+
+Literal* Mips64Assembler::NewLiteral(size_t size, const uint8_t* data) {
+  // We don't support byte and half-word literals.
+  if (size == 4u) {
+    literals_.emplace_back(size, data);
+    return &literals_.back();
+  } else {
+    DCHECK_EQ(size, 8u);
+    long_literals_.emplace_back(size, data);
+    return &long_literals_.back();
+  }
+}
+
+void Mips64Assembler::LoadLiteral(GpuRegister dest_reg,
+                                  LoadOperandType load_type,
+                                  Literal* literal) {
+  // Literal loads are treated as pseudo branches since they require very similar handling.
+  Branch::Type literal_type;
+  switch (load_type) {
+    case kLoadWord:
+      DCHECK_EQ(literal->GetSize(), 4u);
+      literal_type = Branch::kLiteral;
+      break;
+    case kLoadUnsignedWord:
+      DCHECK_EQ(literal->GetSize(), 4u);
+      literal_type = Branch::kLiteralUnsigned;
+      break;
+    case kLoadDoubleword:
+      DCHECK_EQ(literal->GetSize(), 8u);
+      literal_type = Branch::kLiteralLong;
+      break;
+    default:
+      LOG(FATAL) << "Unexpected literal load type " << load_type;
+      UNREACHABLE();
+  }
+  Mips64Label* label = literal->GetLabel();
+  DCHECK(!label->IsBound());
+  branches_.emplace_back(buffer_.Size(), dest_reg, literal_type);
+  FinalizeLabeledBranch(label);
+}
+
+void Mips64Assembler::EmitLiterals() {
+  if (!literals_.empty()) {
+    for (Literal& literal : literals_) {
+      Mips64Label* label = literal.GetLabel();
+      Bind(label);
+      AssemblerBuffer::EnsureCapacity ensured(&buffer_);
+      DCHECK_EQ(literal.GetSize(), 4u);
+      for (size_t i = 0, size = literal.GetSize(); i != size; ++i) {
+        buffer_.Emit<uint8_t>(literal.GetData()[i]);
+      }
+    }
+  }
+  if (!long_literals_.empty()) {
+    // Reserve 4 bytes for potential alignment. If after the branch promotion the 64-bit
+    // literals don't end up 8-byte-aligned, they will be moved down 4 bytes.
+    Emit(0);  // NOP.
+    for (Literal& literal : long_literals_) {
+      Mips64Label* label = literal.GetLabel();
+      Bind(label);
+      AssemblerBuffer::EnsureCapacity ensured(&buffer_);
+      DCHECK_EQ(literal.GetSize(), 8u);
+      for (size_t i = 0, size = literal.GetSize(); i != size; ++i) {
+        buffer_.Emit<uint8_t>(literal.GetData()[i]);
+      }
+    }
+  }
+}
+
 void Mips64Assembler::PromoteBranches() {
   // Promote short branches to long as necessary.
   bool changed;
@@ -1561,6 +1707,35 @@
       end = branch.GetOldLocation();
     }
   }
+
+  // Align 64-bit literals by moving them down by 4 bytes if needed.
+  // This will reduce the PC-relative distance, which should be safe for both near and far literals.
+  if (!long_literals_.empty()) {
+    uint32_t first_literal_location = GetLabelLocation(long_literals_.front().GetLabel());
+    size_t lit_size = long_literals_.size() * sizeof(uint64_t);
+    size_t buf_size = buffer_.Size();
+    // 64-bit literals must be at the very end of the buffer.
+    CHECK_EQ(first_literal_location + lit_size, buf_size);
+    if (!IsAligned<sizeof(uint64_t)>(first_literal_location)) {
+      buffer_.Move(first_literal_location - sizeof(uint32_t), first_literal_location, lit_size);
+      // The 4 reserved bytes proved useless, reduce the buffer size.
+      buffer_.Resize(buf_size - sizeof(uint32_t));
+      // Reduce target addresses in literal and address loads by 4 bytes in order for correct
+      // offsets from PC to be generated.
+      for (auto& branch : branches_) {
+        uint32_t target = branch.GetTarget();
+        if (target >= first_literal_location) {
+          branch.Resolve(target - sizeof(uint32_t));
+        }
+      }
+      // If after this we ever call GetLabelLocation() to get the location of a 64-bit literal,
+      // we need to adjust the location of the literal's label as well.
+      for (Literal& literal : long_literals_) {
+        // Bound label's position is negative, hence incrementing it instead of decrementing.
+        literal.GetLabel()->position_ += sizeof(uint32_t);
+      }
+    }
+  }
 }
 
 // Note: make sure branch_info_[] and EmitBranch() are kept synchronized.
@@ -1569,11 +1744,23 @@
   {  1, 0, 1, Mips64Assembler::Branch::kOffset28, 2 },  // kUncondBranch
   {  2, 0, 1, Mips64Assembler::Branch::kOffset18, 2 },  // kCondBranch
                                                         // Exception: kOffset23 for beqzc/bnezc
-  {  2, 0, 0, Mips64Assembler::Branch::kOffset21, 2 },  // kCall
+  {  1, 0, 1, Mips64Assembler::Branch::kOffset28, 2 },  // kCall
+  // Near label.
+  {  1, 0, 0, Mips64Assembler::Branch::kOffset21, 2 },  // kLabel
+  // Near literals.
+  {  1, 0, 0, Mips64Assembler::Branch::kOffset21, 2 },  // kLiteral
+  {  1, 0, 0, Mips64Assembler::Branch::kOffset21, 2 },  // kLiteralUnsigned
+  {  1, 0, 0, Mips64Assembler::Branch::kOffset21, 3 },  // kLiteralLong
   // Long branches.
   {  2, 0, 0, Mips64Assembler::Branch::kOffset32, 0 },  // kLongUncondBranch
   {  3, 1, 0, Mips64Assembler::Branch::kOffset32, 0 },  // kLongCondBranch
-  {  3, 0, 0, Mips64Assembler::Branch::kOffset32, 0 },  // kLongCall
+  {  2, 0, 0, Mips64Assembler::Branch::kOffset32, 0 },  // kLongCall
+  // Far label.
+  {  2, 0, 0, Mips64Assembler::Branch::kOffset32, 0 },  // kFarLabel
+  // Far literals.
+  {  2, 0, 0, Mips64Assembler::Branch::kOffset32, 0 },  // kFarLiteral
+  {  2, 0, 0, Mips64Assembler::Branch::kOffset32, 0 },  // kFarLiteralUnsigned
+  {  2, 0, 0, Mips64Assembler::Branch::kOffset32, 0 },  // kFarLiteralLong
 };
 
 // Note: make sure branch_info_[] and EmitBranch() are kept synchronized.
@@ -1597,8 +1784,26 @@
       break;
     case Branch::kCall:
       CHECK_EQ(overwrite_location_, branch->GetOffsetLocation());
+      Balc(offset);
+      break;
+
+    // Near label.
+    case Branch::kLabel:
+      CHECK_EQ(overwrite_location_, branch->GetOffsetLocation());
       Addiupc(lhs, offset);
-      Jialc(lhs, 0);
+      break;
+    // Near literals.
+    case Branch::kLiteral:
+      CHECK_EQ(overwrite_location_, branch->GetOffsetLocation());
+      Lwpc(lhs, offset);
+      break;
+    case Branch::kLiteralUnsigned:
+      CHECK_EQ(overwrite_location_, branch->GetOffsetLocation());
+      Lwupc(lhs, offset);
+      break;
+    case Branch::kLiteralLong:
+      CHECK_EQ(overwrite_location_, branch->GetOffsetLocation());
+      Ldpc(lhs, offset);
       break;
 
     // Long branches.
@@ -1616,11 +1821,37 @@
       Jic(AT, Low16Bits(offset));
       break;
     case Branch::kLongCall:
-      offset += (offset & 0x8000) << 1;  // Account for sign extension in daddiu.
+      offset += (offset & 0x8000) << 1;  // Account for sign extension in jialc.
       CHECK_EQ(overwrite_location_, branch->GetOffsetLocation());
-      Auipc(lhs, High16Bits(offset));
-      Daddiu(lhs, lhs, Low16Bits(offset));
-      Jialc(lhs, 0);
+      Auipc(AT, High16Bits(offset));
+      Jialc(AT, Low16Bits(offset));
+      break;
+
+    // Far label.
+    case Branch::kFarLabel:
+      offset += (offset & 0x8000) << 1;  // Account for sign extension in addiu.
+      CHECK_EQ(overwrite_location_, branch->GetOffsetLocation());
+      Auipc(AT, High16Bits(offset));
+      Addiu(lhs, AT, Low16Bits(offset));
+      break;
+    // Far literals.
+    case Branch::kFarLiteral:
+      offset += (offset & 0x8000) << 1;  // Account for sign extension in lw.
+      CHECK_EQ(overwrite_location_, branch->GetOffsetLocation());
+      Auipc(AT, High16Bits(offset));
+      Lw(lhs, AT, Low16Bits(offset));
+      break;
+    case Branch::kFarLiteralUnsigned:
+      offset += (offset & 0x8000) << 1;  // Account for sign extension in lwu.
+      CHECK_EQ(overwrite_location_, branch->GetOffsetLocation());
+      Auipc(AT, High16Bits(offset));
+      Lwu(lhs, AT, Low16Bits(offset));
+      break;
+    case Branch::kFarLiteralLong:
+      offset += (offset & 0x8000) << 1;  // Account for sign extension in ld.
+      CHECK_EQ(overwrite_location_, branch->GetOffsetLocation());
+      Auipc(AT, High16Bits(offset));
+      Ld(lhs, AT, Low16Bits(offset));
       break;
   }
   CHECK_EQ(overwrite_location_, branch->GetEndLocation());
@@ -1631,8 +1862,8 @@
   Buncond(label);
 }
 
-void Mips64Assembler::Jialc(Mips64Label* label, GpuRegister indirect_reg) {
-  Call(label, indirect_reg);
+void Mips64Assembler::Balc(Mips64Label* label) {
+  Call(label);
 }
 
 void Mips64Assembler::Bltc(GpuRegister rs, GpuRegister rt, Mips64Label* label) {
diff --git a/compiler/utils/mips64/assembler_mips64.h b/compiler/utils/mips64/assembler_mips64.h
index 238cb9d..08a55ed 100644
--- a/compiler/utils/mips64/assembler_mips64.h
+++ b/compiler/utils/mips64/assembler_mips64.h
@@ -17,9 +17,11 @@
 #ifndef ART_COMPILER_UTILS_MIPS64_ASSEMBLER_MIPS64_H_
 #define ART_COMPILER_UTILS_MIPS64_ASSEMBLER_MIPS64_H_
 
+#include <deque>
 #include <utility>
 #include <vector>
 
+#include "base/arena_containers.h"
 #include "base/enums.h"
 #include "base/macros.h"
 #include "constants_mips64.h"
@@ -312,6 +314,49 @@
   DISALLOW_COPY_AND_ASSIGN(Mips64Label);
 };
 
+// Assembler literal is a value embedded in code, retrieved using a PC-relative load.
+class Literal {
+ public:
+  static constexpr size_t kMaxSize = 8;
+
+  Literal(uint32_t size, const uint8_t* data)
+      : label_(), size_(size) {
+    DCHECK_LE(size, Literal::kMaxSize);
+    memcpy(data_, data, size);
+  }
+
+  template <typename T>
+  T GetValue() const {
+    DCHECK_EQ(size_, sizeof(T));
+    T value;
+    memcpy(&value, data_, sizeof(T));
+    return value;
+  }
+
+  uint32_t GetSize() const {
+    return size_;
+  }
+
+  const uint8_t* GetData() const {
+    return data_;
+  }
+
+  Mips64Label* GetLabel() {
+    return &label_;
+  }
+
+  const Mips64Label* GetLabel() const {
+    return &label_;
+  }
+
+ private:
+  Mips64Label label_;
+  const uint32_t size_;
+  uint8_t data_[kMaxSize];
+
+  DISALLOW_COPY_AND_ASSIGN(Literal);
+};
+
 // Slowpath entered when Thread::Current()->_exception is non-null.
 class Mips64ExceptionSlowPath {
  public:
@@ -341,6 +386,8 @@
       : Assembler(arena),
         overwriting_(false),
         overwrite_location_(0),
+        literals_(arena->Adapter(kArenaAllocAssembler)),
+        long_literals_(arena->Adapter(kArenaAllocAssembler)),
         last_position_adjustment_(0),
         last_old_position_(0),
         last_branch_id_(0) {
@@ -386,18 +433,18 @@
   void Nor(GpuRegister rd, GpuRegister rs, GpuRegister rt);
 
   void Bitswap(GpuRegister rd, GpuRegister rt);
-  void Dbitswap(GpuRegister rd, GpuRegister rt);
+  void Dbitswap(GpuRegister rd, GpuRegister rt);  // MIPS64
   void Seb(GpuRegister rd, GpuRegister rt);
   void Seh(GpuRegister rd, GpuRegister rt);
-  void Dsbh(GpuRegister rd, GpuRegister rt);
-  void Dshd(GpuRegister rd, GpuRegister rt);
+  void Dsbh(GpuRegister rd, GpuRegister rt);  // MIPS64
+  void Dshd(GpuRegister rd, GpuRegister rt);  // MIPS64
   void Dext(GpuRegister rs, GpuRegister rt, int pos, int size);  // MIPS64
   void Dinsu(GpuRegister rt, GpuRegister rs, int pos, int size);  // MIPS64
   void Wsbh(GpuRegister rd, GpuRegister rt);
   void Sc(GpuRegister rt, GpuRegister base, int16_t imm9 = 0);
-  void Scd(GpuRegister rt, GpuRegister base, int16_t imm9 = 0);
+  void Scd(GpuRegister rt, GpuRegister base, int16_t imm9 = 0);  // MIPS64
   void Ll(GpuRegister rt, GpuRegister base, int16_t imm9 = 0);
-  void Lld(GpuRegister rt, GpuRegister base, int16_t imm9 = 0);
+  void Lld(GpuRegister rt, GpuRegister base, int16_t imm9 = 0);  // MIPS64
 
   void Sll(GpuRegister rd, GpuRegister rt, int shamt);
   void Srl(GpuRegister rd, GpuRegister rt, int shamt);
@@ -409,7 +456,7 @@
   void Srav(GpuRegister rd, GpuRegister rt, GpuRegister rs);
   void Dsll(GpuRegister rd, GpuRegister rt, int shamt);  // MIPS64
   void Dsrl(GpuRegister rd, GpuRegister rt, int shamt);  // MIPS64
-  void Drotr(GpuRegister rd, GpuRegister rt, int shamt);
+  void Drotr(GpuRegister rd, GpuRegister rt, int shamt);  // MIPS64
   void Dsra(GpuRegister rd, GpuRegister rt, int shamt);  // MIPS64
   void Dsll32(GpuRegister rd, GpuRegister rt, int shamt);  // MIPS64
   void Dsrl32(GpuRegister rd, GpuRegister rt, int shamt);  // MIPS64
@@ -427,6 +474,9 @@
   void Lbu(GpuRegister rt, GpuRegister rs, uint16_t imm16);
   void Lhu(GpuRegister rt, GpuRegister rs, uint16_t imm16);
   void Lwu(GpuRegister rt, GpuRegister rs, uint16_t imm16);  // MIPS64
+  void Lwpc(GpuRegister rs, uint32_t imm19);
+  void Lwupc(GpuRegister rs, uint32_t imm19);  // MIPS64
+  void Ldpc(GpuRegister rs, uint32_t imm18);  // MIPS64
   void Lui(GpuRegister rt, uint16_t imm16);
   void Dahi(GpuRegister rs, uint16_t imm16);  // MIPS64
   void Dati(GpuRegister rs, uint16_t imm16);  // MIPS64
@@ -445,8 +495,8 @@
   void Selnez(GpuRegister rd, GpuRegister rs, GpuRegister rt);
   void Clz(GpuRegister rd, GpuRegister rs);
   void Clo(GpuRegister rd, GpuRegister rs);
-  void Dclz(GpuRegister rd, GpuRegister rs);
-  void Dclo(GpuRegister rd, GpuRegister rs);
+  void Dclz(GpuRegister rd, GpuRegister rs);  // MIPS64
+  void Dclo(GpuRegister rd, GpuRegister rs);  // MIPS64
 
   void Jalr(GpuRegister rd, GpuRegister rs);
   void Jalr(GpuRegister rs);
@@ -454,6 +504,7 @@
   void Auipc(GpuRegister rs, uint16_t imm16);
   void Addiupc(GpuRegister rs, uint32_t imm19);
   void Bc(uint32_t imm26);
+  void Balc(uint32_t imm26);
   void Jic(GpuRegister rt, uint16_t imm16);
   void Jialc(GpuRegister rt, uint16_t imm16);
   void Bltc(GpuRegister rs, GpuRegister rt, uint16_t imm16);
@@ -605,8 +656,26 @@
     UNREACHABLE();
   }
 
+  // Create a new literal with a given value.
+  // NOTE: Force the template parameter to be explicitly specified.
+  template <typename T>
+  Literal* NewLiteral(typename Identity<T>::type value) {
+    static_assert(std::is_integral<T>::value, "T must be an integral type.");
+    return NewLiteral(sizeof(value), reinterpret_cast<const uint8_t*>(&value));
+  }
+
+  // Load label address using PC-relative loads. To be used with data labels in the literal /
+  // jump table area only and not with regular code labels.
+  void LoadLabelAddress(GpuRegister dest_reg, Mips64Label* label);
+
+  // Create a new literal with the given data.
+  Literal* NewLiteral(size_t size, const uint8_t* data);
+
+  // Load literal using PC-relative loads.
+  void LoadLiteral(GpuRegister dest_reg, LoadOperandType load_type, Literal* literal);
+
   void Bc(Mips64Label* label);
-  void Jialc(Mips64Label* label, GpuRegister indirect_reg);
+  void Balc(Mips64Label* label);
   void Bltc(GpuRegister rs, GpuRegister rt, Mips64Label* label);
   void Bltzc(GpuRegister rt, Mips64Label* label);
   void Bgtzc(GpuRegister rt, Mips64Label* label);
@@ -756,12 +825,15 @@
 
   // Returns the (always-)current location of a label (can be used in class CodeGeneratorMIPS64,
   // must be used instead of Mips64Label::GetPosition()).
-  uint32_t GetLabelLocation(Mips64Label* label) const;
+  uint32_t GetLabelLocation(const Mips64Label* label) const;
 
   // Get the final position of a label after local fixup based on the old position
   // recorded before FinalizeCode().
   uint32_t GetAdjustedPosition(uint32_t old_position);
 
+  // Note that PC-relative literal loads are handled as pseudo branches because they need very
+  // similar relocation and may similarly expand in size to accomodate for larger offsets relative
+  // to PC.
   enum BranchCondition {
     kCondLT,
     kCondGE,
@@ -791,10 +863,22 @@
       kUncondBranch,
       kCondBranch,
       kCall,
+      // Near label.
+      kLabel,
+      // Near literals.
+      kLiteral,
+      kLiteralUnsigned,
+      kLiteralLong,
       // Long branches.
       kLongUncondBranch,
       kLongCondBranch,
       kLongCall,
+      // Far label.
+      kFarLabel,
+      // Far literals.
+      kFarLiteral,
+      kFarLiteralUnsigned,
+      kFarLiteralLong,
     };
 
     // Bit sizes of offsets defined as enums to minimize chance of typos.
@@ -830,16 +914,16 @@
     };
     static const BranchInfo branch_info_[/* Type */];
 
-    // Unconditional branch.
-    Branch(uint32_t location, uint32_t target);
+    // Unconditional branch or call.
+    Branch(uint32_t location, uint32_t target, bool is_call);
     // Conditional branch.
     Branch(uint32_t location,
            uint32_t target,
            BranchCondition condition,
            GpuRegister lhs_reg,
-           GpuRegister rhs_reg = ZERO);
-    // Call (branch and link) that stores the target address in a given register (i.e. T9).
-    Branch(uint32_t location, uint32_t target, GpuRegister indirect_reg);
+           GpuRegister rhs_reg);
+    // Label address (in literal area) or literal.
+    Branch(uint32_t location, GpuRegister dest_reg, Type label_or_literal_type);
 
     // Some conditional branches with lhs = rhs are effectively NOPs, while some
     // others are effectively unconditional. MIPSR6 conditional branches require lhs != rhs.
@@ -923,7 +1007,7 @@
 
    private:
     // Completes branch construction by determining and recording its type.
-    void InitializeType(bool is_call);
+    void InitializeType(Type initial_type);
     // Helper for the above.
     void InitShortOrLong(OffsetBits ofs_size, Type short_type, Type long_type);
 
@@ -932,7 +1016,7 @@
     uint32_t target_;            // Offset into assembler buffer in bytes.
 
     GpuRegister lhs_reg_;        // Left-hand side register in conditional branches or
-                                 // indirect call register.
+                                 // destination register in literals.
     GpuRegister rhs_reg_;        // Right-hand side register in conditional branches.
     BranchCondition condition_;  // Condition for conditional branches.
 
@@ -957,12 +1041,13 @@
              BranchCondition condition,
              GpuRegister lhs,
              GpuRegister rhs = ZERO);
-  void Call(Mips64Label* label, GpuRegister indirect_reg);
+  void Call(Mips64Label* label);
   void FinalizeLabeledBranch(Mips64Label* label);
 
   Branch* GetBranch(uint32_t branch_id);
   const Branch* GetBranch(uint32_t branch_id) const;
 
+  void EmitLiterals();
   void PromoteBranches();
   void EmitBranch(Branch* branch);
   void EmitBranches();
@@ -981,6 +1066,11 @@
   // The current overwrite location.
   uint32_t overwrite_location_;
 
+  // Use std::deque<> for literal labels to allow insertions at the end
+  // without invalidating pointers and references to existing elements.
+  ArenaDeque<Literal> literals_;
+  ArenaDeque<Literal> long_literals_;  // 64-bit literals separated for alignment reasons.
+
   // Data for AdjustedPosition(), see the description there.
   uint32_t last_position_adjustment_;
   uint32_t last_old_position_;
diff --git a/compiler/utils/mips64/assembler_mips64_test.cc b/compiler/utils/mips64/assembler_mips64_test.cc
index ba8f25e..31d3e4c 100644
--- a/compiler/utils/mips64/assembler_mips64_test.cc
+++ b/compiler/utils/mips64/assembler_mips64_test.cc
@@ -576,83 +576,80 @@
             RepeatRRNoDupes(&mips64::Mips64Assembler::Jalr, "jalr ${reg1}, ${reg2}"), "jalr");
 }
 
-TEST_F(AssemblerMIPS64Test, Jialc) {
+TEST_F(AssemblerMIPS64Test, Balc) {
   mips64::Mips64Label label1, label2;
-  __ Jialc(&label1, mips64::T9);
+  __ Balc(&label1);
   constexpr size_t kAdduCount1 = 63;
   for (size_t i = 0; i != kAdduCount1; ++i) {
     __ Addu(mips64::ZERO, mips64::ZERO, mips64::ZERO);
   }
   __ Bind(&label1);
-  __ Jialc(&label2, mips64::T9);
+  __ Balc(&label2);
   constexpr size_t kAdduCount2 = 64;
   for (size_t i = 0; i != kAdduCount2; ++i) {
     __ Addu(mips64::ZERO, mips64::ZERO, mips64::ZERO);
   }
   __ Bind(&label2);
-  __ Jialc(&label1, mips64::T9);
+  __ Balc(&label1);
 
   std::string expected =
       ".set noreorder\n"
-      "lapc $t9, 1f\n"
-      "jialc $t9, 0\n" +
+      "balc 1f\n" +
       RepeatInsn(kAdduCount1, "addu $zero, $zero, $zero\n") +
       "1:\n"
-      "lapc $t9, 2f\n"
-      "jialc $t9, 0\n" +
+      "balc 2f\n" +
       RepeatInsn(kAdduCount2, "addu $zero, $zero, $zero\n") +
       "2:\n"
-      "lapc $t9, 1b\n"
-      "jialc $t9, 0\n";
-  DriverStr(expected, "Jialc");
+      "balc 1b\n";
+  DriverStr(expected, "Balc");
 }
 
-TEST_F(AssemblerMIPS64Test, LongJialc) {
+TEST_F(AssemblerMIPS64Test, LongBalc) {
   mips64::Mips64Label label1, label2;
-  __ Jialc(&label1, mips64::T9);
-  constexpr uint32_t kAdduCount1 = (1u << 18) + 1;
-  for (uint32_t i = 0; i != kAdduCount1; ++i) {
-    __ Addu(mips64::ZERO, mips64::ZERO, mips64::ZERO);
+  __ Balc(&label1);
+  constexpr uint32_t kNopCount1 = (1u << 25) + 1;
+  for (uint32_t i = 0; i != kNopCount1; ++i) {
+    __ Nop();
   }
   __ Bind(&label1);
-  __ Jialc(&label2, mips64::T9);
-  constexpr uint32_t kAdduCount2 = (1u << 18) + 1;
-  for (uint32_t i = 0; i != kAdduCount2; ++i) {
-    __ Addu(mips64::ZERO, mips64::ZERO, mips64::ZERO);
+  __ Balc(&label2);
+  constexpr uint32_t kNopCount2 = (1u << 25) + 1;
+  for (uint32_t i = 0; i != kNopCount2; ++i) {
+    __ Nop();
   }
   __ Bind(&label2);
-  __ Jialc(&label1, mips64::T9);
+  __ Balc(&label1);
 
-  uint32_t offset_forward1 = 3 + kAdduCount1;  // 3: account for auipc, daddiu and jic.
+  uint32_t offset_forward1 = 2 + kNopCount1;  // 2: account for auipc and jialc.
   offset_forward1 <<= 2;
-  offset_forward1 += (offset_forward1 & 0x8000) << 1;  // Account for sign extension in daddiu.
+  offset_forward1 += (offset_forward1 & 0x8000) << 1;  // Account for sign extension in jialc.
 
-  uint32_t offset_forward2 = 3 + kAdduCount2;  // 3: account for auipc, daddiu and jic.
+  uint32_t offset_forward2 = 2 + kNopCount2;  // 2: account for auipc and jialc.
   offset_forward2 <<= 2;
-  offset_forward2 += (offset_forward2 & 0x8000) << 1;  // Account for sign extension in daddiu.
+  offset_forward2 += (offset_forward2 & 0x8000) << 1;  // Account for sign extension in jialc.
 
-  uint32_t offset_back = -(3 + kAdduCount2);  // 3: account for auipc, daddiu and jic.
+  uint32_t offset_back = -(2 + kNopCount2);  // 2: account for auipc and jialc.
   offset_back <<= 2;
-  offset_back += (offset_back & 0x8000) << 1;  // Account for sign extension in daddiu.
+  offset_back += (offset_back & 0x8000) << 1;  // Account for sign extension in jialc.
 
+  // Note, we're using the ".fill" directive to tell the assembler to generate many NOPs
+  // instead of generating them ourselves in the source code. This saves a few minutes
+  // of test time.
   std::ostringstream oss;
   oss <<
       ".set noreorder\n"
-      "auipc $t9, 0x" << std::hex << High16Bits(offset_forward1) << "\n"
-      "daddiu $t9, 0x" << std::hex << Low16Bits(offset_forward1) << "\n"
-      "jialc $t9, 0\n" <<
-      RepeatInsn(kAdduCount1, "addu $zero, $zero, $zero\n") <<
+      "auipc $at, 0x" << std::hex << High16Bits(offset_forward1) << "\n"
+      "jialc $at, 0x" << std::hex << Low16Bits(offset_forward1) << "\n"
+      ".fill 0x" << std::hex << kNopCount1 << " , 4, 0\n"
       "1:\n"
-      "auipc $t9, 0x" << std::hex << High16Bits(offset_forward2) << "\n"
-      "daddiu $t9, 0x" << std::hex << Low16Bits(offset_forward2) << "\n"
-      "jialc $t9, 0\n" <<
-      RepeatInsn(kAdduCount2, "addu $zero, $zero, $zero\n") <<
+      "auipc $at, 0x" << std::hex << High16Bits(offset_forward2) << "\n"
+      "jialc $at, 0x" << std::hex << Low16Bits(offset_forward2) << "\n"
+      ".fill 0x" << std::hex << kNopCount2 << " , 4, 0\n"
       "2:\n"
-      "auipc $t9, 0x" << std::hex << High16Bits(offset_back) << "\n"
-      "daddiu $t9, 0x" << std::hex << Low16Bits(offset_back) << "\n"
-      "jialc $t9, 0\n";
+      "auipc $at, 0x" << std::hex << High16Bits(offset_back) << "\n"
+      "jialc $at, 0x" << std::hex << Low16Bits(offset_back) << "\n";
   std::string expected = oss.str();
-  DriverStr(expected, "LongJialc");
+  DriverStr(expected, "LongBalc");
 }
 
 TEST_F(AssemblerMIPS64Test, Bc) {
@@ -827,6 +824,258 @@
 // MISC //
 //////////
 
+TEST_F(AssemblerMIPS64Test, Lwpc) {
+  // Lwpc() takes an unsigned 19-bit immediate, while the GNU assembler needs a signed offset,
+  // hence the sign extension from bit 18 with `imm - ((imm & 0x40000) << 1)`.
+  // The GNU assembler also wants the offset to be a multiple of 4, which it will shift right
+  // by 2 positions when encoding, hence `<< 2` to compensate for that shift.
+  // We capture the value of the immediate with `.set imm, {imm}` because the value is needed
+  // twice for the sign extension, but `{imm}` is substituted only once.
+  const char* code = ".set imm, {imm}\nlw ${reg}, ((imm - ((imm & 0x40000) << 1)) << 2)($pc)";
+  DriverStr(RepeatRIb(&mips64::Mips64Assembler::Lwpc, 19, code), "Lwpc");
+}
+
+TEST_F(AssemblerMIPS64Test, Lwupc) {
+  // The comment for the Lwpc test applies here as well.
+  const char* code = ".set imm, {imm}\nlwu ${reg}, ((imm - ((imm & 0x40000) << 1)) << 2)($pc)";
+  DriverStr(RepeatRIb(&mips64::Mips64Assembler::Lwupc, 19, code), "Lwupc");
+}
+
+TEST_F(AssemblerMIPS64Test, Ldpc) {
+  // The comment for the Lwpc test applies here as well.
+  const char* code = ".set imm, {imm}\nld ${reg}, ((imm - ((imm & 0x20000) << 1)) << 3)($pc)";
+  DriverStr(RepeatRIb(&mips64::Mips64Assembler::Ldpc, 18, code), "Ldpc");
+}
+
+TEST_F(AssemblerMIPS64Test, LoadFarthestNearLabelAddress) {
+  mips64::Mips64Label label;
+  __ LoadLabelAddress(mips64::V0, &label);
+  constexpr uint32_t kAdduCount = 0x3FFDE;
+  for (uint32_t i = 0; i != kAdduCount; ++i) {
+    __ Addu(mips64::ZERO, mips64::ZERO, mips64::ZERO);
+  }
+  __ Bind(&label);
+
+  std::string expected =
+      "lapc $v0, 1f\n" +
+      RepeatInsn(kAdduCount, "addu $zero, $zero, $zero\n") +
+      "1:\n";
+  DriverStr(expected, "LoadFarthestNearLabelAddress");
+  EXPECT_EQ(__ GetLabelLocation(&label), (1 + kAdduCount) * 4);
+}
+
+TEST_F(AssemblerMIPS64Test, LoadNearestFarLabelAddress) {
+  mips64::Mips64Label label;
+  __ LoadLabelAddress(mips64::V0, &label);
+  constexpr uint32_t kAdduCount = 0x3FFDF;
+  for (uint32_t i = 0; i != kAdduCount; ++i) {
+    __ Addu(mips64::ZERO, mips64::ZERO, mips64::ZERO);
+  }
+  __ Bind(&label);
+
+  std::string expected =
+      "1:\n"
+      "auipc $at, %hi(2f - 1b)\n"
+      "addiu $v0, $at, %lo(2f - 1b)\n" +
+      RepeatInsn(kAdduCount, "addu $zero, $zero, $zero\n") +
+      "2:\n";
+  DriverStr(expected, "LoadNearestFarLabelAddress");
+  EXPECT_EQ(__ GetLabelLocation(&label), (2 + kAdduCount) * 4);
+}
+
+TEST_F(AssemblerMIPS64Test, LoadFarthestNearLiteral) {
+  mips64::Literal* literal = __ NewLiteral<uint32_t>(0x12345678);
+  __ LoadLiteral(mips64::V0, mips64::kLoadWord, literal);
+  constexpr uint32_t kAdduCount = 0x3FFDE;
+  for (uint32_t i = 0; i != kAdduCount; ++i) {
+    __ Addu(mips64::ZERO, mips64::ZERO, mips64::ZERO);
+  }
+
+  std::string expected =
+      "lwpc $v0, 1f\n" +
+      RepeatInsn(kAdduCount, "addu $zero, $zero, $zero\n") +
+      "1:\n"
+      ".word 0x12345678\n";
+  DriverStr(expected, "LoadFarthestNearLiteral");
+  EXPECT_EQ(__ GetLabelLocation(literal->GetLabel()), (1 + kAdduCount) * 4);
+}
+
+TEST_F(AssemblerMIPS64Test, LoadNearestFarLiteral) {
+  mips64::Literal* literal = __ NewLiteral<uint32_t>(0x12345678);
+  __ LoadLiteral(mips64::V0, mips64::kLoadWord, literal);
+  constexpr uint32_t kAdduCount = 0x3FFDF;
+  for (uint32_t i = 0; i != kAdduCount; ++i) {
+    __ Addu(mips64::ZERO, mips64::ZERO, mips64::ZERO);
+  }
+
+  std::string expected =
+      "1:\n"
+      "auipc $at, %hi(2f - 1b)\n"
+      "lw $v0, %lo(2f - 1b)($at)\n" +
+      RepeatInsn(kAdduCount, "addu $zero, $zero, $zero\n") +
+      "2:\n"
+      ".word 0x12345678\n";
+  DriverStr(expected, "LoadNearestFarLiteral");
+  EXPECT_EQ(__ GetLabelLocation(literal->GetLabel()), (2 + kAdduCount) * 4);
+}
+
+TEST_F(AssemblerMIPS64Test, LoadFarthestNearLiteralUnsigned) {
+  mips64::Literal* literal = __ NewLiteral<uint32_t>(0x12345678);
+  __ LoadLiteral(mips64::V0, mips64::kLoadUnsignedWord, literal);
+  constexpr uint32_t kAdduCount = 0x3FFDE;
+  for (uint32_t i = 0; i != kAdduCount; ++i) {
+    __ Addu(mips64::ZERO, mips64::ZERO, mips64::ZERO);
+  }
+
+  std::string expected =
+      "lwupc $v0, 1f\n" +
+      RepeatInsn(kAdduCount, "addu $zero, $zero, $zero\n") +
+      "1:\n"
+      ".word 0x12345678\n";
+  DriverStr(expected, "LoadFarthestNearLiteralUnsigned");
+  EXPECT_EQ(__ GetLabelLocation(literal->GetLabel()), (1 + kAdduCount) * 4);
+}
+
+TEST_F(AssemblerMIPS64Test, LoadNearestFarLiteralUnsigned) {
+  mips64::Literal* literal = __ NewLiteral<uint32_t>(0x12345678);
+  __ LoadLiteral(mips64::V0, mips64::kLoadUnsignedWord, literal);
+  constexpr uint32_t kAdduCount = 0x3FFDF;
+  for (uint32_t i = 0; i != kAdduCount; ++i) {
+    __ Addu(mips64::ZERO, mips64::ZERO, mips64::ZERO);
+  }
+
+  std::string expected =
+      "1:\n"
+      "auipc $at, %hi(2f - 1b)\n"
+      "lwu $v0, %lo(2f - 1b)($at)\n" +
+      RepeatInsn(kAdduCount, "addu $zero, $zero, $zero\n") +
+      "2:\n"
+      ".word 0x12345678\n";
+  DriverStr(expected, "LoadNearestFarLiteralUnsigned");
+  EXPECT_EQ(__ GetLabelLocation(literal->GetLabel()), (2 + kAdduCount) * 4);
+}
+
+TEST_F(AssemblerMIPS64Test, LoadFarthestNearLiteralLong) {
+  mips64::Literal* literal = __ NewLiteral<uint64_t>(UINT64_C(0x0123456789ABCDEF));
+  __ LoadLiteral(mips64::V0, mips64::kLoadDoubleword, literal);
+  constexpr uint32_t kAdduCount = 0x3FFDD;
+  for (uint32_t i = 0; i != kAdduCount; ++i) {
+    __ Addu(mips64::ZERO, mips64::ZERO, mips64::ZERO);
+  }
+
+  std::string expected =
+      "ldpc $v0, 1f\n" +
+      RepeatInsn(kAdduCount, "addu $zero, $zero, $zero\n") +
+      "1:\n"
+      ".dword 0x0123456789ABCDEF\n";
+  DriverStr(expected, "LoadFarthestNearLiteralLong");
+  EXPECT_EQ(__ GetLabelLocation(literal->GetLabel()), (1 + kAdduCount) * 4);
+}
+
+TEST_F(AssemblerMIPS64Test, LoadNearestFarLiteralLong) {
+  mips64::Literal* literal = __ NewLiteral<uint64_t>(UINT64_C(0x0123456789ABCDEF));
+  __ LoadLiteral(mips64::V0, mips64::kLoadDoubleword, literal);
+  constexpr uint32_t kAdduCount = 0x3FFDE;
+  for (uint32_t i = 0; i != kAdduCount; ++i) {
+    __ Addu(mips64::ZERO, mips64::ZERO, mips64::ZERO);
+  }
+
+  std::string expected =
+      "1:\n"
+      "auipc $at, %hi(2f - 1b)\n"
+      "ld $v0, %lo(2f - 1b)($at)\n" +
+      RepeatInsn(kAdduCount, "addu $zero, $zero, $zero\n") +
+      "2:\n"
+      ".dword 0x0123456789ABCDEF\n";
+  DriverStr(expected, "LoadNearestFarLiteralLong");
+  EXPECT_EQ(__ GetLabelLocation(literal->GetLabel()), (2 + kAdduCount) * 4);
+}
+
+TEST_F(AssemblerMIPS64Test, LongLiteralAlignmentNop) {
+  mips64::Literal* literal1 = __ NewLiteral<uint64_t>(UINT64_C(0x0123456789ABCDEF));
+  mips64::Literal* literal2 = __ NewLiteral<uint64_t>(UINT64_C(0x5555555555555555));
+  mips64::Literal* literal3 = __ NewLiteral<uint64_t>(UINT64_C(0xAAAAAAAAAAAAAAAA));
+  __ LoadLiteral(mips64::A1, mips64::kLoadDoubleword, literal1);
+  __ LoadLiteral(mips64::A2, mips64::kLoadDoubleword, literal2);
+  __ LoadLiteral(mips64::A3, mips64::kLoadDoubleword, literal3);
+  __ LoadLabelAddress(mips64::V0, literal1->GetLabel());
+  __ LoadLabelAddress(mips64::V1, literal2->GetLabel());
+  // A nop will be inserted here before the 64-bit literals.
+
+  std::string expected =
+      "ldpc $a1, 1f\n"
+      // The GNU assembler incorrectly requires the ldpc instruction to be located
+      // at an address that's a multiple of 8. TODO: Remove this workaround if/when
+      // the assembler is fixed.
+      // "ldpc $a2, 2f\n"
+      ".word 0xECD80004\n"
+      "ldpc $a3, 3f\n"
+      "lapc $v0, 1f\n"
+      "lapc $v1, 2f\n"
+      "nop\n"
+      "1:\n"
+      ".dword 0x0123456789ABCDEF\n"
+      "2:\n"
+      ".dword 0x5555555555555555\n"
+      "3:\n"
+      ".dword 0xAAAAAAAAAAAAAAAA\n";
+  DriverStr(expected, "LongLiteralAlignmentNop");
+  EXPECT_EQ(__ GetLabelLocation(literal1->GetLabel()), 6 * 4u);
+  EXPECT_EQ(__ GetLabelLocation(literal2->GetLabel()), 8 * 4u);
+  EXPECT_EQ(__ GetLabelLocation(literal3->GetLabel()), 10 * 4u);
+}
+
+TEST_F(AssemblerMIPS64Test, LongLiteralAlignmentNoNop) {
+  mips64::Literal* literal1 = __ NewLiteral<uint64_t>(UINT64_C(0x0123456789ABCDEF));
+  mips64::Literal* literal2 = __ NewLiteral<uint64_t>(UINT64_C(0x5555555555555555));
+  __ LoadLiteral(mips64::A1, mips64::kLoadDoubleword, literal1);
+  __ LoadLiteral(mips64::A2, mips64::kLoadDoubleword, literal2);
+  __ LoadLabelAddress(mips64::V0, literal1->GetLabel());
+  __ LoadLabelAddress(mips64::V1, literal2->GetLabel());
+
+  std::string expected =
+      "ldpc $a1, 1f\n"
+      // The GNU assembler incorrectly requires the ldpc instruction to be located
+      // at an address that's a multiple of 8. TODO: Remove this workaround if/when
+      // the assembler is fixed.
+      // "ldpc $a2, 2f\n"
+      ".word 0xECD80003\n"
+      "lapc $v0, 1f\n"
+      "lapc $v1, 2f\n"
+      "1:\n"
+      ".dword 0x0123456789ABCDEF\n"
+      "2:\n"
+      ".dword 0x5555555555555555\n";
+  DriverStr(expected, "LongLiteralAlignmentNoNop");
+  EXPECT_EQ(__ GetLabelLocation(literal1->GetLabel()), 4 * 4u);
+  EXPECT_EQ(__ GetLabelLocation(literal2->GetLabel()), 6 * 4u);
+}
+
+TEST_F(AssemblerMIPS64Test, FarLongLiteralAlignmentNop) {
+  mips64::Literal* literal = __ NewLiteral<uint64_t>(UINT64_C(0x0123456789ABCDEF));
+  __ LoadLiteral(mips64::V0, mips64::kLoadDoubleword, literal);
+  __ LoadLabelAddress(mips64::V1, literal->GetLabel());
+  constexpr uint32_t kAdduCount = 0x3FFDF;
+  for (uint32_t i = 0; i != kAdduCount; ++i) {
+    __ Addu(mips64::ZERO, mips64::ZERO, mips64::ZERO);
+  }
+  // A nop will be inserted here before the 64-bit literal.
+
+  std::string expected =
+      "1:\n"
+      "auipc $at, %hi(3f - 1b)\n"
+      "ld $v0, %lo(3f - 1b)($at)\n"
+      "2:\n"
+      "auipc $at, %hi(3f - 2b)\n"
+      "addiu $v1, $at, %lo(3f - 2b)\n" +
+      RepeatInsn(kAdduCount, "addu $zero, $zero, $zero\n") +
+      "nop\n"
+      "3:\n"
+      ".dword 0x0123456789ABCDEF\n";
+  DriverStr(expected, "FarLongLiteralAlignmentNop");
+  EXPECT_EQ(__ GetLabelLocation(literal->GetLabel()), (5 + kAdduCount) * 4);
+}
+
 TEST_F(AssemblerMIPS64Test, Bitswap) {
   DriverStr(RepeatRR(&mips64::Mips64Assembler::Bitswap, "bitswap ${reg1}, ${reg2}"), "bitswap");
 }
diff --git a/dex2oat/dex2oat.cc b/dex2oat/dex2oat.cc
index 8fb4040..5a0f0c6 100644
--- a/dex2oat/dex2oat.cc
+++ b/dex2oat/dex2oat.cc
@@ -33,6 +33,8 @@
 #include <sys/utsname.h>
 #endif
 
+#include "android-base/strings.h"
+
 #include "arch/instruction_set_features.h"
 #include "arch/mips/instruction_set_features_mips.h"
 #include "art_method-inl.h"
@@ -96,7 +98,7 @@
   for (int i = 0; i < original_argc; ++i) {
     command.push_back(original_argv[i]);
   }
-  return Join(command, ' ');
+  return android::base::Join(command, ' ');
 }
 
 // A stripped version. Remove some less essential parameters. If we see a "--zip-fd=" parameter, be
@@ -108,7 +110,7 @@
   // Do a pre-pass to look for zip-fd.
   bool saw_zip_fd = false;
   for (int i = 0; i < original_argc; ++i) {
-    if (StartsWith(original_argv[i], "--zip-fd=")) {
+    if (android::base::StartsWith(original_argv[i], "--zip-fd=")) {
       saw_zip_fd = true;
       break;
     }
@@ -123,17 +125,17 @@
     }
 
     // Any instruction-setXXX is dropped.
-    if (StartsWith(original_argv[i], "--instruction-set")) {
+    if (android::base::StartsWith(original_argv[i], "--instruction-set")) {
       continue;
     }
 
     // The boot image is dropped.
-    if (StartsWith(original_argv[i], "--boot-image=")) {
+    if (android::base::StartsWith(original_argv[i], "--boot-image=")) {
       continue;
     }
 
     // The image format is dropped.
-    if (StartsWith(original_argv[i], "--image-format=")) {
+    if (android::base::StartsWith(original_argv[i], "--image-format=")) {
       continue;
     }
 
@@ -142,11 +144,11 @@
     // However, we prefer to drop this when we saw --zip-fd.
     if (saw_zip_fd) {
       // Drop anything --zip-X, --dex-X, --oat-X, --swap-X, or --app-image-X
-      if (StartsWith(original_argv[i], "--zip-") ||
-          StartsWith(original_argv[i], "--dex-") ||
-          StartsWith(original_argv[i], "--oat-") ||
-          StartsWith(original_argv[i], "--swap-") ||
-          StartsWith(original_argv[i], "--app-image-")) {
+      if (android::base::StartsWith(original_argv[i], "--zip-") ||
+          android::base::StartsWith(original_argv[i], "--dex-") ||
+          android::base::StartsWith(original_argv[i], "--oat-") ||
+          android::base::StartsWith(original_argv[i], "--swap-") ||
+          android::base::StartsWith(original_argv[i], "--app-image-")) {
         continue;
       }
     }
@@ -159,7 +161,7 @@
     // It seems only "/system/bin/dex2oat" is left, or not even that. Use a pretty line.
     return "Starting dex2oat.";
   }
-  return Join(command, ' ');
+  return android::base::Join(command, ' ');
 }
 
 static void UsageErrorV(const char* fmt, va_list ap) {
@@ -999,7 +1001,7 @@
       if (last_dex_dot != std::string::npos) {
         dex_file = dex_file.substr(0, last_dex_dot);
       }
-      if (StartsWith(dex_file, "core-")) {
+      if (android::base::StartsWith(dex_file, "core-")) {
         infix = dex_file.substr(strlen("core"));
       }
     }
@@ -1059,7 +1061,7 @@
         in.insert(last_dot, infix);
       }
     }
-    if (EndsWith(in, ".jar")) {
+    if (android::base::EndsWith(in, ".jar")) {
       in = in.substr(0, in.length() - strlen(".jar")) +
           (replace_suffix != nullptr ? replace_suffix : "");
     }
@@ -1484,7 +1486,7 @@
         for (const gc::space::ImageSpace* image_space : image_spaces) {
           image_filenames.push_back(image_space->GetImageFilename());
         }
-        std::string image_file_location = Join(image_filenames, ':');
+        std::string image_file_location = android::base::Join(image_filenames, ':');
         if (!image_file_location.empty()) {
           key_value_store_->Put(OatHeader::kImageLocationKey, image_file_location);
         }
@@ -1687,7 +1689,7 @@
               }
             }
 
-            if (StartsWith(dex_location, filter.c_str())) {
+            if (android::base::StartsWith(dex_location, filter.c_str())) {
               VLOG(compiler) << "Disabling inlining from " << dex_file->GetLocation();
               no_inline_from_dex_files_.push_back(dex_file);
               break;
@@ -2362,10 +2364,10 @@
     RuntimeOptions raw_options;
     if (boot_image_filename_.empty()) {
       std::string boot_class_path = "-Xbootclasspath:";
-      boot_class_path += Join(dex_filenames_, ':');
+      boot_class_path += android::base::Join(dex_filenames_, ':');
       raw_options.push_back(std::make_pair(boot_class_path, nullptr));
       std::string boot_class_path_locations = "-Xbootclasspath-locations:";
-      boot_class_path_locations += Join(dex_locations_, ':');
+      boot_class_path_locations += android::base::Join(dex_locations_, ':');
       raw_options.push_back(std::make_pair(boot_class_path_locations, nullptr));
     } else {
       std::string boot_image_option = "-Ximage:";
@@ -2579,7 +2581,7 @@
     while (in_stream.good()) {
       std::string dot;
       std::getline(in_stream, dot);
-      if (StartsWith(dot, "#") || dot.empty()) {
+      if (android::base::StartsWith(dot, "#") || dot.empty()) {
         continue;
       }
       if (process != nullptr) {
diff --git a/disassembler/disassembler_mips.cc b/disassembler/disassembler_mips.cc
index 4787395..c82600b 100644
--- a/disassembler/disassembler_mips.cc
+++ b/disassembler/disassembler_mips.cc
@@ -22,6 +22,8 @@
 #include "android-base/logging.h"
 #include "android-base/stringprintf.h"
 
+#include "base/bit_utils.h"
+
 using android::base::StringPrintf;
 
 namespace art {
@@ -154,6 +156,7 @@
   { kSpecial3Mask | 0x3f, (31 << kOpcodeShift), "ext", "TSAZ", },
   { kSpecial3Mask | 0x3f, (31 << kOpcodeShift) | 3, "dext", "TSAZ", },
   { kSpecial3Mask | 0x3f, (31 << kOpcodeShift) | 4, "ins", "TSAz", },
+  { kSpecial3Mask | 0x3f, (31 << kOpcodeShift) | 6, "dinsu", "TSFz", },
   { kSpecial3Mask | (0x1f << 21) | (0x1f << 6) | 0x3f,
     (31 << kOpcodeShift) | (16 << 6) | 32,
     "seb",
@@ -218,8 +221,8 @@
   { kITypeMask, 12 << kOpcodeShift, "andi", "TSi", },
   { kITypeMask, 13 << kOpcodeShift, "ori", "TSi", },
   { kITypeMask, 14 << kOpcodeShift, "xori", "TSi", },
-  { kITypeMask | (0x1f << 21), 15 << kOpcodeShift, "lui", "TI", },
-  { kITypeMask, 15 << kOpcodeShift, "aui", "TSI", },
+  { kITypeMask | (0x1f << 21), 15 << kOpcodeShift, "lui", "Ti", },
+  { kITypeMask, 15 << kOpcodeShift, "aui", "TSi", },
 
   { kITypeMask | (0x3e3 << 16), (17 << kOpcodeShift) | (8 << 21), "bc1f", "cB" },
   { kITypeMask | (0x3e3 << 16), (17 << kOpcodeShift) | (8 << 21) | (1 << 16), "bc1t", "cB" },
@@ -335,6 +338,8 @@
   { kITypeMask | (0x1f << 16), (59u << kOpcodeShift) | (30 << 16), "auipc", "Si" },
   { kITypeMask | (0x3 << 19), (59u << kOpcodeShift) | (0 << 19), "addiupc", "Sp" },
   { kITypeMask | (0x3 << 19), (59u << kOpcodeShift) | (1 << 19), "lwpc", "So" },
+  { kITypeMask | (0x3 << 19), (59u << kOpcodeShift) | (2 << 19), "lwupc", "So" },
+  { kITypeMask | (0x7 << 18), (59u << kOpcodeShift) | (6 << 18), "ldpc", "S0" },
   { kITypeMask, 61u << kOpcodeShift, "sdc1", "tO", },
   { kITypeMask | (0x1f << 21), 62u << kOpcodeShift, "jialc", "Ti" },
   { kITypeMask | (1 << 21), (62u << kOpcodeShift) | (1 << 21), "bnezc", "Sb" },  // TODO: de-dup?
@@ -468,6 +473,7 @@
           case 'D': args << 'r' << rd; break;
           case 'd': args << 'f' << rd; break;
           case 'a': args << 'f' << sa; break;
+          case 'F': args << (sa + 32); break;  // dinsu position.
           case 'f':  // Floating point "fmt".
             {
               size_t fmt = (instruction >> 21) & 0x7;  // TODO: other fmts?
@@ -481,9 +487,6 @@
               }
               continue;  // No ", ".
             }
-          case 'I':  // Upper 16-bit immediate.
-            args << reinterpret_cast<void*>((instruction & 0xffff) << 16);
-            break;
           case 'i':  // Sign-extended lower 16-bit immediate.
             args << static_cast<int16_t>(instruction & 0xffff);
             break;
@@ -512,7 +515,7 @@
               }
             }
             break;
-          case 'o':  // 19-bit offset in lwpc.
+          case 'o':  // 19-bit offset in lwpc and lwupc.
             {
               int32_t offset = (instruction & 0x7ffff) - ((instruction & 0x40000) << 1);
               offset <<= 2;
@@ -520,6 +523,15 @@
               args << StringPrintf("  ; %+d", offset);
             }
             break;
+          case '0':  // 18-bit offset in ldpc.
+            {
+              int32_t offset = (instruction & 0x3ffff) - ((instruction & 0x20000) << 1);
+              offset <<= 3;
+              uintptr_t ptr = RoundDown(reinterpret_cast<uintptr_t>(instr_ptr), 8);
+              args << FormatInstructionPointer(reinterpret_cast<const uint8_t*>(ptr + offset));
+              args << StringPrintf("  ; %+d", offset);
+            }
+            break;
           case 'P':  // 26-bit offset in bc and balc.
             {
               int32_t offset = (instruction & 0x3ffffff) - ((instruction & 0x2000000) << 1);
@@ -541,7 +553,7 @@
           case 'T': args << 'r' << rt; break;
           case 't': args << 'f' << rt; break;
           case 'Z': args << (rd + 1); break;  // sz ([d]ext size).
-          case 'z': args << (rd - sa + 1); break;  // sz ([d]ins size).
+          case 'z': args << (rd - sa + 1); break;  // sz ([d]ins, dinsu size).
         }
         if (*(args_fmt + 1)) {
           args << ", ";
@@ -551,17 +563,14 @@
     }
   }
 
-  // TODO: Simplify this once these sequences are simplified in the compiler.
   // Special cases for sequences of:
   //   pc-relative +/- 2GB branch:
   //     auipc  reg, imm
   //     jic    reg, imm
   //   pc-relative +/- 2GB branch and link:
   //     auipc  reg, imm
-  //     daddiu reg, reg, imm
-  //     jialc  reg, 0
-  if (((op == 0x36 && rs == 0 && rt != 0) ||  // jic
-       (op == 0x19 && rs == rt && rt != 0)) &&  // daddiu
+  //     jialc  reg, imm
+  if (((op == 0x36 || op == 0x3E) && rs == 0 && rt != 0) &&  // ji[al]c
       last_ptr_ && (intptr_t)instr_ptr - (intptr_t)last_ptr_ == 4 &&
       (last_instr_ & 0xFC1F0000) == 0xEC1E0000 &&  // auipc
       ((last_instr_ >> 21) & 0x1F) == rt) {
@@ -569,9 +578,9 @@
     offset -= (offset & 0x8000) << 1;
     offset -= 4;
     if (op == 0x36) {
-      args << "  ; b ";
+      args << "  ; bc ";
     } else {
-      args << "  ; move r" << rt << ", ";
+      args << "  ; balc ";
     }
     args << FormatInstructionPointer(instr_ptr + (int32_t)offset);
     args << StringPrintf("  ; %+d", (int32_t)offset);
diff --git a/oatdump/oatdump.cc b/oatdump/oatdump.cc
index 80c7113..e4462d8 100644
--- a/oatdump/oatdump.cc
+++ b/oatdump/oatdump.cc
@@ -26,6 +26,8 @@
 #include <unordered_set>
 #include <vector>
 
+#include "android-base/strings.h"
+
 #include "arch/instruction_set_features.h"
 #include "art_field-inl.h"
 #include "art_method-inl.h"
@@ -668,6 +670,12 @@
     }
 
   private:
+    // All of the elements from one container to another.
+    template <typename Dest, typename Src>
+    static void AddAll(Dest& dest, const Src& src) {
+      dest.insert(src.begin(), src.end());
+    }
+
     void WalkClass(const DexFile& dex_file, const DexFile::ClassDef& class_def) {
       const uint8_t* class_data = dex_file.GetClassData(class_def);
       if (class_data == nullptr) {  // empty class such as a marker interface?
@@ -2952,7 +2960,7 @@
           table_index++;
 
           std::string p_name = ptr2->PrettyMethod(true);
-          if (StartsWith(p_name, method.c_str())) {
+          if (android::base::StartsWith(p_name, method.c_str())) {
             std::cerr << "  Slot "
                       << index
                       << " ("
@@ -2965,7 +2973,7 @@
         }
       } else {
         std::string p_name = ptr->PrettyMethod(true);
-        if (StartsWith(p_name, method.c_str())) {
+        if (android::base::StartsWith(p_name, method.c_str())) {
           std::cerr << "  Slot " << index << " (1)" << std::endl;
           std::cerr << "    " << p_name << std::endl;
         } else {
@@ -2978,7 +2986,7 @@
               for (ArtMethod& iface_method : iface->GetMethods(pointer_size)) {
                 if (ImTable::GetImtIndex(&iface_method) == index) {
                   std::string i_name = iface_method.PrettyMethod(true);
-                  if (StartsWith(i_name, method.c_str())) {
+                  if (android::base::StartsWith(i_name, method.c_str())) {
                     std::cerr << "  Slot " << index << " (1)" << std::endl;
                     std::cerr << "    " << p_name << " (" << i_name << ")" << std::endl;
                   }
@@ -2997,7 +3005,7 @@
     while (in_stream.good()) {
       std::string dot;
       std::getline(in_stream, dot);
-      if (StartsWith(dot, "#") || dot.empty()) {
+      if (android::base::StartsWith(dot, "#") || dot.empty()) {
         continue;
       }
       output.push_back(dot);
diff --git a/oatdump/oatdump_test.cc b/oatdump/oatdump_test.cc
index 22db818..a2eba45 100644
--- a/oatdump/oatdump_test.cc
+++ b/oatdump/oatdump_test.cc
@@ -18,6 +18,8 @@
 #include <string>
 #include <vector>
 
+#include "android-base/strings.h"
+
 #include "common_runtime_test.h"
 
 #include "base/stringprintf.h"
@@ -143,7 +145,7 @@
       }
       argv.push_back(nullptr);
       UNUSED(execv(argv[0], &argv[0]));
-      const std::string command_line(Join(exec_argv, ' '));
+      const std::string command_line(android::base::Join(exec_argv, ' '));
       PLOG(ERROR) << "Failed to execv(" << command_line << ")";
       // _exit to avoid atexit handlers in child.
       _exit(1);
diff --git a/patchoat/patchoat.cc b/patchoat/patchoat.cc
index cb5a790..62d1ddf 100644
--- a/patchoat/patchoat.cc
+++ b/patchoat/patchoat.cc
@@ -24,6 +24,8 @@
 #include <string>
 #include <vector>
 
+#include "android-base/strings.h"
+
 #include "art_field-inl.h"
 #include "art_method-inl.h"
 #include "base/dumpable.h"
@@ -286,8 +288,8 @@
       std::string converted_image_filename = space->GetImageLocation();
       std::replace(converted_image_filename.begin() + 1, converted_image_filename.end(), '/', '@');
       std::string output_image_filename = output_directory +
-                                          (StartsWith(converted_image_filename, "/") ? "" : "/") +
-                                          converted_image_filename;
+          (android::base::StartsWith(converted_image_filename, "/") ? "" : "/") +
+          converted_image_filename;
       std::string output_vdex_filename =
           ImageHeader::GetVdexLocationFromImageLocation(output_image_filename);
       std::string output_oat_filename =
@@ -343,8 +345,8 @@
     std::string converted_image_filename = space->GetImageLocation();
     std::replace(converted_image_filename.begin() + 1, converted_image_filename.end(), '/', '@');
     std::string output_image_filename = output_directory +
-                                        (StartsWith(converted_image_filename, "/") ? "" : "/") +
-                                        converted_image_filename;
+        (android::base::StartsWith(converted_image_filename, "/") ? "" : "/") +
+        converted_image_filename;
     bool new_oat_out;
     std::unique_ptr<File>
         output_image_file(CreateOrOpen(output_image_filename.c_str(), &new_oat_out));
@@ -932,7 +934,7 @@
   for (int i = 0; i < orig_argc; ++i) {
     command.push_back(orig_argv[i]);
   }
-  return Join(command, ' ');
+  return android::base::Join(command, ' ');
 }
 
 static void UsageErrorV(const char* fmt, va_list ap) {
diff --git a/profman/profman.cc b/profman/profman.cc
index bfef834..0b2d172 100644
--- a/profman/profman.cc
+++ b/profman/profman.cc
@@ -25,6 +25,8 @@
 #include <string>
 #include <vector>
 
+#include "android-base/strings.h"
+
 #include "base/dumpable.h"
 #include "base/scoped_flock.h"
 #include "base/stringpiece.h"
@@ -48,7 +50,7 @@
   for (int i = 0; i < original_argc; ++i) {
     command.push_back(original_argv[i]);
   }
-  return Join(command, ' ');
+  return android::base::Join(command, ' ');
 }
 
 static constexpr int kInvalidFd = -1;
diff --git a/runtime/Android.bp b/runtime/Android.bp
index 08be5b2..32ebee2 100644
--- a/runtime/Android.bp
+++ b/runtime/Android.bp
@@ -517,6 +517,7 @@
         "base/unix_file/fd_file_test.cc",
         "cha_test.cc",
         "class_linker_test.cc",
+        "class_table_test.cc",
         "compiler_filter_test.cc",
         "dex_file_test.cc",
         "dex_file_verifier_test.cc",
diff --git a/runtime/arch/arm/instruction_set_features_arm.cc b/runtime/arch/arm/instruction_set_features_arm.cc
index c81a93c..f264b82 100644
--- a/runtime/arch/arm/instruction_set_features_arm.cc
+++ b/runtime/arch/arm/instruction_set_features_arm.cc
@@ -24,6 +24,8 @@
 #include "signal.h"
 #include <fstream>
 
+#include "android-base/strings.h"
+
 #include "base/stringprintf.h"
 #include "utils.h"  // For Trim.
 
@@ -271,7 +273,7 @@
   bool has_atomic_ldrd_strd = has_atomic_ldrd_strd_;
   bool has_div = has_div_;
   for (auto i = features.begin(); i != features.end(); i++) {
-    std::string feature = Trim(*i);
+    std::string feature = android::base::Trim(*i);
     if (feature == "div") {
       has_div = true;
     } else if (feature == "-div") {
diff --git a/runtime/arch/arm64/instruction_set_features_arm64.cc b/runtime/arch/arm64/instruction_set_features_arm64.cc
index 4e7dea3..f7b5a76 100644
--- a/runtime/arch/arm64/instruction_set_features_arm64.cc
+++ b/runtime/arch/arm64/instruction_set_features_arm64.cc
@@ -19,6 +19,8 @@
 #include <fstream>
 #include <sstream>
 
+#include "android-base/strings.h"
+
 #include "base/stl_util.h"
 #include "base/stringprintf.h"
 #include "utils.h"  // For Trim.
@@ -137,7 +139,7 @@
     const bool smp, const std::vector<std::string>& features, std::string* error_msg) const {
   bool is_a53 = fix_cortex_a53_835769_;
   for (auto i = features.begin(); i != features.end(); i++) {
-    std::string feature = Trim(*i);
+    std::string feature = android::base::Trim(*i);
     if (feature == "a53") {
       is_a53 = true;
     } else if (feature == "-a53") {
diff --git a/runtime/arch/instruction_set_features.cc b/runtime/arch/instruction_set_features.cc
index b32391f..db004e7 100644
--- a/runtime/arch/instruction_set_features.cc
+++ b/runtime/arch/instruction_set_features.cc
@@ -16,6 +16,8 @@
 
 #include "instruction_set_features.h"
 
+#include "android-base/strings.h"
+
 #include "base/casts.h"
 #include "utils.h"
 
@@ -224,7 +226,7 @@
       *error_msg = "Unexpected instruction set features after 'default'";
       return std::unique_ptr<const InstructionSetFeatures>();
     }
-    std::string feature = Trim(*it);
+    std::string feature = android::base::Trim(*it);
     bool erase = false;
     if (feature == "default") {
       if (!first) {
diff --git a/runtime/arch/mips/instruction_set_features_mips.cc b/runtime/arch/mips/instruction_set_features_mips.cc
index a95b6f6..a65c967 100644
--- a/runtime/arch/mips/instruction_set_features_mips.cc
+++ b/runtime/arch/mips/instruction_set_features_mips.cc
@@ -19,6 +19,8 @@
 #include <fstream>
 #include <sstream>
 
+#include "android-base/strings.h"
+
 #include "base/stl_util.h"
 #include "base/stringprintf.h"
 #include "utils.h"  // For Trim.
@@ -210,7 +212,7 @@
   bool mips_isa_gte2 = mips_isa_gte2_;
   bool r6 = r6_;
   for (auto i = features.begin(); i != features.end(); i++) {
-    std::string feature = Trim(*i);
+    std::string feature = android::base::Trim(*i);
     if (feature == "fpu32") {
       fpu_32bit = true;
     } else if (feature == "-fpu32") {
diff --git a/runtime/arch/mips64/instruction_set_features_mips64.cc b/runtime/arch/mips64/instruction_set_features_mips64.cc
index 490a8d2..e564d1e 100644
--- a/runtime/arch/mips64/instruction_set_features_mips64.cc
+++ b/runtime/arch/mips64/instruction_set_features_mips64.cc
@@ -19,6 +19,8 @@
 #include <fstream>
 #include <sstream>
 
+#include "android-base/strings.h"
+
 #include "base/stringprintf.h"
 #include "utils.h"  // For Trim.
 
@@ -105,7 +107,7 @@
   auto i = features.begin();
   if (i != features.end()) {
     // We don't have any features.
-    std::string feature = Trim(*i);
+    std::string feature = android::base::Trim(*i);
     *error_msg = StringPrintf("Unknown instruction set feature: '%s'", feature.c_str());
     return nullptr;
   }
diff --git a/runtime/arch/x86/instruction_set_features_x86.cc b/runtime/arch/x86/instruction_set_features_x86.cc
index 90b55a9..cc102ec 100644
--- a/runtime/arch/x86/instruction_set_features_x86.cc
+++ b/runtime/arch/x86/instruction_set_features_x86.cc
@@ -19,6 +19,8 @@
 #include <fstream>
 #include <sstream>
 
+#include "android-base/strings.h"
+
 #include "arch/x86_64/instruction_set_features_x86_64.h"
 #include "base/stringprintf.h"
 #include "utils.h"  // For Trim.
@@ -293,7 +295,7 @@
   bool has_AVX2 = has_AVX2_;
   bool has_POPCNT = has_POPCNT_;
   for (auto i = features.begin(); i != features.end(); i++) {
-    std::string feature = Trim(*i);
+    std::string feature = android::base::Trim(*i);
     if (feature == "ssse3") {
       has_SSSE3 = true;
     } else if (feature == "-ssse3") {
diff --git a/runtime/class_linker_test.cc b/runtime/class_linker_test.cc
index 862585a..685677b 100644
--- a/runtime/class_linker_test.cc
+++ b/runtime/class_linker_test.cc
@@ -19,6 +19,8 @@
 #include <memory>
 #include <string>
 
+#include "android-base/strings.h"
+
 #include "art_field-inl.h"
 #include "art_method-inl.h"
 #include "base/enums.h"
@@ -800,12 +802,12 @@
   jobject jclass_loader = LoadDex("Nested");
   std::vector<const DexFile*> dex_files(GetDexFiles(jclass_loader));
   ASSERT_EQ(dex_files.size(), 1U);
-  EXPECT_TRUE(EndsWith(dex_files[0]->GetLocation(), "Nested.jar"));
+  EXPECT_TRUE(android::base::EndsWith(dex_files[0]->GetLocation(), "Nested.jar"));
 
   jobject jclass_loader2 = LoadDex("MultiDex");
   std::vector<const DexFile*> dex_files2(GetDexFiles(jclass_loader2));
   ASSERT_EQ(dex_files2.size(), 2U);
-  EXPECT_TRUE(EndsWith(dex_files2[0]->GetLocation(), "MultiDex.jar"));
+  EXPECT_TRUE(android::base::EndsWith(dex_files2[0]->GetLocation(), "MultiDex.jar"));
 }
 
 TEST_F(ClassLinkerTest, FindClassNested) {
diff --git a/runtime/class_table-inl.h b/runtime/class_table-inl.h
index 229cd47..dfe8949 100644
--- a/runtime/class_table-inl.h
+++ b/runtime/class_table-inl.h
@@ -71,6 +71,19 @@
   return true;
 }
 
+template <typename Visitor>
+bool ClassTable::Visit(const Visitor& visitor) {
+  ReaderMutexLock mu(Thread::Current(), lock_);
+  for (ClassSet& class_set : classes_) {
+    for (TableSlot& table_slot : class_set) {
+      if (!visitor(table_slot.Read())) {
+        return false;
+      }
+    }
+  }
+  return true;
+}
+
 template<ReadBarrierOption kReadBarrierOption>
 inline mirror::Class* ClassTable::TableSlot::Read() const {
   const uint32_t before = data_.LoadRelaxed();
diff --git a/runtime/class_table.cc b/runtime/class_table.cc
index ec33e5e..0f985c6 100644
--- a/runtime/class_table.cc
+++ b/runtime/class_table.cc
@@ -33,8 +33,9 @@
 
 bool ClassTable::Contains(ObjPtr<mirror::Class> klass) {
   ReaderMutexLock mu(Thread::Current(), lock_);
+  TableSlot slot(klass);
   for (ClassSet& class_set : classes_) {
-    auto it = class_set.Find(TableSlot(klass));
+    auto it = class_set.Find(slot);
     if (it != class_set.end()) {
       return it->Read() == klass;
     }
@@ -44,8 +45,9 @@
 
 mirror::Class* ClassTable::LookupByDescriptor(ObjPtr<mirror::Class> klass) {
   ReaderMutexLock mu(Thread::Current(), lock_);
+  TableSlot slot(klass);
   for (ClassSet& class_set : classes_) {
-    auto it = class_set.Find(TableSlot(klass));
+    auto it = class_set.Find(slot);
     if (it != class_set.end()) {
       return it->Read();
     }
@@ -110,8 +112,8 @@
 }
 
 mirror::Class* ClassTable::Lookup(const char* descriptor, size_t hash) {
-  ReaderMutexLock mu(Thread::Current(), lock_);
   DescriptorHashPair pair(descriptor, hash);
+  ReaderMutexLock mu(Thread::Current(), lock_);
   for (ClassSet& class_set : classes_) {
     auto it = class_set.FindWithHash(pair, hash);
     if (it != class_set.end()) {
@@ -122,12 +124,14 @@
 }
 
 void ClassTable::Insert(ObjPtr<mirror::Class> klass) {
+  const uint32_t hash = TableSlot::HashDescriptor(klass);
   WriterMutexLock mu(Thread::Current(), lock_);
-  classes_.back().Insert(TableSlot(klass));
+  classes_.back().InsertWithHash(TableSlot(klass, hash), hash);
 }
 
 void ClassTable::InsertWithoutLocks(ObjPtr<mirror::Class> klass) {
-  classes_.back().Insert(TableSlot(klass));
+  const uint32_t hash = TableSlot::HashDescriptor(klass);
+  classes_.back().InsertWithHash(TableSlot(klass, hash), hash);
 }
 
 void ClassTable::InsertWithHash(ObjPtr<mirror::Class> klass, size_t hash) {
@@ -136,8 +140,8 @@
 }
 
 bool ClassTable::Remove(const char* descriptor) {
-  WriterMutexLock mu(Thread::Current(), lock_);
   DescriptorHashPair pair(descriptor, ComputeModifiedUtf8Hash(descriptor));
+  WriterMutexLock mu(Thread::Current(), lock_);
   for (ClassSet& class_set : classes_) {
     auto it = class_set.Find(pair);
     if (it != class_set.end()) {
@@ -250,10 +254,12 @@
   strong_roots_.clear();
 }
 
-ClassTable::TableSlot::TableSlot(ObjPtr<mirror::Class> klass) {
+ClassTable::TableSlot::TableSlot(ObjPtr<mirror::Class> klass)
+    : TableSlot(klass, HashDescriptor(klass)) {}
+
+uint32_t ClassTable::TableSlot::HashDescriptor(ObjPtr<mirror::Class> klass) {
   std::string temp;
-  data_.StoreRelaxed(Encode(klass.Ptr(),
-                            MaskHash(ComputeModifiedUtf8Hash(klass->GetDescriptor(&temp)))));
+  return ComputeModifiedUtf8Hash(klass->GetDescriptor(&temp));
 }
 
 }  // namespace art
diff --git a/runtime/class_table.h b/runtime/class_table.h
index 104871f..f27d809 100644
--- a/runtime/class_table.h
+++ b/runtime/class_table.h
@@ -73,6 +73,9 @@
       return MaskHash(other) == Hash();
     }
 
+    static uint32_t HashDescriptor(ObjPtr<mirror::Class> klass)
+        REQUIRES_SHARED(Locks::mutator_lock_);
+
     template<ReadBarrierOption kReadBarrierOption = kWithReadBarrier>
     mirror::Class* Read() const REQUIRES_SHARED(Locks::mutator_lock_);
 
@@ -174,6 +177,10 @@
   bool Visit(Visitor& visitor)
       REQUIRES(!lock_)
       REQUIRES_SHARED(Locks::mutator_lock_);
+  template <typename Visitor>
+  bool Visit(const Visitor& visitor)
+      REQUIRES(!lock_)
+      REQUIRES_SHARED(Locks::mutator_lock_);
 
   // Return the first class that matches the descriptor. Returns null if there are none.
   mirror::Class* Lookup(const char* descriptor, size_t hash)
diff --git a/runtime/class_table_test.cc b/runtime/class_table_test.cc
new file mode 100644
index 0000000..f1248eb
--- /dev/null
+++ b/runtime/class_table_test.cc
@@ -0,0 +1,163 @@
+/*
+ * Copyright (C) 2016 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 "class_table-inl.h"
+
+#include "art_field-inl.h"
+#include "art_method-inl.h"
+#include "class_linker-inl.h"
+#include "common_runtime_test.h"
+#include "dex_file.h"
+#include "gc/accounting/card_table-inl.h"
+#include "gc/heap.h"
+#include "handle_scope-inl.h"
+#include "mirror/class-inl.h"
+#include "obj_ptr.h"
+#include "scoped_thread_state_change-inl.h"
+
+namespace art {
+namespace mirror {
+
+class CollectRootVisitor {
+ public:
+  CollectRootVisitor() {}
+
+  template <class MirrorType>
+  ALWAYS_INLINE void VisitRootIfNonNull(GcRoot<MirrorType>& root) const
+      REQUIRES_SHARED(Locks::mutator_lock_) {
+    if (!root.IsNull()) {
+      VisitRoot(root);
+    }
+  }
+
+  template <class MirrorType>
+  ALWAYS_INLINE void VisitRootIfNonNull(mirror::CompressedReference<MirrorType>* root) const
+      REQUIRES_SHARED(Locks::mutator_lock_) {
+    if (!root->IsNull()) {
+      VisitRoot(root);
+    }
+  }
+
+  template <class MirrorType>
+  void VisitRoot(GcRoot<MirrorType>& root) const REQUIRES_SHARED(Locks::mutator_lock_) {
+    VisitRoot(root.AddressWithoutBarrier());
+  }
+
+  template <class MirrorType>
+  void VisitRoot(mirror::CompressedReference<MirrorType>* root) const
+      REQUIRES_SHARED(Locks::mutator_lock_) {
+    roots_.insert(root->AsMirrorPtr());
+  }
+
+  mutable std::set<mirror::Object*> roots_;
+};
+
+
+class ClassTableTest : public CommonRuntimeTest {};
+
+TEST_F(ClassTableTest, ClassTable) {
+  ScopedObjectAccess soa(Thread::Current());
+  jobject jclass_loader = LoadDex("XandY");
+  VariableSizedHandleScope hs(soa.Self());
+  Handle<ClassLoader> class_loader(hs.NewHandle(soa.Decode<ClassLoader>(jclass_loader)));
+  const char* descriptor_x = "LX;";
+  const char* descriptor_y = "LY;";
+  Handle<mirror::Class> h_X(
+      hs.NewHandle(class_linker_->FindClass(soa.Self(), descriptor_x, class_loader)));
+  Handle<mirror::Class> h_Y(
+      hs.NewHandle(class_linker_->FindClass(soa.Self(), descriptor_y, class_loader)));
+  Handle<mirror::Object> obj_X = hs.NewHandle(h_X->AllocObject(soa.Self()));
+  ASSERT_TRUE(obj_X.Get() != nullptr);
+  ClassTable table;
+  EXPECT_EQ(table.NumZygoteClasses(class_loader.Get()), 0u);
+  EXPECT_EQ(table.NumNonZygoteClasses(class_loader.Get()), 0u);
+
+  // Add h_X to the class table.
+  table.Insert(h_X.Get());
+  EXPECT_EQ(table.LookupByDescriptor(h_X.Get()), h_X.Get());
+  EXPECT_EQ(table.Lookup(descriptor_x, ComputeModifiedUtf8Hash(descriptor_x)), h_X.Get());
+  EXPECT_EQ(table.Lookup("NOT_THERE", ComputeModifiedUtf8Hash("NOT_THERE")), nullptr);
+  EXPECT_EQ(table.NumZygoteClasses(class_loader.Get()), 0u);
+  EXPECT_EQ(table.NumNonZygoteClasses(class_loader.Get()), 1u);
+
+  // Create the zygote snapshot and ensure the accounting is correct.
+  table.FreezeSnapshot();
+  EXPECT_EQ(table.NumZygoteClasses(class_loader.Get()), 1u);
+  EXPECT_EQ(table.NumNonZygoteClasses(class_loader.Get()), 0u);
+
+  // Test inserting and related lookup functions.
+  EXPECT_EQ(table.LookupByDescriptor(h_Y.Get()), nullptr);
+  EXPECT_FALSE(table.Contains(h_Y.Get()));
+  table.Insert(h_Y.Get());
+  EXPECT_EQ(table.LookupByDescriptor(h_X.Get()), h_X.Get());
+  EXPECT_EQ(table.LookupByDescriptor(h_Y.Get()), h_Y.Get());
+  EXPECT_TRUE(table.Contains(h_X.Get()));
+  EXPECT_TRUE(table.Contains(h_Y.Get()));
+
+  EXPECT_EQ(table.NumZygoteClasses(class_loader.Get()), 1u);
+  EXPECT_EQ(table.NumNonZygoteClasses(class_loader.Get()), 1u);
+
+  // Test adding / clearing strong roots.
+  EXPECT_TRUE(table.InsertStrongRoot(obj_X.Get()));
+  EXPECT_FALSE(table.InsertStrongRoot(obj_X.Get()));
+  table.ClearStrongRoots();
+  EXPECT_TRUE(table.InsertStrongRoot(obj_X.Get()));
+
+  // Collect all the roots and make sure there is nothing missing.
+  CollectRootVisitor roots;
+  table.VisitRoots(roots);
+  EXPECT_TRUE(roots.roots_.find(h_X.Get()) != roots.roots_.end());
+  EXPECT_TRUE(roots.roots_.find(h_Y.Get()) != roots.roots_.end());
+  EXPECT_TRUE(roots.roots_.find(obj_X.Get()) != roots.roots_.end());
+
+  // Checks that vising only classes works.
+  std::set<mirror::Class*> classes;
+  table.Visit([&classes](ObjPtr<mirror::Class> klass) REQUIRES_SHARED(Locks::mutator_lock_) {
+    classes.insert(klass.Ptr());
+    return true;
+  });
+  EXPECT_TRUE(classes.find(h_X.Get()) != classes.end());
+  EXPECT_TRUE(classes.find(h_Y.Get()) != classes.end());
+  EXPECT_EQ(classes.size(), 2u);
+  classes.clear();
+  table.Visit([&classes](ObjPtr<mirror::Class> klass) REQUIRES_SHARED(Locks::mutator_lock_) {
+    classes.insert(klass.Ptr());
+    // Return false to exit the Visit early.
+    return false;
+  });
+  EXPECT_EQ(classes.size(), 1u);
+
+  // Test remove.
+  table.Remove(descriptor_x);
+  EXPECT_FALSE(table.Contains(h_X.Get()));
+
+  // Test that WriteToMemory and ReadFromMemory work.
+  table.Insert(h_X.Get());
+  const size_t count = table.WriteToMemory(nullptr);
+  std::unique_ptr<uint8_t[]> buffer(new uint8_t[count]());
+  ASSERT_EQ(table.WriteToMemory(&buffer[0]), count);
+  ClassTable table2;
+  size_t count2 = table2.ReadFromMemory(&buffer[0]);
+  EXPECT_EQ(count, count2);
+  // Strong roots are not serialized, only classes.
+  EXPECT_TRUE(table2.Contains(h_X.Get()));
+  EXPECT_TRUE(table2.Contains(h_Y.Get()));
+
+  // TODO: Add tests for UpdateClass, InsertOatFile.
+}
+
+}  // namespace mirror
+}  // namespace art
diff --git a/runtime/elf_file.cc b/runtime/elf_file.cc
index 2ea7bb6..ee0f340 100644
--- a/runtime/elf_file.cc
+++ b/runtime/elf_file.cc
@@ -20,6 +20,8 @@
 #include <sys/types.h>
 #include <unistd.h>
 
+#include "android-base/strings.h"
+
 #include "arch/instruction_set.h"
 #include "base/logging.h"
 #include "base/stringprintf.h"
@@ -1451,7 +1453,7 @@
       section_headers_original_indexes.push_back(0);
       continue;
     }
-    if (StartsWith(name, ".debug")
+    if (android::base::StartsWith(name, ".debug")
         || (strcmp(name, ".strtab") == 0)
         || (strcmp(name, ".symtab") == 0)) {
       continue;
diff --git a/runtime/gc/collector/concurrent_copying.cc b/runtime/gc/collector/concurrent_copying.cc
index fbab73f..b889913 100644
--- a/runtime/gc/collector/concurrent_copying.cc
+++ b/runtime/gc/collector/concurrent_copying.cc
@@ -1360,9 +1360,10 @@
         << " is_marked=" << IsMarked(to_ref);
   }
 #ifdef USE_BAKER_OR_BROOKS_READ_BARRIER
+  mirror::Object* referent = nullptr;
   if (UNLIKELY((to_ref->GetClass<kVerifyNone, kWithoutReadBarrier>()->IsTypeOfReferenceClass() &&
-                to_ref->AsReference()->GetReferent<kWithoutReadBarrier>() != nullptr &&
-                !IsInToSpace(to_ref->AsReference()->GetReferent<kWithoutReadBarrier>())))) {
+                (referent = to_ref->AsReference()->GetReferent<kWithoutReadBarrier>()) != nullptr &&
+                !IsInToSpace(referent)))) {
     // Leave this reference gray in the queue so that GetReferent() will trigger a read barrier. We
     // will change it to white later in ReferenceQueue::DequeuePendingReference().
     DCHECK(to_ref->AsReference()->GetPendingNext() != nullptr) << "Left unenqueued ref gray " << to_ref;
diff --git a/runtime/gc/space/image_space.cc b/runtime/gc/space/image_space.cc
index c726944..76f3692 100644
--- a/runtime/gc/space/image_space.cc
+++ b/runtime/gc/space/image_space.cc
@@ -22,6 +22,8 @@
 #include <sys/types.h>
 #include <unistd.h>
 
+#include "android-base/strings.h"
+
 #include "art_method.h"
 #include "base/enums.h"
 #include "base/macros.h"
@@ -137,7 +139,7 @@
     arg_vector.push_back(compiler_options[i].c_str());
   }
 
-  std::string command_line(Join(arg_vector, ' '));
+  std::string command_line(android::base::Join(arg_vector, ' '));
   LOG(INFO) << "GenerateImage: " << command_line;
   return Exec(arg_vector, error_msg);
 }
@@ -257,7 +259,7 @@
   argv.push_back(instruction_set_arg);
   argv.push_back(base_offset_arg);
 
-  std::string command_line(Join(argv, ' '));
+  std::string command_line(android::base::Join(argv, ' '));
   LOG(INFO) << "RelocateImage: " << command_line;
   return Exec(argv, error_msg);
 }
diff --git a/runtime/interpreter/interpreter_switch_impl.cc b/runtime/interpreter/interpreter_switch_impl.cc
index 52eacd5..b0d7fb2 100644
--- a/runtime/interpreter/interpreter_switch_impl.cc
+++ b/runtime/interpreter/interpreter_switch_impl.cc
@@ -92,6 +92,16 @@
     }                                                                                          \
   } while (false)
 
+#define HANDLE_BACKWARD_BRANCH(offset)                                                         \
+  do {                                                                                         \
+    if (IsBackwardBranch(offset)) {                                                            \
+      HOTNESS_UPDATE();                                                                        \
+      /* Record new dex pc early to have consistent suspend point at loop header. */           \
+      shadow_frame.SetDexPC(inst->GetDexPc(insns));                                            \
+      self->AllowThreadSuspension();                                                           \
+    }                                                                                          \
+  } while (false)
+
 template<bool do_access_check, bool transaction_active>
 JValue ExecuteSwitchImpl(Thread* self, const DexFile::CodeItem* code_item,
                          ShadowFrame& shadow_frame, JValue result_register,
@@ -594,55 +604,40 @@
         PREAMBLE();
         int8_t offset = inst->VRegA_10t(inst_data);
         BRANCH_INSTRUMENTATION(offset);
-        if (IsBackwardBranch(offset)) {
-          HOTNESS_UPDATE();
-          self->AllowThreadSuspension();
-        }
         inst = inst->RelativeAt(offset);
+        HANDLE_BACKWARD_BRANCH(offset);
         break;
       }
       case Instruction::GOTO_16: {
         PREAMBLE();
         int16_t offset = inst->VRegA_20t();
         BRANCH_INSTRUMENTATION(offset);
-        if (IsBackwardBranch(offset)) {
-          HOTNESS_UPDATE();
-          self->AllowThreadSuspension();
-        }
         inst = inst->RelativeAt(offset);
+        HANDLE_BACKWARD_BRANCH(offset);
         break;
       }
       case Instruction::GOTO_32: {
         PREAMBLE();
         int32_t offset = inst->VRegA_30t();
         BRANCH_INSTRUMENTATION(offset);
-        if (IsBackwardBranch(offset)) {
-          HOTNESS_UPDATE();
-          self->AllowThreadSuspension();
-        }
         inst = inst->RelativeAt(offset);
+        HANDLE_BACKWARD_BRANCH(offset);
         break;
       }
       case Instruction::PACKED_SWITCH: {
         PREAMBLE();
         int32_t offset = DoPackedSwitch(inst, shadow_frame, inst_data);
         BRANCH_INSTRUMENTATION(offset);
-        if (IsBackwardBranch(offset)) {
-          HOTNESS_UPDATE();
-          self->AllowThreadSuspension();
-        }
         inst = inst->RelativeAt(offset);
+        HANDLE_BACKWARD_BRANCH(offset);
         break;
       }
       case Instruction::SPARSE_SWITCH: {
         PREAMBLE();
         int32_t offset = DoSparseSwitch(inst, shadow_frame, inst_data);
         BRANCH_INSTRUMENTATION(offset);
-        if (IsBackwardBranch(offset)) {
-          HOTNESS_UPDATE();
-          self->AllowThreadSuspension();
-        }
         inst = inst->RelativeAt(offset);
+        HANDLE_BACKWARD_BRANCH(offset);
         break;
       }
 
@@ -739,11 +734,8 @@
             shadow_frame.GetVReg(inst->VRegB_22t(inst_data))) {
           int16_t offset = inst->VRegC_22t();
           BRANCH_INSTRUMENTATION(offset);
-          if (IsBackwardBranch(offset)) {
-            HOTNESS_UPDATE();
-            self->AllowThreadSuspension();
-          }
           inst = inst->RelativeAt(offset);
+          HANDLE_BACKWARD_BRANCH(offset);
         } else {
           BRANCH_INSTRUMENTATION(2);
           inst = inst->Next_2xx();
@@ -756,11 +748,8 @@
             shadow_frame.GetVReg(inst->VRegB_22t(inst_data))) {
           int16_t offset = inst->VRegC_22t();
           BRANCH_INSTRUMENTATION(offset);
-          if (IsBackwardBranch(offset)) {
-            HOTNESS_UPDATE();
-            self->AllowThreadSuspension();
-          }
           inst = inst->RelativeAt(offset);
+          HANDLE_BACKWARD_BRANCH(offset);
         } else {
           BRANCH_INSTRUMENTATION(2);
           inst = inst->Next_2xx();
@@ -773,11 +762,8 @@
             shadow_frame.GetVReg(inst->VRegB_22t(inst_data))) {
           int16_t offset = inst->VRegC_22t();
           BRANCH_INSTRUMENTATION(offset);
-          if (IsBackwardBranch(offset)) {
-            HOTNESS_UPDATE();
-            self->AllowThreadSuspension();
-          }
           inst = inst->RelativeAt(offset);
+          HANDLE_BACKWARD_BRANCH(offset);
         } else {
           BRANCH_INSTRUMENTATION(2);
           inst = inst->Next_2xx();
@@ -790,11 +776,8 @@
             shadow_frame.GetVReg(inst->VRegB_22t(inst_data))) {
           int16_t offset = inst->VRegC_22t();
           BRANCH_INSTRUMENTATION(offset);
-          if (IsBackwardBranch(offset)) {
-            HOTNESS_UPDATE();
-            self->AllowThreadSuspension();
-          }
           inst = inst->RelativeAt(offset);
+          HANDLE_BACKWARD_BRANCH(offset);
         } else {
           BRANCH_INSTRUMENTATION(2);
           inst = inst->Next_2xx();
@@ -807,11 +790,8 @@
         shadow_frame.GetVReg(inst->VRegB_22t(inst_data))) {
           int16_t offset = inst->VRegC_22t();
           BRANCH_INSTRUMENTATION(offset);
-          if (IsBackwardBranch(offset)) {
-            HOTNESS_UPDATE();
-            self->AllowThreadSuspension();
-          }
           inst = inst->RelativeAt(offset);
+          HANDLE_BACKWARD_BRANCH(offset);
         } else {
           BRANCH_INSTRUMENTATION(2);
           inst = inst->Next_2xx();
@@ -824,11 +804,8 @@
             shadow_frame.GetVReg(inst->VRegB_22t(inst_data))) {
           int16_t offset = inst->VRegC_22t();
           BRANCH_INSTRUMENTATION(offset);
-          if (IsBackwardBranch(offset)) {
-            HOTNESS_UPDATE();
-            self->AllowThreadSuspension();
-          }
           inst = inst->RelativeAt(offset);
+          HANDLE_BACKWARD_BRANCH(offset);
         } else {
           BRANCH_INSTRUMENTATION(2);
           inst = inst->Next_2xx();
@@ -840,11 +817,8 @@
         if (shadow_frame.GetVReg(inst->VRegA_21t(inst_data)) == 0) {
           int16_t offset = inst->VRegB_21t();
           BRANCH_INSTRUMENTATION(offset);
-          if (IsBackwardBranch(offset)) {
-            HOTNESS_UPDATE();
-            self->AllowThreadSuspension();
-          }
           inst = inst->RelativeAt(offset);
+          HANDLE_BACKWARD_BRANCH(offset);
         } else {
           BRANCH_INSTRUMENTATION(2);
           inst = inst->Next_2xx();
@@ -856,11 +830,8 @@
         if (shadow_frame.GetVReg(inst->VRegA_21t(inst_data)) != 0) {
           int16_t offset = inst->VRegB_21t();
           BRANCH_INSTRUMENTATION(offset);
-          if (IsBackwardBranch(offset)) {
-            HOTNESS_UPDATE();
-            self->AllowThreadSuspension();
-          }
           inst = inst->RelativeAt(offset);
+          HANDLE_BACKWARD_BRANCH(offset);
         } else {
           BRANCH_INSTRUMENTATION(2);
           inst = inst->Next_2xx();
@@ -872,11 +843,8 @@
         if (shadow_frame.GetVReg(inst->VRegA_21t(inst_data)) < 0) {
           int16_t offset = inst->VRegB_21t();
           BRANCH_INSTRUMENTATION(offset);
-          if (IsBackwardBranch(offset)) {
-            HOTNESS_UPDATE();
-            self->AllowThreadSuspension();
-          }
           inst = inst->RelativeAt(offset);
+          HANDLE_BACKWARD_BRANCH(offset);
         } else {
           BRANCH_INSTRUMENTATION(2);
           inst = inst->Next_2xx();
@@ -888,11 +856,8 @@
         if (shadow_frame.GetVReg(inst->VRegA_21t(inst_data)) >= 0) {
           int16_t offset = inst->VRegB_21t();
           BRANCH_INSTRUMENTATION(offset);
-          if (IsBackwardBranch(offset)) {
-            HOTNESS_UPDATE();
-            self->AllowThreadSuspension();
-          }
           inst = inst->RelativeAt(offset);
+          HANDLE_BACKWARD_BRANCH(offset);
         } else {
           BRANCH_INSTRUMENTATION(2);
           inst = inst->Next_2xx();
@@ -904,11 +869,8 @@
         if (shadow_frame.GetVReg(inst->VRegA_21t(inst_data)) > 0) {
           int16_t offset = inst->VRegB_21t();
           BRANCH_INSTRUMENTATION(offset);
-          if (IsBackwardBranch(offset)) {
-            HOTNESS_UPDATE();
-            self->AllowThreadSuspension();
-          }
           inst = inst->RelativeAt(offset);
+          HANDLE_BACKWARD_BRANCH(offset);
         } else {
           BRANCH_INSTRUMENTATION(2);
           inst = inst->Next_2xx();
@@ -920,11 +882,8 @@
         if (shadow_frame.GetVReg(inst->VRegA_21t(inst_data)) <= 0) {
           int16_t offset = inst->VRegB_21t();
           BRANCH_INSTRUMENTATION(offset);
-          if (IsBackwardBranch(offset)) {
-            HOTNESS_UPDATE();
-            self->AllowThreadSuspension();
-          }
           inst = inst->RelativeAt(offset);
+          HANDLE_BACKWARD_BRANCH(offset);
         } else {
           BRANCH_INSTRUMENTATION(2);
           inst = inst->Next_2xx();
diff --git a/runtime/jit/profile_saver.cc b/runtime/jit/profile_saver.cc
index 11d601e..025d10c 100644
--- a/runtime/jit/profile_saver.cc
+++ b/runtime/jit/profile_saver.cc
@@ -20,6 +20,8 @@
 #include <sys/stat.h>
 #include <fcntl.h>
 
+#include "android-base/strings.h"
+
 #include "art_method-inl.h"
 #include "base/enums.h"
 #include "base/systrace.h"
@@ -412,7 +414,7 @@
   }
 
   VLOG(profiler) << "Starting profile saver using output file: " << output_filename
-      << ". Tracking: " << Join(code_paths_to_profile, ':');
+      << ". Tracking: " << android::base::Join(code_paths_to_profile, ':');
 
   instance_ = new ProfileSaver(options,
                                output_filename,
diff --git a/runtime/mirror/dex_cache-inl.h b/runtime/mirror/dex_cache-inl.h
index b54e416..a59bb7b 100644
--- a/runtime/mirror/dex_cache-inl.h
+++ b/runtime/mirror/dex_cache-inl.h
@@ -72,7 +72,7 @@
 
 inline Class* DexCache::GetResolvedType(dex::TypeIndex type_idx) {
   // It is theorized that a load acquire is not required since obtaining the resolved class will
-  // always have an address depedency or a lock.
+  // always have an address dependency or a lock.
   DCHECK_LT(type_idx.index_, NumResolvedTypes());
   return GetResolvedTypes()[type_idx.index_].Read();
 }
diff --git a/runtime/mirror/string-inl.h b/runtime/mirror/string-inl.h
index 6870fda..95516ac 100644
--- a/runtime/mirror/string-inl.h
+++ b/runtime/mirror/string-inl.h
@@ -305,8 +305,11 @@
 
 template<typename MemoryType>
 bool String::AllASCII(const MemoryType* const chars, const int length) {
+  static_assert(std::is_unsigned<MemoryType>::value, "Expecting unsigned MemoryType");
   for (int i = 0; i < length; ++i) {
-    if (chars[i] >= 0x80) {
+    // Valid ASCII characters are in range 1..0x7f. Zero is not considered ASCII
+    // because it would complicate the detection of ASCII strings in Modified-UTF8.
+    if ((chars[i] - 1u) >= 0x7fu) {
       return false;
     }
   }
diff --git a/runtime/oat_file_assistant.cc b/runtime/oat_file_assistant.cc
index 6a62a16..7f7b1b5 100644
--- a/runtime/oat_file_assistant.cc
+++ b/runtime/oat_file_assistant.cc
@@ -19,6 +19,9 @@
 #include <sstream>
 
 #include <sys/stat.h>
+
+#include "android-base/strings.h"
+
 #include "base/logging.h"
 #include "base/stringprintf.h"
 #include "compiler_filter.h"
@@ -456,7 +459,7 @@
   argv.push_back("--output-oat-file=" + oat_file_name);
   argv.push_back("--patched-image-location=" + image_info->location);
 
-  std::string command_line(Join(argv, ' '));
+  std::string command_line(android::base::Join(argv, ' '));
   if (!Exec(argv, error_msg)) {
     // Manually delete the file. This ensures there is no garbage left over if
     // the process unexpectedly died.
@@ -605,7 +608,7 @@
 
   argv.insert(argv.end(), args.begin(), args.end());
 
-  std::string command_line(Join(argv, ' '));
+  std::string command_line(android::base::Join(argv, ' '));
   return Exec(argv, error_msg);
 }
 
diff --git a/runtime/oat_file_assistant_test.cc b/runtime/oat_file_assistant_test.cc
index 94c12af..26dbaab 100644
--- a/runtime/oat_file_assistant_test.cc
+++ b/runtime/oat_file_assistant_test.cc
@@ -20,6 +20,7 @@
 #include <vector>
 #include <sys/param.h>
 
+#include "android-base/strings.h"
 #include <backtrace/BacktraceMap.h>
 #include <gtest/gtest.h>
 
@@ -1057,7 +1058,7 @@
 
   // Reverse again to get the right path order, and join to get the result.
   std::reverse(target_path.begin(), target_path.end());
-  return Join(target_path, '/');
+  return android::base::Join(target_path, '/');
 }
 
 // Case: Non-absolute path to Dex location.
@@ -1134,7 +1135,7 @@
         /*dex_elements*/nullptr,
         &oat_file,
         &error_msgs);
-    CHECK(!dex_files.empty()) << Join(error_msgs, '\n');
+    CHECK(!dex_files.empty()) << android::base::Join(error_msgs, '\n');
     CHECK(dex_files[0]->GetOatDexFile() != nullptr) << dex_files[0]->GetLocation();
     loaded_oat_file_ = dex_files[0]->GetOatDexFile()->GetOatFile();
     CHECK_EQ(loaded_oat_file_, oat_file);
diff --git a/runtime/openjdkjvmti/ti_stack.cc b/runtime/openjdkjvmti/ti_stack.cc
index 6f8976f..579fb50 100644
--- a/runtime/openjdkjvmti/ti_stack.cc
+++ b/runtime/openjdkjvmti/ti_stack.cc
@@ -67,14 +67,10 @@
       m = m->GetInterfaceMethodIfProxy(art::kRuntimePointerSize);
       jmethodID id = art::jni::EncodeArtMethod(m);
 
-      art::mirror::DexCache* dex_cache = m->GetDexCache();
-      int32_t line_number = -1;
-      if (dex_cache != nullptr) {  // be tolerant of bad input
-        const art::DexFile* dex_file = dex_cache->GetDexFile();
-        line_number = art::annotations::GetLineNumFromPC(dex_file, m, GetDexPc(false));
-      }
+      uint32_t dex_pc = GetDexPc(false);
+      jlong dex_location = (dex_pc == art::DexFile::kDexNoIndex) ? -1 : static_cast<jlong>(dex_pc);
 
-      jvmtiFrameInfo info = { id, static_cast<jlong>(line_number) };
+      jvmtiFrameInfo info = { id, dex_location };
       frames.push_back(info);
 
       if (stop == 1) {
diff --git a/runtime/runtime.cc b/runtime/runtime.cc
index 14628f0..59c5961 100644
--- a/runtime/runtime.cc
+++ b/runtime/runtime.cc
@@ -37,6 +37,8 @@
 #include <vector>
 #include <fcntl.h>
 
+#include "android-base/strings.h"
+
 #include "JniConstants.h"
 #include "ScopedLocalRef.h"
 #include "arch/arm/quick_method_frame_info_arm.h"
@@ -869,7 +871,7 @@
         ImageHeader::GetOatLocationFromImageLocation(image_locations[index].c_str());
     // Note: in the multi-image case, the image location may end in ".jar," and not ".art." Handle
     //       that here.
-    if (EndsWith(oat_location, ".jar")) {
+    if (android::base::EndsWith(oat_location, ".jar")) {
       oat_location.replace(oat_location.length() - 3, 3, "oat");
     }
     std::string error_msg;
@@ -1225,7 +1227,7 @@
       for (const DexFile* dex_file : boot_class_path) {
         dex_locations.push_back(dex_file->GetLocation());
       }
-      boot_class_path_string_ = Join(dex_locations, ':');
+      boot_class_path_string_ = android::base::Join(dex_locations, ':');
     }
     {
       ScopedTrace trace2("AddImageStringsToTable");
@@ -1892,7 +1894,7 @@
   }
 
   VLOG(profiler) << "Register app with " << profile_output_filename
-      << " " << Join(code_paths, ':');
+      << " " << android::base::Join(code_paths, ':');
 
   if (profile_output_filename.empty()) {
     LOG(WARNING) << "JIT profile information will not be recorded: profile filename is empty.";
diff --git a/runtime/thread.cc b/runtime/thread.cc
index bc133d1..d79bf36 100644
--- a/runtime/thread.cc
+++ b/runtime/thread.cc
@@ -873,6 +873,62 @@
   Dbg::DdmSendThreadNotification(this, CHUNK_TYPE("THNM"));
 }
 
+static void GetThreadStack(pthread_t thread,
+                           void** stack_base,
+                           size_t* stack_size,
+                           size_t* guard_size) {
+#if defined(__APPLE__)
+  *stack_size = pthread_get_stacksize_np(thread);
+  void* stack_addr = pthread_get_stackaddr_np(thread);
+
+  // Check whether stack_addr is the base or end of the stack.
+  // (On Mac OS 10.7, it's the end.)
+  int stack_variable;
+  if (stack_addr > &stack_variable) {
+    *stack_base = reinterpret_cast<uint8_t*>(stack_addr) - *stack_size;
+  } else {
+    *stack_base = stack_addr;
+  }
+
+  // This is wrong, but there doesn't seem to be a way to get the actual value on the Mac.
+  pthread_attr_t attributes;
+  CHECK_PTHREAD_CALL(pthread_attr_init, (&attributes), __FUNCTION__);
+  CHECK_PTHREAD_CALL(pthread_attr_getguardsize, (&attributes, guard_size), __FUNCTION__);
+  CHECK_PTHREAD_CALL(pthread_attr_destroy, (&attributes), __FUNCTION__);
+#else
+  pthread_attr_t attributes;
+  CHECK_PTHREAD_CALL(pthread_getattr_np, (thread, &attributes), __FUNCTION__);
+  CHECK_PTHREAD_CALL(pthread_attr_getstack, (&attributes, stack_base, stack_size), __FUNCTION__);
+  CHECK_PTHREAD_CALL(pthread_attr_getguardsize, (&attributes, guard_size), __FUNCTION__);
+  CHECK_PTHREAD_CALL(pthread_attr_destroy, (&attributes), __FUNCTION__);
+
+#if defined(__GLIBC__)
+  // If we're the main thread, check whether we were run with an unlimited stack. In that case,
+  // glibc will have reported a 2GB stack for our 32-bit process, and our stack overflow detection
+  // will be broken because we'll die long before we get close to 2GB.
+  bool is_main_thread = (::art::GetTid() == getpid());
+  if (is_main_thread) {
+    rlimit stack_limit;
+    if (getrlimit(RLIMIT_STACK, &stack_limit) == -1) {
+      PLOG(FATAL) << "getrlimit(RLIMIT_STACK) failed";
+    }
+    if (stack_limit.rlim_cur == RLIM_INFINITY) {
+      size_t old_stack_size = *stack_size;
+
+      // Use the kernel default limit as our size, and adjust the base to match.
+      *stack_size = 8 * MB;
+      *stack_base = reinterpret_cast<uint8_t*>(*stack_base) + (old_stack_size - *stack_size);
+
+      VLOG(threads) << "Limiting unlimited stack (reported as " << PrettySize(old_stack_size) << ")"
+                    << " to " << PrettySize(*stack_size)
+                    << " with base " << *stack_base;
+    }
+  }
+#endif
+
+#endif
+}
+
 bool Thread::InitStackHwm() {
   void* read_stack_base;
   size_t read_stack_size;
@@ -1322,6 +1378,32 @@
   VLOG(threads) << this << " self-reviving";
 }
 
+static std::string GetSchedulerGroupName(pid_t tid) {
+  // /proc/<pid>/cgroup looks like this:
+  // 2:devices:/
+  // 1:cpuacct,cpu:/
+  // We want the third field from the line whose second field contains the "cpu" token.
+  std::string cgroup_file;
+  if (!ReadFileToString(StringPrintf("/proc/self/task/%d/cgroup", tid), &cgroup_file)) {
+    return "";
+  }
+  std::vector<std::string> cgroup_lines;
+  Split(cgroup_file, '\n', &cgroup_lines);
+  for (size_t i = 0; i < cgroup_lines.size(); ++i) {
+    std::vector<std::string> cgroup_fields;
+    Split(cgroup_lines[i], ':', &cgroup_fields);
+    std::vector<std::string> cgroups;
+    Split(cgroup_fields[1], ',', &cgroups);
+    for (size_t j = 0; j < cgroups.size(); ++j) {
+      if (cgroups[j] == "cpu") {
+        return cgroup_fields[2].substr(1);  // Skip the leading slash.
+      }
+    }
+  }
+  return "";
+}
+
+
 void Thread::DumpState(std::ostream& os, const Thread* thread, pid_t tid) {
   std::string group_name;
   int priority;
diff --git a/runtime/utils.cc b/runtime/utils.cc
index 66739a9..4732f59 100644
--- a/runtime/utils.cc
+++ b/runtime/utils.cc
@@ -25,6 +25,8 @@
 #include <unistd.h>
 #include <memory>
 
+#include "android-base/strings.h"
+
 #include "base/stl_util.h"
 #include "base/unix_file/fd_file.h"
 #include "dex_file-inl.h"
@@ -139,59 +141,6 @@
   return result;
 }
 
-void GetThreadStack(pthread_t thread, void** stack_base, size_t* stack_size, size_t* guard_size) {
-#if defined(__APPLE__)
-  *stack_size = pthread_get_stacksize_np(thread);
-  void* stack_addr = pthread_get_stackaddr_np(thread);
-
-  // Check whether stack_addr is the base or end of the stack.
-  // (On Mac OS 10.7, it's the end.)
-  int stack_variable;
-  if (stack_addr > &stack_variable) {
-    *stack_base = reinterpret_cast<uint8_t*>(stack_addr) - *stack_size;
-  } else {
-    *stack_base = stack_addr;
-  }
-
-  // This is wrong, but there doesn't seem to be a way to get the actual value on the Mac.
-  pthread_attr_t attributes;
-  CHECK_PTHREAD_CALL(pthread_attr_init, (&attributes), __FUNCTION__);
-  CHECK_PTHREAD_CALL(pthread_attr_getguardsize, (&attributes, guard_size), __FUNCTION__);
-  CHECK_PTHREAD_CALL(pthread_attr_destroy, (&attributes), __FUNCTION__);
-#else
-  pthread_attr_t attributes;
-  CHECK_PTHREAD_CALL(pthread_getattr_np, (thread, &attributes), __FUNCTION__);
-  CHECK_PTHREAD_CALL(pthread_attr_getstack, (&attributes, stack_base, stack_size), __FUNCTION__);
-  CHECK_PTHREAD_CALL(pthread_attr_getguardsize, (&attributes, guard_size), __FUNCTION__);
-  CHECK_PTHREAD_CALL(pthread_attr_destroy, (&attributes), __FUNCTION__);
-
-#if defined(__GLIBC__)
-  // If we're the main thread, check whether we were run with an unlimited stack. In that case,
-  // glibc will have reported a 2GB stack for our 32-bit process, and our stack overflow detection
-  // will be broken because we'll die long before we get close to 2GB.
-  bool is_main_thread = (::art::GetTid() == getpid());
-  if (is_main_thread) {
-    rlimit stack_limit;
-    if (getrlimit(RLIMIT_STACK, &stack_limit) == -1) {
-      PLOG(FATAL) << "getrlimit(RLIMIT_STACK) failed";
-    }
-    if (stack_limit.rlim_cur == RLIM_INFINITY) {
-      size_t old_stack_size = *stack_size;
-
-      // Use the kernel default limit as our size, and adjust the base to match.
-      *stack_size = 8 * MB;
-      *stack_base = reinterpret_cast<uint8_t*>(*stack_base) + (old_stack_size - *stack_size);
-
-      VLOG(threads) << "Limiting unlimited stack (reported as " << PrettySize(old_stack_size) << ")"
-                    << " to " << PrettySize(*stack_size)
-                    << " with base " << *stack_base;
-    }
-  }
-#endif
-
-#endif
-}
-
 bool ReadFileToString(const std::string& file_name, std::string* result) {
   File file(file_name, O_RDONLY, false);
   if (!file.IsOpened()) {
@@ -411,6 +360,10 @@
                       negative_str, byte_count / kBytesPerUnit[i], kUnitStrings[i]);
 }
 
+static inline constexpr bool NeedsEscaping(uint16_t ch) {
+  return (ch < ' ' || ch > '~');
+}
+
 std::string PrintableChar(uint16_t ch) {
   std::string result;
   result += '\'';
@@ -782,67 +735,6 @@
   }
 }
 
-std::string Trim(const std::string& s) {
-  std::string result;
-  unsigned int start_index = 0;
-  unsigned int end_index = s.size() - 1;
-
-  // Skip initial whitespace.
-  while (start_index < s.size()) {
-    if (!isspace(s[start_index])) {
-      break;
-    }
-    start_index++;
-  }
-
-  // Skip terminating whitespace.
-  while (end_index >= start_index) {
-    if (!isspace(s[end_index])) {
-      break;
-    }
-    end_index--;
-  }
-
-  // All spaces, no beef.
-  if (end_index < start_index) {
-    return "";
-  }
-  // Start_index is the first non-space, end_index is the last one.
-  return s.substr(start_index, end_index - start_index + 1);
-}
-
-template <typename StringT>
-std::string Join(const std::vector<StringT>& strings, char separator) {
-  if (strings.empty()) {
-    return "";
-  }
-
-  std::string result(strings[0]);
-  for (size_t i = 1; i < strings.size(); ++i) {
-    result += separator;
-    result += strings[i];
-  }
-  return result;
-}
-
-// Explicit instantiations.
-template std::string Join<std::string>(const std::vector<std::string>& strings, char separator);
-template std::string Join<const char*>(const std::vector<const char*>& strings, char separator);
-
-bool StartsWith(const std::string& s, const char* prefix) {
-  return s.compare(0, strlen(prefix), prefix) == 0;
-}
-
-bool EndsWith(const std::string& s, const char* suffix) {
-  size_t suffix_length = strlen(suffix);
-  size_t string_length = s.size();
-  if (suffix_length > string_length) {
-    return false;
-  }
-  size_t offset = string_length - suffix_length;
-  return s.compare(offset, suffix_length, suffix) == 0;
-}
-
 void SetThreadName(const char* thread_name) {
   int hasAt = 0;
   int hasDot = 0;
@@ -892,31 +784,6 @@
   *task_cpu = strtoull(fields[36].c_str(), nullptr, 10);
 }
 
-std::string GetSchedulerGroupName(pid_t tid) {
-  // /proc/<pid>/cgroup looks like this:
-  // 2:devices:/
-  // 1:cpuacct,cpu:/
-  // We want the third field from the line whose second field contains the "cpu" token.
-  std::string cgroup_file;
-  if (!ReadFileToString(StringPrintf("/proc/self/task/%d/cgroup", tid), &cgroup_file)) {
-    return "";
-  }
-  std::vector<std::string> cgroup_lines;
-  Split(cgroup_file, '\n', &cgroup_lines);
-  for (size_t i = 0; i < cgroup_lines.size(); ++i) {
-    std::vector<std::string> cgroup_fields;
-    Split(cgroup_lines[i], ':', &cgroup_fields);
-    std::vector<std::string> cgroups;
-    Split(cgroup_fields[1], ',', &cgroups);
-    for (size_t j = 0; j < cgroups.size(); ++j) {
-      if (cgroups[j] == "cpu") {
-        return cgroup_fields[2].substr(1);  // Skip the leading slash.
-      }
-    }
-  }
-  return "";
-}
-
 const char* GetAndroidRoot() {
   const char* android_root = getenv("ANDROID_ROOT");
   if (android_root == nullptr) {
@@ -1005,7 +872,9 @@
     return false;
   }
   std::string cache_file(&location[1]);  // skip leading slash
-  if (!EndsWith(location, ".dex") && !EndsWith(location, ".art") && !EndsWith(location, ".oat")) {
+  if (!android::base::EndsWith(location, ".dex") &&
+      !android::base::EndsWith(location, ".art") &&
+      !android::base::EndsWith(location, ".oat")) {
     cache_file += "/";
     cache_file += DexFile::kClassesDex;
   }
@@ -1032,7 +901,7 @@
 }
 
 int ExecAndReturnCode(std::vector<std::string>& arg_vector, std::string* error_msg) {
-  const std::string command_line(Join(arg_vector, ' '));
+  const std::string command_line(android::base::Join(arg_vector, ' '));
   CHECK_GE(arg_vector.size(), 1U) << command_line;
 
   // Convert the args to char pointers.
@@ -1091,7 +960,7 @@
 bool Exec(std::vector<std::string>& arg_vector, std::string* error_msg) {
   int status = ExecAndReturnCode(arg_vector, error_msg);
   if (status != 0) {
-    const std::string command_line(Join(arg_vector, ' '));
+    const std::string command_line(android::base::Join(arg_vector, ' '));
     *error_msg = StringPrintf("Failed execv(%s) because non-0 exit status",
                               command_line.c_str());
     return false;
diff --git a/runtime/utils.h b/runtime/utils.h
index 1e98057..04e0dde 100644
--- a/runtime/utils.h
+++ b/runtime/utils.h
@@ -64,45 +64,12 @@
   return true;
 }
 
-// Return whether x / divisor == x * (1.0f / divisor), for every float x.
-static constexpr bool CanDivideByReciprocalMultiplyFloat(int32_t divisor) {
-  // True, if the most significant bits of divisor are 0.
-  return ((divisor & 0x7fffff) == 0);
-}
-
-// Return whether x / divisor == x * (1.0 / divisor), for every double x.
-static constexpr bool CanDivideByReciprocalMultiplyDouble(int64_t divisor) {
-  // True, if the most significant bits of divisor are 0.
-  return ((divisor & ((UINT64_C(1) << 52) - 1)) == 0);
-}
-
 static inline uint32_t PointerToLowMemUInt32(const void* p) {
   uintptr_t intp = reinterpret_cast<uintptr_t>(p);
   DCHECK_LE(intp, 0xFFFFFFFFU);
   return intp & 0xFFFFFFFFU;
 }
 
-static inline bool NeedsEscaping(uint16_t ch) {
-  return (ch < ' ' || ch > '~');
-}
-
-template <typename T> T SafeAbs(T value) {
-  // std::abs has undefined behavior on min limits.
-  DCHECK_NE(value, std::numeric_limits<T>::min());
-  return std::abs(value);
-}
-
-template <typename T> T AbsOrMin(T value) {
-  return (value == std::numeric_limits<T>::min())
-      ? value
-      : std::abs(value);
-}
-
-template <typename T>
-inline typename std::make_unsigned<T>::type MakeUnsigned(T x) {
-  return static_cast<typename std::make_unsigned<T>::type>(x);
-}
-
 uint8_t* DecodeBase64(const char* src, size_t* dst_size);
 
 std::string PrintableChar(uint16_t ch);
@@ -111,12 +78,6 @@
 // Java escapes are used for non-ASCII characters.
 std::string PrintableString(const char* utf8);
 
-// Tests whether 's' starts with 'prefix'.
-bool StartsWith(const std::string& s, const char* prefix);
-
-// Tests whether 's' ends with 'suffix'.
-bool EndsWith(const std::string& s, const char* suffix);
-
 // Used to implement PrettyClass, PrettyField, PrettyMethod, and PrettyTypeOf,
 // one of which is probably more useful to you.
 // Returns a human-readable equivalent of 'descriptor'. So "I" would be "int",
@@ -167,27 +128,15 @@
 // strings. Empty strings will be omitted.
 void Split(const std::string& s, char separator, std::vector<std::string>* result);
 
-// Trims whitespace off both ends of the given string.
-std::string Trim(const std::string& s);
-
-// Joins a vector of strings into a single string, using the given separator.
-template <typename StringT> std::string Join(const std::vector<StringT>& strings, char separator);
-
 // Returns the calling thread's tid. (The C libraries don't expose this.)
 pid_t GetTid();
 
 // Returns the given thread's name.
 std::string GetThreadName(pid_t tid);
 
-// Returns details of the given thread's stack.
-void GetThreadStack(pthread_t thread, void** stack_base, size_t* stack_size, size_t* guard_size);
-
 // Reads data from "/proc/self/task/${tid}/stat".
 void GetTaskStats(pid_t tid, char* state, int* utime, int* stime, int* task_cpu);
 
-// Returns the name of the scheduler group for the given thread the current process, or the empty string.
-std::string GetSchedulerGroupName(pid_t tid);
-
 // Sets the name of the current thread. The name may be truncated to an
 // implementation-defined limit.
 void SetThreadName(const char* thread_name);
@@ -251,15 +200,6 @@
   }
 };
 
-template <typename Vector>
-void Push32(Vector* buf, int32_t data) {
-  static_assert(std::is_same<typename Vector::value_type, uint8_t>::value, "Invalid value type");
-  buf->push_back(data & 0xff);
-  buf->push_back((data >> 8) & 0xff);
-  buf->push_back((data >> 16) & 0xff);
-  buf->push_back((data >> 24) & 0xff);
-}
-
 inline bool TestBitmap(size_t idx, const uint8_t* bitmap) {
   return ((bitmap[idx / kBitsPerByte] >> (idx % kBitsPerByte)) & 0x01) != 0;
 }
@@ -334,12 +274,6 @@
   return dist(rng);
 }
 
-// All of the elements from one container to another.
-template <typename Dest, typename Src>
-static void AddAll(Dest& dest, const Src& src) {
-  dest.insert(src.begin(), src.end());
-}
-
 // Return the file size in bytes or -1 if the file does not exists.
 int64_t GetFileSizeBytes(const std::string& filename);
 
diff --git a/runtime/utils_test.cc b/runtime/utils_test.cc
index be4d394..82d92fc 100644
--- a/runtime/utils_test.cc
+++ b/runtime/utils_test.cc
@@ -273,58 +273,6 @@
   EXPECT_EQ(expected, actual);
 }
 
-TEST_F(UtilsTest, Join) {
-  std::vector<std::string> strings;
-
-  strings.clear();
-  EXPECT_EQ("", Join(strings, ':'));
-
-  strings.clear();
-  strings.push_back("foo");
-  EXPECT_EQ("foo", Join(strings, ':'));
-
-  strings.clear();
-  strings.push_back("");
-  strings.push_back("foo");
-  EXPECT_EQ(":foo", Join(strings, ':'));
-
-  strings.clear();
-  strings.push_back("foo");
-  strings.push_back("");
-  EXPECT_EQ("foo:", Join(strings, ':'));
-
-  strings.clear();
-  strings.push_back("");
-  strings.push_back("foo");
-  strings.push_back("");
-  EXPECT_EQ(":foo:", Join(strings, ':'));
-
-  strings.clear();
-  strings.push_back("foo");
-  strings.push_back("bar");
-  EXPECT_EQ("foo:bar", Join(strings, ':'));
-
-  strings.clear();
-  strings.push_back("foo");
-  strings.push_back("bar");
-  strings.push_back("baz");
-  EXPECT_EQ("foo:bar:baz", Join(strings, ':'));
-}
-
-TEST_F(UtilsTest, StartsWith) {
-  EXPECT_FALSE(StartsWith("foo", "bar"));
-  EXPECT_TRUE(StartsWith("foo", "foo"));
-  EXPECT_TRUE(StartsWith("food", "foo"));
-  EXPECT_FALSE(StartsWith("fo", "foo"));
-}
-
-TEST_F(UtilsTest, EndsWith) {
-  EXPECT_FALSE(EndsWith("foo", "bar"));
-  EXPECT_TRUE(EndsWith("foo", "foo"));
-  EXPECT_TRUE(EndsWith("foofoo", "foo"));
-  EXPECT_FALSE(EndsWith("oo", "foo"));
-}
-
 TEST_F(UtilsTest, GetDalvikCacheFilename) {
   std::string name;
   std::string error;
diff --git a/runtime/verifier/method_verifier_test.cc b/runtime/verifier/method_verifier_test.cc
index 52be2df..be5c18b 100644
--- a/runtime/verifier/method_verifier_test.cc
+++ b/runtime/verifier/method_verifier_test.cc
@@ -19,6 +19,8 @@
 #include <stdio.h>
 #include <memory>
 
+#include "android-base/strings.h"
+
 #include "class_linker-inl.h"
 #include "common_runtime_test.h"
 #include "dex_file.h"
@@ -42,7 +44,7 @@
     MethodVerifier::FailureKind failure = MethodVerifier::VerifyClass(
         self, klass, nullptr, true, HardFailLogMode::kLogWarning, &error_msg);
 
-    if (StartsWith(descriptor, "Ljava/lang/invoke")) {
+    if (android::base::StartsWith(descriptor, "Ljava/lang/invoke")) {
       ASSERT_TRUE(failure == MethodVerifier::kSoftFailure ||
                   failure == MethodVerifier::kNoFailure) << error_msg;
 
diff --git a/runtime/verifier/verifier_deps.cc b/runtime/verifier/verifier_deps.cc
index f9bff23..3af7c01 100644
--- a/runtime/verifier/verifier_deps.cc
+++ b/runtime/verifier/verifier_deps.cc
@@ -345,8 +345,15 @@
   // merely on no issues with linking (valid access flags, superclass and
   // implemented interfaces). If the class at any point reached the IsResolved
   // status, the requirement holds. This is guaranteed by RegTypeCache::ResolveClass.
-  DCHECK(destination != nullptr && !destination->IsPrimitive());
-  DCHECK(source != nullptr && !source->IsPrimitive());
+  DCHECK(destination != nullptr);
+  DCHECK(source != nullptr);
+
+  if (destination->IsPrimitive() || source->IsPrimitive()) {
+    // Primitive types are trivially non-assignable to anything else.
+    // We do not need to record trivial assignability, as it will
+    // not change across releases.
+    return;
+  }
 
   if (destination == source ||
       destination->IsObjectClass() ||
diff --git a/test/021-string2/expected.txt b/test/021-string2/expected.txt
index a9c6eb8..f269c7c 100644
--- a/test/021-string2/expected.txt
+++ b/test/021-string2/expected.txt
@@ -1,2 +1,6 @@
 Got expected npe
 OK
+ true true true true
+ true true true true
+ true true true true
+ true true true true
diff --git a/test/021-string2/src/Main.java b/test/021-string2/src/Main.java
index 51351e1..df0a3dd 100644
--- a/test/021-string2/src/Main.java
+++ b/test/021-string2/src/Main.java
@@ -92,6 +92,31 @@
 
         testCompareToAndEquals();
         testIndexOf();
+
+        String s0_0 = "\u0000";
+        String s0_1 = new String(s0_0);
+        String s0_2 = new String(new char[] { '\u0000' });
+        String s0_3 = s0_0 + "";
+        System.out.println(
+            " " + $noinline$equals(s0_0, s0_0) +
+            " " + $noinline$equals(s0_0, s0_1) +
+            " " + $noinline$equals(s0_0, s0_2) +
+            " " + $noinline$equals(s0_0, s0_3));
+        System.out.println(
+            " " + $noinline$equals(s0_1, s0_0) +
+            " " + $noinline$equals(s0_1, s0_1) +
+            " " + $noinline$equals(s0_1, s0_2) +
+            " " + $noinline$equals(s0_1, s0_3));
+        System.out.println(
+            " " + $noinline$equals(s0_2, s0_0) +
+            " " + $noinline$equals(s0_2, s0_1) +
+            " " + $noinline$equals(s0_2, s0_2) +
+            " " + $noinline$equals(s0_2, s0_3));
+        System.out.println(
+            " " + $noinline$equals(s0_3, s0_0) +
+            " " + $noinline$equals(s0_3, s0_1) +
+            " " + $noinline$equals(s0_3, s0_2) +
+            " " + $noinline$equals(s0_3, s0_3));
     }
 
     public static void testCompareToAndEquals() {
diff --git a/test/630-safecast-array/expected.txt b/test/630-safecast-array/expected.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/630-safecast-array/expected.txt
diff --git a/test/630-safecast-array/info.txt b/test/630-safecast-array/info.txt
new file mode 100644
index 0000000..e105167
--- /dev/null
+++ b/test/630-safecast-array/info.txt
@@ -0,0 +1,3 @@
+Regression test for vdex, which used to crash in AddAssignability
+called by the dex2dex compiler, not anticipating arrays of primitive
+type.
diff --git a/test/630-safecast-array/smali/Main.smali b/test/630-safecast-array/smali/Main.smali
new file mode 100644
index 0000000..a50f37c
--- /dev/null
+++ b/test/630-safecast-array/smali/Main.smali
@@ -0,0 +1,33 @@
+# Copyright 2016 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.
+
+.class LMain;
+.super Ljava/lang/Object;
+
+.method public static main([Ljava/lang/String;)V
+.registers 1
+    return-void
+.end method
+
+.method public static testPrimitiveDestination([Ljava/lang/String;)V
+.registers 1
+    check-cast p0, [B
+    return-void
+.end method
+
+.method public static testPrimitiveSource([B)V
+.registers 1
+    check-cast p0, [Ljava/lang/String;
+    return-void
+.end method
diff --git a/test/911-get-stack-trace/expected.txt b/test/911-get-stack-trace/expected.txt
index 20bab78..77c77ca 100644
--- a/test/911-get-stack-trace/expected.txt
+++ b/test/911-get-stack-trace/expected.txt
@@ -3,206 +3,206 @@
 ###################
 From top
 ---------
- getStackTrace (Ljava/lang/Thread;II)[Ljava/lang/String;
- print (Ljava/lang/Thread;II)V
- printOrWait (IILMain$ControlData;)V
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- doTest ()V
- main ([Ljava/lang/String;)V
+ getStackTrace (Ljava/lang/Thread;II)[[Ljava/lang/String; -1
+ print (Ljava/lang/Thread;II)V 0
+ printOrWait (IILMain$ControlData;)V 6
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 2
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ doTest ()V 38
+ main ([Ljava/lang/String;)V 6
 ---------
- print (Ljava/lang/Thread;II)V
- printOrWait (IILMain$ControlData;)V
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- doTest ()V
- main ([Ljava/lang/String;)V
+ print (Ljava/lang/Thread;II)V 0
+ printOrWait (IILMain$ControlData;)V 6
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 2
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ doTest ()V 42
+ main ([Ljava/lang/String;)V 6
 ---------
- getStackTrace (Ljava/lang/Thread;II)[Ljava/lang/String;
- print (Ljava/lang/Thread;II)V
- printOrWait (IILMain$ControlData;)V
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
+ getStackTrace (Ljava/lang/Thread;II)[[Ljava/lang/String; -1
+ print (Ljava/lang/Thread;II)V 0
+ printOrWait (IILMain$ControlData;)V 6
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 2
+ bar (IIILMain$ControlData;)J 0
 ---------
- printOrWait (IILMain$ControlData;)V
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- baz (IIILMain$ControlData;)Ljava/lang/Object;
+ printOrWait (IILMain$ControlData;)V 6
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 2
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
 From bottom
 ---------
- main ([Ljava/lang/String;)V
+ main ([Ljava/lang/String;)V 6
 ---------
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- doTest ()V
- main ([Ljava/lang/String;)V
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ doTest ()V 65
+ main ([Ljava/lang/String;)V 6
 ---------
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
 
 ################################
 ### Other thread (suspended) ###
 ################################
 From top
 ---------
- wait ()V
- printOrWait (IILMain$ControlData;)V
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- run ()V
+ wait ()V -1
+ printOrWait (IILMain$ControlData;)V 24
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 2
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ run ()V 4
 ---------
- printOrWait (IILMain$ControlData;)V
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- run ()V
+ printOrWait (IILMain$ControlData;)V 24
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 2
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ run ()V 4
 ---------
- wait ()V
- printOrWait (IILMain$ControlData;)V
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
+ wait ()V -1
+ printOrWait (IILMain$ControlData;)V 24
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 2
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
 ---------
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 2
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
+ bar (IIILMain$ControlData;)J 0
 From bottom
 ---------
- run ()V
+ run ()V 4
 ---------
- foo (IIILMain$ControlData;)I
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- run ()V
+ foo (IIILMain$ControlData;)I 0
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ run ()V 4
 ---------
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
+ bar (IIILMain$ControlData;)J 0
 
 ###########################
 ### Other thread (live) ###
 ###########################
 From top
 ---------
- printOrWait (IILMain$ControlData;)V
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- run ()V
+ printOrWait (IILMain$ControlData;)V 44
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 2
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ run ()V 4
 ---------
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- run ()V
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 2
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ run ()V 4
 ---------
- printOrWait (IILMain$ControlData;)V
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- baz (IIILMain$ControlData;)Ljava/lang/Object;
+ printOrWait (IILMain$ControlData;)V 44
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 2
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
 ---------
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
 From bottom
 ---------
- run ()V
+ run ()V 4
 ---------
- foo (IIILMain$ControlData;)I
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- run ()V
+ foo (IIILMain$ControlData;)I 0
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ run ()V 4
 ---------
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
- foo (IIILMain$ControlData;)I
- baz (IIILMain$ControlData;)Ljava/lang/Object;
- bar (IIILMain$ControlData;)J
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
+ bar (IIILMain$ControlData;)J 0
+ foo (IIILMain$ControlData;)I 0
+ baz (IIILMain$ControlData;)Ljava/lang/Object; 9
+ bar (IIILMain$ControlData;)J 0
diff --git a/test/911-get-stack-trace/src/Main.java b/test/911-get-stack-trace/src/Main.java
index df4501d..722bee8 100644
--- a/test/911-get-stack-trace/src/Main.java
+++ b/test/911-get-stack-trace/src/Main.java
@@ -109,13 +109,14 @@
     t.join();
   }
 
-  public static void print(String[] stack) {
+  public static void print(String[][] stack) {
     System.out.println("---------");
-    for (int i = 0; i < stack.length; i += 2) {
-      System.out.print(' ');
-      System.out.print(stack[i]);
-      System.out.print(' ');
-      System.out.println(stack[i + 1]);
+    for (String[] stackElement : stack) {
+      for (String part : stackElement) {
+        System.out.print(' ');
+        System.out.print(part);
+      }
+      System.out.println();
     }
   }
 
@@ -174,5 +175,5 @@
     volatile boolean stop = false;
   }
 
-  public static native String[] getStackTrace(Thread thread, int start, int max);
+  public static native String[][] getStackTrace(Thread thread, int start, int max);
 }
diff --git a/test/911-get-stack-trace/stack_trace.cc b/test/911-get-stack-trace/stack_trace.cc
index e7d9380..b5b5678 100644
--- a/test/911-get-stack-trace/stack_trace.cc
+++ b/test/911-get-stack-trace/stack_trace.cc
@@ -16,10 +16,13 @@
 
 #include "stack_trace.h"
 
+#include <inttypes.h>
 #include <memory>
 #include <stdio.h>
 
 #include "base/logging.h"
+#include "base/macros.h"
+#include "base/stringprintf.h"
 #include "jni.h"
 #include "openjdkjvmti/jvmti.h"
 #include "ScopedLocalRef.h"
@@ -44,8 +47,7 @@
     }
   }
 
-  auto callback = [&](jint i) -> jstring {
-    size_t method_index = static_cast<size_t>(i) / 2;
+  auto callback = [&](jint method_index) -> jobjectArray {
     char* name;
     char* sig;
     char* gen;
@@ -58,12 +60,20 @@
         return nullptr;
       }
     }
-    jstring callback_result;
-    if (i % 2 == 0) {
-      callback_result = name == nullptr ? nullptr : env->NewStringUTF(name);
-    } else {
-      callback_result = sig == nullptr ? nullptr : env->NewStringUTF(sig);
-    }
+
+    auto inner_callback = [&](jint component_index) -> jstring {
+      switch (component_index) {
+        case 0:
+          return (name == nullptr) ? nullptr : env->NewStringUTF(name);
+        case 1:
+          return (sig == nullptr) ? nullptr : env->NewStringUTF(sig);
+        case 2:
+          return env->NewStringUTF(StringPrintf("%" PRId64, frames[method_index].location).c_str());
+      }
+      LOG(FATAL) << "Unreachable";
+      UNREACHABLE();
+    };
+    jobjectArray inner_array = CreateObjectArray(env, 3, "java/lang/String", inner_callback);
 
     if (name != nullptr) {
       jvmti_env->Deallocate(reinterpret_cast<unsigned char*>(name));
@@ -74,9 +84,10 @@
     if (gen != nullptr) {
       jvmti_env->Deallocate(reinterpret_cast<unsigned char*>(gen));
     }
-    return callback_result;
+
+    return inner_array;
   };
-  return CreateObjectArray(env, 2 * count, "java/lang/String", callback);
+  return CreateObjectArray(env, count, "[Ljava/lang/String;", callback);
 }
 
 // Don't do anything
diff --git a/test/Android.run-test.mk b/test/Android.run-test.mk
index 2f1ca6d..b515130 100644
--- a/test/Android.run-test.mk
+++ b/test/Android.run-test.mk
@@ -514,9 +514,11 @@
 # Test 906 iterates the heap filtering with different options. No instances should be created
 # between those runs to be able to have precise checks.
 # Test 902 hits races with the JIT compiler. b/32821077
+# Test 626-const-class-linking can deadlock with JIT. b/33567581
 # Test 629 requires compilation.
 TEST_ART_BROKEN_JIT_RUN_TESTS := \
   137-cfi \
+  626-const-class-linking \
   629-vdex-speed \
   902-hello-transformation \
   904-object-allocation \