diff --git a/runtime/class_linker.cc b/runtime/class_linker.cc
index f2c2f03..32ad422 100644
--- a/runtime/class_linker.cc
+++ b/runtime/class_linker.cc
@@ -7024,6 +7024,23 @@
   return string;
 }
 
+mirror::String* ClassLinker::LookupString(const DexFile& dex_file,
+                                          uint32_t string_idx,
+                                          Handle<mirror::DexCache> dex_cache) {
+  DCHECK(dex_cache.Get() != nullptr);
+  mirror::String* resolved = dex_cache->GetResolvedString(string_idx);
+  if (resolved != nullptr) {
+    return resolved;
+  }
+  uint32_t utf16_length;
+  const char* utf8_data = dex_file.StringDataAndUtf16LengthByIdx(string_idx, &utf16_length);
+  mirror::String* string = intern_table_->LookupStrong(Thread::Current(), utf16_length, utf8_data);
+  if (string != nullptr) {
+    dex_cache->SetResolvedString(string_idx, string);
+  }
+  return string;
+}
+
 mirror::Class* ClassLinker::ResolveType(const DexFile& dex_file,
                                         uint16_t type_idx,
                                         mirror::Class* referrer) {
diff --git a/runtime/class_linker.h b/runtime/class_linker.h
index 886f586..b4b7f34 100644
--- a/runtime/class_linker.h
+++ b/runtime/class_linker.h
@@ -247,6 +247,12 @@
                                 Handle<mirror::DexCache> dex_cache)
       SHARED_REQUIRES(Locks::mutator_lock_);
 
+  // Find a String with the given index from the DexFile, storing the
+  // result in the DexCache if found. Return null if not found.
+  mirror::String* LookupString(const DexFile& dex_file, uint32_t string_idx,
+                               Handle<mirror::DexCache> dex_cache)
+      SHARED_REQUIRES(Locks::mutator_lock_);
+
   // Resolve a Type with the given index from the DexFile, storing the
   // result in the DexCache. The referrer is used to identity the
   // target DexCache and ClassLoader to use for resolution.
diff --git a/runtime/intern_table.cc b/runtime/intern_table.cc
index 74a2532..79f24a8 100644
--- a/runtime/intern_table.cc
+++ b/runtime/intern_table.cc
@@ -97,6 +97,17 @@
   return LookupStrongLocked(s);
 }
 
+mirror::String* InternTable::LookupStrong(Thread* self,
+                                          uint32_t utf16_length,
+                                          const char* utf8_data) {
+  DCHECK_EQ(utf16_length, CountModifiedUtf8Chars(utf8_data));
+  Utf8String string(utf16_length,
+                    utf8_data,
+                    ComputeUtf16HashFromModifiedUtf8(utf8_data, utf16_length));
+  MutexLock mu(self, *Locks::intern_table_lock_);
+  return strong_interns_.Find(string);
+}
+
 mirror::String* InternTable::LookupWeakLocked(mirror::String* s) {
   return weak_interns_.Find(s);
 }
@@ -365,6 +376,20 @@
   return a.Read()->Equals(b.Read());
 }
 
+bool InternTable::StringHashEquals::operator()(const GcRoot<mirror::String>& a,
+                                               const Utf8String& b) const {
+  if (kIsDebugBuild) {
+    Locks::mutator_lock_->AssertSharedHeld(Thread::Current());
+  }
+  mirror::String* a_string = a.Read();
+  uint32_t a_length = static_cast<uint32_t>(a_string->GetLength());
+  if (a_length != b.GetUtf16Length()) {
+    return false;
+  }
+  const uint16_t* a_value = a_string->GetValue();
+  return CompareModifiedUtf8ToUtf16AsCodePointValues(b.GetUtf8Data(), a_value, a_length) == 0;
+}
+
 size_t InternTable::Table::AddTableFromMemory(const uint8_t* ptr) {
   size_t read_count = 0;
   UnorderedSet set(ptr, /*make copy*/false, &read_count);
@@ -421,6 +446,17 @@
   return nullptr;
 }
 
+mirror::String* InternTable::Table::Find(const Utf8String& string) {
+  Locks::intern_table_lock_->AssertHeld(Thread::Current());
+  for (UnorderedSet& table : tables_) {
+    auto it = table.Find(string);
+    if (it != table.end()) {
+      return it->Read();
+    }
+  }
+  return nullptr;
+}
+
 void InternTable::Table::AddNewTable() {
   tables_.push_back(UnorderedSet());
 }
diff --git a/runtime/intern_table.h b/runtime/intern_table.h
index 274f5ad..f845de5 100644
--- a/runtime/intern_table.h
+++ b/runtime/intern_table.h
@@ -88,6 +88,9 @@
   mirror::String* LookupStrong(Thread* self, mirror::String* s)
       REQUIRES(!Locks::intern_table_lock_)
       SHARED_REQUIRES(Locks::mutator_lock_);
+  mirror::String* LookupStrong(Thread* self, uint32_t utf16_length, const char* utf8_data)
+      REQUIRES(!Locks::intern_table_lock_)
+      SHARED_REQUIRES(Locks::mutator_lock_);
 
   // Lookup a weak intern, returns null if not found.
   mirror::String* LookupWeak(Thread* self, mirror::String* s)
@@ -136,11 +139,32 @@
       REQUIRES(!Locks::intern_table_lock_);
 
  private:
+  // Modified UTF-8-encoded string treated as UTF16.
+  class Utf8String {
+   public:
+    Utf8String(uint32_t utf16_length, const char* utf8_data, int32_t hash)
+        : hash_(hash), utf16_length_(utf16_length), utf8_data_(utf8_data) { }
+
+    int32_t GetHash() const { return hash_; }
+    uint32_t GetUtf16Length() const { return utf16_length_; }
+    const char* GetUtf8Data() const { return utf8_data_; }
+
+   private:
+    int32_t hash_;
+    uint32_t utf16_length_;
+    const char* utf8_data_;
+  };
+
   class StringHashEquals {
    public:
     std::size_t operator()(const GcRoot<mirror::String>& root) const NO_THREAD_SAFETY_ANALYSIS;
     bool operator()(const GcRoot<mirror::String>& a, const GcRoot<mirror::String>& b) const
         NO_THREAD_SAFETY_ANALYSIS;
+
+    // Utf8String can be used for lookup.
+    std::size_t operator()(const Utf8String& key) const { return key.GetHash(); }
+    bool operator()(const GcRoot<mirror::String>& a, const Utf8String& b) const
+        NO_THREAD_SAFETY_ANALYSIS;
   };
   class GcRootEmptyFn {
    public:
@@ -159,6 +183,8 @@
     Table();
     mirror::String* Find(mirror::String* s) SHARED_REQUIRES(Locks::mutator_lock_)
         REQUIRES(Locks::intern_table_lock_);
+    mirror::String* Find(const Utf8String& string) SHARED_REQUIRES(Locks::mutator_lock_)
+        REQUIRES(Locks::intern_table_lock_);
     void Insert(mirror::String* s) SHARED_REQUIRES(Locks::mutator_lock_)
         REQUIRES(Locks::intern_table_lock_);
     void Remove(mirror::String* s)
diff --git a/runtime/intern_table_test.cc b/runtime/intern_table_test.cc
index b60b32d..fe78bf2 100644
--- a/runtime/intern_table_test.cc
+++ b/runtime/intern_table_test.cc
@@ -35,12 +35,14 @@
   Handle<mirror::String> foo_3(
       hs.NewHandle(mirror::String::AllocFromModifiedUtf8(soa.Self(), "foo")));
   Handle<mirror::String> bar(hs.NewHandle(intern_table.InternStrong(3, "bar")));
+  ASSERT_TRUE(foo_1.Get() != nullptr);
+  ASSERT_TRUE(foo_2.Get() != nullptr);
+  ASSERT_TRUE(foo_3.Get() != nullptr);
+  ASSERT_TRUE(bar.Get() != nullptr);
+  EXPECT_EQ(foo_1.Get(), foo_2.Get());
   EXPECT_TRUE(foo_1->Equals("foo"));
   EXPECT_TRUE(foo_2->Equals("foo"));
   EXPECT_TRUE(foo_3->Equals("foo"));
-  EXPECT_TRUE(foo_1.Get() != nullptr);
-  EXPECT_TRUE(foo_2.Get() != nullptr);
-  EXPECT_EQ(foo_1.Get(), foo_2.Get());
   EXPECT_NE(foo_1.Get(), bar.Get());
   EXPECT_NE(foo_2.Get(), bar.Get());
   EXPECT_NE(foo_3.Get(), bar.Get());
@@ -175,4 +177,39 @@
   }
 }
 
+TEST_F(InternTableTest, LookupStrong) {
+  ScopedObjectAccess soa(Thread::Current());
+  InternTable intern_table;
+  StackHandleScope<3> hs(soa.Self());
+  Handle<mirror::String> foo(hs.NewHandle(intern_table.InternStrong(3, "foo")));
+  Handle<mirror::String> bar(hs.NewHandle(intern_table.InternStrong(3, "bar")));
+  Handle<mirror::String> foobar(hs.NewHandle(intern_table.InternStrong(6, "foobar")));
+  ASSERT_TRUE(foo.Get() != nullptr);
+  ASSERT_TRUE(bar.Get() != nullptr);
+  ASSERT_TRUE(foobar.Get() != nullptr);
+  ASSERT_TRUE(foo->Equals("foo"));
+  ASSERT_TRUE(bar->Equals("bar"));
+  ASSERT_TRUE(foobar->Equals("foobar"));
+  ASSERT_NE(foo.Get(), bar.Get());
+  ASSERT_NE(foo.Get(), foobar.Get());
+  ASSERT_NE(bar.Get(), foobar.Get());
+  mirror::String* lookup_foo = intern_table.LookupStrong(soa.Self(), 3, "foo");
+  EXPECT_EQ(lookup_foo, foo.Get());
+  mirror::String* lookup_bar = intern_table.LookupStrong(soa.Self(), 3, "bar");
+  EXPECT_EQ(lookup_bar, bar.Get());
+  mirror::String* lookup_foobar = intern_table.LookupStrong(soa.Self(), 6, "foobar");
+  EXPECT_EQ(lookup_foobar, foobar.Get());
+  mirror::String* lookup_foox = intern_table.LookupStrong(soa.Self(), 4, "foox");
+  EXPECT_TRUE(lookup_foox == nullptr);
+  mirror::String* lookup_fooba = intern_table.LookupStrong(soa.Self(), 5, "fooba");
+  EXPECT_TRUE(lookup_fooba == nullptr);
+  mirror::String* lookup_foobaR = intern_table.LookupStrong(soa.Self(), 6, "foobaR");
+  EXPECT_TRUE(lookup_foobaR == nullptr);
+  // Try a hash conflict.
+  ASSERT_EQ(ComputeUtf16HashFromModifiedUtf8("foobar", 6),
+            ComputeUtf16HashFromModifiedUtf8("foobbS", 6));
+  mirror::String* lookup_foobbS = intern_table.LookupStrong(soa.Self(), 6, "foobbS");
+  EXPECT_TRUE(lookup_foobbS == nullptr);
+}
+
 }  // namespace art
diff --git a/runtime/runtime.cc b/runtime/runtime.cc
index 8a38f3a..630d101 100644
--- a/runtime/runtime.cc
+++ b/runtime/runtime.cc
@@ -554,19 +554,6 @@
 
   started_ = true;
 
-  // Use !IsAotCompiler so that we get test coverage, tests are never the zygote.
-  if (!IsAotCompiler()) {
-    ScopedObjectAccess soa(self);
-    {
-      ScopedTrace trace2("AddImageStringsToTable");
-      GetInternTable()->AddImagesStringsToTable(heap_->GetBootImageSpaces());
-    }
-    {
-      ScopedTrace trace2("MoveImageClassesToClassTable");
-      GetClassLinker()->AddBootImageClassesToClassTable();
-    }
-  }
-
   if (jit_options_->UseJIT()) {
     std::string error_msg;
     if (!IsZygote()) {
@@ -1140,6 +1127,14 @@
       }
       boot_class_path_string_ = Join(dex_locations, ':');
     }
+    {
+      ScopedTrace trace2("AddImageStringsToTable");
+      GetInternTable()->AddImagesStringsToTable(heap_->GetBootImageSpaces());
+    }
+    {
+      ScopedTrace trace2("MoveImageClassesToClassTable");
+      GetClassLinker()->AddBootImageClassesToClassTable();
+    }
   } else {
     std::vector<std::string> dex_filenames;
     Split(boot_class_path_string_, ':', &dex_filenames);
diff --git a/runtime/safe_map.h b/runtime/safe_map.h
index 0e5b503..49f80f3 100644
--- a/runtime/safe_map.h
+++ b/runtime/safe_map.h
@@ -19,6 +19,7 @@
 
 #include <map>
 #include <memory>
+#include <type_traits>
 
 #include "base/allocator.h"
 #include "base/logging.h"
@@ -124,6 +125,18 @@
     return result.first;
   }
 
+  template <typename CreateFn>
+  V GetOrCreate(const K& k, CreateFn create) {
+    static_assert(std::is_same<V, typename std::result_of<CreateFn()>::type>::value,
+                  "Argument `create` should return a value of type V.");
+    auto lb = lower_bound(k);
+    if (lb != end() && !key_comp()(k, lb->first)) {
+      return lb->second;
+    }
+    auto it = PutBefore(lb, k, create());
+    return it->second;
+  }
+
   bool Equals(const Self& rhs) const {
     return map_ == rhs.map_;
   }
diff --git a/runtime/utf.cc b/runtime/utf.cc
index a2d6363..5e9fdf7 100644
--- a/runtime/utf.cc
+++ b/runtime/utf.cc
@@ -178,6 +178,23 @@
   return static_cast<int32_t>(hash);
 }
 
+int32_t ComputeUtf16HashFromModifiedUtf8(const char* utf8, size_t utf16_length) {
+  uint32_t hash = 0;
+  while (utf16_length != 0u) {
+    const uint32_t pair = GetUtf16FromUtf8(&utf8);
+    const uint16_t first = GetLeadingUtf16Char(pair);
+    hash = hash * 31 + first;
+    --utf16_length;
+    const uint16_t second = GetTrailingUtf16Char(pair);
+    if (second != 0) {
+      hash = hash * 31 + second;
+      DCHECK_NE(utf16_length, 0u);
+      --utf16_length;
+    }
+  }
+  return static_cast<int32_t>(hash);
+}
+
 uint32_t ComputeModifiedUtf8Hash(const char* chars) {
   uint32_t hash = 0;
   while (*chars != '\0') {
diff --git a/runtime/utf.h b/runtime/utf.h
index 4abd605..27d2fd5 100644
--- a/runtime/utf.h
+++ b/runtime/utf.h
@@ -83,6 +83,7 @@
 int32_t ComputeUtf16Hash(mirror::CharArray* chars, int32_t offset, size_t char_count)
     SHARED_REQUIRES(Locks::mutator_lock_);
 int32_t ComputeUtf16Hash(const uint16_t* chars, size_t char_count);
+int32_t ComputeUtf16HashFromModifiedUtf8(const char* utf8, size_t utf16_length);
 
 // Compute a hash code of a modified UTF-8 string. Not the standard java hash since it returns a
 // uint32_t and hashes individual chars instead of codepoint words.