diff --git a/dex2oat/linker/image_writer.cc b/dex2oat/linker/image_writer.cc
index 305bf50..262b224 100644
--- a/dex2oat/linker/image_writer.cc
+++ b/dex2oat/linker/image_writer.cc
@@ -254,6 +254,14 @@
   }
 
   {
+    // All remaining weak interns are referenced. Promote them to strong interns. Whether a
+    // string was strongly or weakly interned, we shall make it strongly interned in the image.
+    TimingLogger::ScopedTiming t("PromoteInterns", timings);
+    ScopedObjectAccess soa(self);
+    Runtime::Current()->GetInternTable()->PromoteWeakToStrong();
+  }
+
+  {
     // Preload deterministic contents to the dex cache arrays we're going to write.
     ScopedObjectAccess soa(self);
     ObjPtr<mirror::ClassLoader> class_loader = GetAppClassLoader();
@@ -390,7 +398,7 @@
     ObjPtr<mirror::Object> referred_obj = root->AsMirrorPtr();
 
     if (curr_obj_->IsDexCache() &&
-        image_writer_.IsValidAppImageStringReference(referred_obj)) {
+        image_writer_.IsInternedAppImageStringReference(referred_obj)) {
       ++dex_cache_string_ref_counter_;
     }
   }
@@ -405,7 +413,7 @@
         obj->GetFieldObject<mirror::Object, kVerifyNone, kWithoutReadBarrier>(
             member_offset);
 
-    if (image_writer_.IsValidAppImageStringReference(referred_obj)) {
+    if (image_writer_.IsInternedAppImageStringReference(referred_obj)) {
       string_ref_info_.emplace_back(reinterpret_cast<uintptr_t>(obj.Ptr()),
                                     member_offset.Uint32Value());
     }
@@ -494,7 +502,7 @@
             ObjPtr<mirror::String> referred_string =
                 dex_cache->GetStrings()[index].load().object.Read();
 
-            if (IsValidAppImageStringReference(referred_string)) {
+            if (IsInternedAppImageStringReference(referred_string)) {
               ++string_info_collected;
               visitor.AddStringRefInfo(
                   SetDexCacheStringNativeRefTag(reinterpret_cast<uintptr_t>(object.Ptr())), index);
@@ -505,7 +513,7 @@
           GcRoot<mirror::String>* preresolved_strings = dex_cache->GetPreResolvedStrings();
           for (size_t index = 0; index < dex_cache->NumPreResolvedStrings(); ++index) {
             ObjPtr<mirror::String> referred_string = preresolved_strings[index].Read();
-            if (IsValidAppImageStringReference(referred_string)) {
+            if (IsInternedAppImageStringReference(referred_string)) {
               ++string_info_collected;
               visitor.AddStringRefInfo(SetDexCachePreResolvedStringNativeRefTag(
                 reinterpret_cast<uintptr_t>(object.Ptr())),
@@ -547,11 +555,11 @@
 
     if (curr_obj_->IsClass()) {
       class_violation_ = class_violation_ ||
-                         image_writer_.IsValidAppImageStringReference(referred_obj);
+                         image_writer_.IsInternedAppImageStringReference(referred_obj);
 
     } else if (curr_obj_->IsClassLoader()) {
       class_loader_violation_ = class_loader_violation_ ||
-                                image_writer_.IsValidAppImageStringReference(referred_obj);
+                                image_writer_.IsInternedAppImageStringReference(referred_obj);
 
     } else if (!curr_obj_->IsDexCache()) {
       LOG(FATAL) << "Dex2Oat:AppImage | " <<
@@ -640,10 +648,12 @@
             sfo_section_base);
 }
 
-bool ImageWriter::IsValidAppImageStringReference(ObjPtr<mirror::Object> referred_obj) const {
+bool ImageWriter::IsInternedAppImageStringReference(ObjPtr<mirror::Object> referred_obj) const {
   return referred_obj != nullptr &&
          !IsInBootImage(referred_obj.Ptr()) &&
-         referred_obj->IsString();
+         referred_obj->IsString() &&
+         referred_obj == Runtime::Current()->GetInternTable()->LookupStrong(
+             Thread::Current(), referred_obj->AsString());
 }
 
 // Helper class that erases the image file if it isn't properly flushed and closed.
@@ -1824,31 +1834,6 @@
   }
 }
 
-mirror::String* ImageWriter::FindInternedString(mirror::String* string) {
-  Thread* const self = Thread::Current();
-  for (const ImageInfo& image_info : image_infos_) {
-    const ObjPtr<mirror::String> found = image_info.intern_table_->LookupStrong(self, string);
-    DCHECK(image_info.intern_table_->LookupWeak(self, string) == nullptr)
-        << string->ToModifiedUtf8();
-    if (found != nullptr) {
-      return found.Ptr();
-    }
-  }
-  if (!compiler_options_.IsBootImage()) {
-    Runtime* const runtime = Runtime::Current();
-    ObjPtr<mirror::String> found = runtime->GetInternTable()->LookupStrong(self, string);
-    // If we found it in the runtime intern table it could either be in the boot image or interned
-    // during app image compilation. If it was in the boot image return that, otherwise return null
-    // since it belongs to another image space.
-    if (found != nullptr && runtime->GetHeap()->ObjectIsInBootImageSpace(found.Ptr())) {
-      return found.Ptr();
-    }
-    DCHECK(runtime->GetInternTable()->LookupWeak(self, string) == nullptr)
-        << string->ToModifiedUtf8();
-  }
-  return nullptr;
-}
-
 ObjPtr<mirror::ObjectArray<mirror::Object>> ImageWriter::CollectDexCaches(Thread* self,
                                                                           size_t oat_index) const {
   std::unordered_set<const DexFile*> image_dex_files;
@@ -1968,17 +1953,18 @@
     return obj;
   }
   if (!IsImageBinSlotAssigned(obj)) {
-    // We want to intern all strings but also assign offsets for the source string. Since the
-    // pruning phase has already happened, if we intern a string to one in the image we still
-    // end up copying an unreachable string.
     if (obj->IsString()) {
-      // Need to check if the string is already interned in another image info so that we don't have
-      // the intern tables of two different images contain the same string.
-      mirror::String* interned = FindInternedString(obj->AsString().Ptr());
-      if (interned == nullptr) {
-        // Not in another image space, insert to our table.
-        interned =
-            GetImageInfo(oat_index).intern_table_->InternStrongImageString(obj->AsString()).Ptr();
+      ObjPtr<mirror::String> str = obj->AsString();
+      InternTable* intern_table = Runtime::Current()->GetInternTable();
+      Thread* const self = Thread::Current();
+      if (intern_table->LookupStrong(self, str) == str) {
+        DCHECK(std::none_of(image_infos_.begin(),
+                            image_infos_.end(),
+                            [=](ImageInfo& info) REQUIRES_SHARED(Locks::mutator_lock_) {
+                              return info.intern_table_->LookupStrong(self, str) != nullptr;
+                            }));
+        ObjPtr<mirror::String> interned =
+            GetImageInfo(oat_index).intern_table_->InternStrongImageString(str);
         DCHECK_EQ(interned, obj);
       }
     } else if (obj->IsDexCache()) {
@@ -2114,13 +2100,6 @@
     AssignImageBinSlot(obj, oat_index);
     work_stack.emplace(obj, oat_index);
   }
-  if (obj->IsString()) {
-    // Always return the interned string if there exists one.
-    mirror::String* interned = FindInternedString(obj->AsString().Ptr());
-    if (interned != nullptr) {
-      return interned;
-    }
-  }
   return obj;
 }
 
diff --git a/dex2oat/linker/image_writer.h b/dex2oat/linker/image_writer.h
index cae28cf..f74a220 100644
--- a/dex2oat/linker/image_writer.h
+++ b/dex2oat/linker/image_writer.h
@@ -704,10 +704,6 @@
     return image_infos_[oat_index];
   }
 
-  // Find an already strong interned string in the other images or in the boot image. Used to
-  // remove duplicates in the multi image and app image case.
-  mirror::String* FindInternedString(mirror::String* string) REQUIRES_SHARED(Locks::mutator_lock_);
-
   // Return true if there already exists a native allocation for an object.
   bool NativeRelocationAssigned(void* ptr) const;
 
@@ -736,7 +732,7 @@
    *   - The referred-object is a Java String
    */
   ALWAYS_INLINE
-  bool IsValidAppImageStringReference(ObjPtr<mirror::Object> referred_obj) const
+  bool IsInternedAppImageStringReference(ObjPtr<mirror::Object> referred_obj) const
       REQUIRES_SHARED(Locks::mutator_lock_);
 
   const CompilerOptions& compiler_options_;
diff --git a/runtime/class_linker.cc b/runtime/class_linker.cc
index 8fed3ca..1343b16 100644
--- a/runtime/class_linker.cc
+++ b/runtime/class_linker.cc
@@ -1326,14 +1326,16 @@
 };
 
 /*
- * A class used to ensure that all strings in an AppImage have been properly
- * interned, and is only ever run in debug mode.
+ * A class used to ensure that all references to strings interned in an AppImage have been
+ * properly recorded in the interned references list, and is only ever run in debug mode.
  */
-class VerifyStringInterningVisitor {
+class CountInternedStringReferencesVisitor {
  public:
-  explicit VerifyStringInterningVisitor(const gc::space::ImageSpace& space) :
-      space_(space),
-      intern_table_(*Runtime::Current()->GetInternTable()) {}
+  CountInternedStringReferencesVisitor(const gc::space::ImageSpace& space,
+                                       const InternTable::UnorderedSet& image_interns)
+      : space_(space),
+        image_interns_(image_interns),
+        count_(0u) {}
 
   void TestObject(ObjPtr<mirror::Object> referred_obj) const
       REQUIRES_SHARED(Locks::mutator_lock_) {
@@ -1341,15 +1343,9 @@
         space_.HasAddress(referred_obj.Ptr()) &&
         referred_obj->IsString()) {
       ObjPtr<mirror::String> referred_str = referred_obj->AsString();
-
-      if (kIsDebugBuild) {
-        // Saved to temporary variables to aid in debugging.
-        ObjPtr<mirror::String> strong_lookup_result =
-            intern_table_.LookupStrong(Thread::Current(), referred_str);
-        ObjPtr<mirror::String> weak_lookup_result =
-            intern_table_.LookupWeak(Thread::Current(), referred_str);
-
-        DCHECK((strong_lookup_result == referred_str) || (weak_lookup_result == referred_str));
+      auto it = image_interns_.find(GcRoot<mirror::String>(referred_str));
+      if (it != image_interns_.end() && it->Read() == referred_str) {
+        ++count_;
       }
     }
   }
@@ -1372,33 +1368,35 @@
                   MemberOffset offset,
                   bool is_static ATTRIBUTE_UNUSED) const
       REQUIRES_SHARED(Locks::mutator_lock_) {
-    // There could be overlap between ranges, we must avoid visiting the same reference twice.
-    // Avoid the class field since we already fixed it up in FixupClassVisitor.
-    if (offset.Uint32Value() != mirror::Object::ClassOffset().Uint32Value()) {
-      // Updating images, don't do a read barrier.
-      ObjPtr<mirror::Object> referred_obj =
-          obj->GetFieldObject<mirror::Object, kVerifyNone, kWithoutReadBarrier>(offset);
-
-      TestObject(referred_obj);
-    }
+    // References within image or across images don't need a read barrier.
+    ObjPtr<mirror::Object> referred_obj =
+        obj->GetFieldObject<mirror::Object, kVerifyNone, kWithoutReadBarrier>(offset);
+    TestObject(referred_obj);
   }
 
   void operator()(ObjPtr<mirror::Class> klass ATTRIBUTE_UNUSED,
                   ObjPtr<mirror::Reference> ref) const
       REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::heap_bitmap_lock_) {
-    operator()(ref, mirror::Reference::ReferentOffset(), false);
+    operator()(ref, mirror::Reference::ReferentOffset(), /*is_static=*/ false);
   }
 
+  size_t GetCount() const {
+    return count_;
+  }
+
+ private:
   const gc::space::ImageSpace& space_;
-  InternTable& intern_table_;
+  const InternTable::UnorderedSet& image_interns_;
+  mutable size_t count_;  // Modified from the `const` callbacks.
 };
 
 /*
- * This function verifies that string references in the AppImage have been
- * properly interned.  To be considered properly interned a reference must
- * point to the same version of the string that the intern table does.
+ * This function counts references to strings interned in the AppImage.
+ * This is used in debug build to check against the number of the recorded references.
  */
-void VerifyStringInterning(gc::space::ImageSpace& space) REQUIRES_SHARED(Locks::mutator_lock_) {
+size_t CountInternedStringReferences(gc::space::ImageSpace& space,
+                                     const InternTable::UnorderedSet& image_interns)
+    REQUIRES_SHARED(Locks::mutator_lock_) {
   const gc::accounting::ContinuousSpaceBitmap* bitmap = space.GetMarkBitmap();
   const ImageHeader& image_header = space.GetImageHeader();
   const uint8_t* target_base = space.GetMemMap()->Begin();
@@ -1407,7 +1405,7 @@
   auto objects_begin = reinterpret_cast<uintptr_t>(target_base + objects_section.Offset());
   auto objects_end = reinterpret_cast<uintptr_t>(target_base + objects_section.End());
 
-  VerifyStringInterningVisitor visitor(space);
+  CountInternedStringReferencesVisitor visitor(space, image_interns);
   bitmap->VisitMarkedRange(objects_begin,
                            objects_end,
                            [&space, &visitor](mirror::Object* obj)
@@ -1427,6 +1425,119 @@
       }
     }
   });
+  return visitor.GetCount();
+}
+
+template <typename Visitor>
+static void VisitInternedStringReferences(
+    gc::space::ImageSpace* space,
+    bool use_preresolved_strings,
+    const Visitor& visitor) REQUIRES_SHARED(Locks::mutator_lock_) {
+  const uint8_t* target_base = space->Begin();
+  const ImageSection& sro_section =
+      space->GetImageHeader().GetImageStringReferenceOffsetsSection();
+  const size_t num_string_offsets = sro_section.Size() / sizeof(AppImageReferenceOffsetInfo);
+
+  VLOG(image)
+      << "ClassLinker:AppImage:InternStrings:imageStringReferenceOffsetCount = "
+      << num_string_offsets;
+
+  const auto* sro_base =
+      reinterpret_cast<const AppImageReferenceOffsetInfo*>(target_base + sro_section.Offset());
+
+  for (size_t offset_index = 0; offset_index < num_string_offsets; ++offset_index) {
+    uint32_t base_offset = sro_base[offset_index].first;
+
+    if (HasDexCacheStringNativeRefTag(base_offset)) {
+      base_offset = ClearDexCacheNativeRefTags(base_offset);
+      DCHECK_ALIGNED(base_offset, 2);
+
+      ObjPtr<mirror::DexCache> dex_cache =
+          reinterpret_cast<mirror::DexCache*>(space->Begin() + base_offset);
+      uint32_t string_slot_index = sro_base[offset_index].second;
+
+      mirror::StringDexCachePair source =
+          dex_cache->GetStrings()[string_slot_index].load(std::memory_order_relaxed);
+      ObjPtr<mirror::String> referred_string = source.object.Read();
+      DCHECK(referred_string != nullptr);
+
+      ObjPtr<mirror::String> visited = visitor(referred_string);
+      if (visited != referred_string) {
+        // Because we are not using a helper function we need to mark the GC card manually.
+        WriteBarrier::ForEveryFieldWrite(dex_cache);
+        dex_cache->GetStrings()[string_slot_index].store(
+            mirror::StringDexCachePair(visited, source.index), std::memory_order_relaxed);
+      }
+    } else if (HasDexCachePreResolvedStringNativeRefTag(base_offset)) {
+      if (use_preresolved_strings) {
+        base_offset = ClearDexCacheNativeRefTags(base_offset);
+        DCHECK_ALIGNED(base_offset, 2);
+
+        ObjPtr<mirror::DexCache> dex_cache =
+            reinterpret_cast<mirror::DexCache*>(space->Begin() + base_offset);
+        uint32_t string_index = sro_base[offset_index].second;
+
+        ObjPtr<mirror::String> referred_string =
+            dex_cache->GetPreResolvedStrings()[string_index].Read();
+        DCHECK(referred_string != nullptr);
+
+        ObjPtr<mirror::String> visited = visitor(referred_string);
+        if (visited != referred_string) {
+          // Because we are not using a helper function we need to mark the GC card manually.
+          WriteBarrier::ForEveryFieldWrite(dex_cache);
+          dex_cache->GetPreResolvedStrings()[string_index] = GcRoot<mirror::String>(visited);
+        }
+      }
+    } else {
+      uint32_t raw_member_offset = sro_base[offset_index].second;
+      DCHECK_ALIGNED(base_offset, 2);
+      DCHECK_ALIGNED(raw_member_offset, 2);
+
+      ObjPtr<mirror::Object> obj_ptr =
+          reinterpret_cast<mirror::Object*>(space->Begin() + base_offset);
+      MemberOffset member_offset(raw_member_offset);
+      ObjPtr<mirror::String> referred_string =
+          obj_ptr->GetFieldObject<mirror::String,
+                                  kVerifyNone,
+                                  kWithoutReadBarrier,
+                                  /* kIsVolatile= */ false>(member_offset);
+      DCHECK(referred_string != nullptr);
+
+      ObjPtr<mirror::String> visited = visitor(referred_string);
+      if (visited != referred_string) {
+        obj_ptr->SetFieldObject</* kTransactionActive= */ false,
+                                /* kCheckTransaction= */ false,
+                                kVerifyNone,
+                                /* kIsVolatile= */ false>(member_offset, visited);
+      }
+    }
+  }
+}
+
+static void VerifyInternedStringReferences(gc::space::ImageSpace* space)
+    REQUIRES_SHARED(Locks::mutator_lock_) {
+  InternTable::UnorderedSet image_interns;
+  const ImageSection& section = space->GetImageHeader().GetInternedStringsSection();
+  if (section.Size() > 0) {
+    size_t read_count;
+    const uint8_t* data = space->Begin() + section.Offset();
+    InternTable::UnorderedSet image_set(data, /*make_copy_of_data=*/ false, &read_count);
+    image_set.swap(image_interns);
+  }
+  size_t num_recorded_refs = 0u;
+  VisitInternedStringReferences(
+      space,
+      /*use_preresolved_strings=*/ true,
+      [&image_interns, &num_recorded_refs](ObjPtr<mirror::String> str)
+          REQUIRES_SHARED(Locks::mutator_lock_) {
+        auto it = image_interns.find(GcRoot<mirror::String>(str));
+        CHECK(it != image_interns.end());
+        CHECK(it->Read() == str);
+        ++num_recorded_refs;
+        return str;
+      });
+  size_t num_found_refs = CountInternedStringReferences(*space, image_interns);
+  CHECK_EQ(num_recorded_refs, num_found_refs);
 }
 
 // new_class_set is the set of classes that were read from the class table section in the image.
@@ -1445,12 +1556,6 @@
 
   static void HandleAppImageStrings(gc::space::ImageSpace* space)
       REQUIRES_SHARED(Locks::mutator_lock_);
-
-  static void UpdateInternStrings(
-      gc::space::ImageSpace* space,
-      bool use_preresolved_strings,
-      const SafeMap<mirror::String*, mirror::String*>& intern_remap)
-      REQUIRES_SHARED(Locks::mutator_lock_);
 };
 
 void AppImageLoadingHelper::Update(
@@ -1463,6 +1568,12 @@
     REQUIRES_SHARED(Locks::mutator_lock_) {
   ScopedTrace app_image_timing("AppImage:Updating");
 
+  if (kIsDebugBuild && ClassLinker::kAppImageMayContainStrings) {
+    // In debug build, verify the string references before applying
+    // the Runtime::LoadAppImageStartupCache() option.
+    VerifyInternedStringReferences(space);
+  }
+
   Thread* const self = Thread::Current();
   Runtime* const runtime = Runtime::Current();
   gc::Heap* const heap = runtime->GetHeap();
@@ -1535,10 +1646,6 @@
 
   if (ClassLinker::kAppImageMayContainStrings) {
     HandleAppImageStrings(space);
-
-    if (kIsDebugBuild) {
-      VerifyStringInterning(*space);
-    }
   }
 
   if (kVerifyArtMethodDeclaringClasses) {
@@ -1555,104 +1662,6 @@
   }
 }
 
-void AppImageLoadingHelper::UpdateInternStrings(
-    gc::space::ImageSpace* space,
-    bool use_preresolved_strings,
-    const SafeMap<mirror::String*, mirror::String*>& intern_remap) {
-  const uint8_t* target_base = space->Begin();
-  const ImageSection& sro_section =
-      space->GetImageHeader().GetImageStringReferenceOffsetsSection();
-  const size_t num_string_offsets = sro_section.Size() / sizeof(AppImageReferenceOffsetInfo);
-  InternTable* const intern_table = Runtime::Current()->GetInternTable();
-
-  VLOG(image)
-      << "ClassLinker:AppImage:InternStrings:imageStringReferenceOffsetCount = "
-      << num_string_offsets;
-
-  const auto* sro_base =
-      reinterpret_cast<const AppImageReferenceOffsetInfo*>(target_base + sro_section.Offset());
-
-  for (size_t offset_index = 0; offset_index < num_string_offsets; ++offset_index) {
-    uint32_t base_offset = sro_base[offset_index].first;
-
-    if (HasDexCacheStringNativeRefTag(base_offset)) {
-      base_offset = ClearDexCacheNativeRefTags(base_offset);
-      DCHECK_ALIGNED(base_offset, 2);
-
-      ObjPtr<mirror::DexCache> dex_cache =
-          reinterpret_cast<mirror::DexCache*>(space->Begin() + base_offset);
-      uint32_t string_index = sro_base[offset_index].second;
-
-      mirror::StringDexCachePair source = dex_cache->GetStrings()[string_index].load();
-      ObjPtr<mirror::String> referred_string = source.object.Read();
-      DCHECK(referred_string != nullptr);
-
-      auto it = intern_remap.find(referred_string.Ptr());
-      if (it != intern_remap.end()) {
-        // This doesn't use SetResolvedString to maintain consistency with how
-        // we load the string.  The index from the source string must be
-        // re-used due to the circular nature of the cache.  Because we are not
-        // using a helper function we need to mark the GC card manually.
-        WriteBarrier::ForEveryFieldWrite(dex_cache);
-        dex_cache->GetStrings()[string_index].store(
-            mirror::StringDexCachePair(it->second, source.index));
-      } else if (!use_preresolved_strings) {
-        dex_cache->GetStrings()[string_index].store(
-            mirror::StringDexCachePair(intern_table->InternStrong(referred_string), source.index));
-      }
-    } else if (HasDexCachePreResolvedStringNativeRefTag(base_offset)) {
-      if (use_preresolved_strings) {
-        base_offset = ClearDexCacheNativeRefTags(base_offset);
-        DCHECK_ALIGNED(base_offset, 2);
-
-        ObjPtr<mirror::DexCache> dex_cache =
-            reinterpret_cast<mirror::DexCache*>(space->Begin() + base_offset);
-        uint32_t string_index = sro_base[offset_index].second;
-
-        ObjPtr<mirror::String> referred_string =
-            dex_cache->GetPreResolvedStrings()[string_index].Read();
-        DCHECK(referred_string != nullptr);
-
-        auto it = intern_remap.find(referred_string.Ptr());
-        if (it != intern_remap.end()) {
-          // Because we are not using a helper function we need to mark the GC card manually.
-          WriteBarrier::ForEveryFieldWrite(dex_cache);
-          dex_cache->GetPreResolvedStrings()[string_index] = GcRoot<mirror::String>(it->second);
-        }
-      }
-    } else {
-      uint32_t raw_member_offset = sro_base[offset_index].second;
-      DCHECK_ALIGNED(base_offset, 2);
-      DCHECK_ALIGNED(raw_member_offset, 2);
-
-      ObjPtr<mirror::Object> obj_ptr =
-          reinterpret_cast<mirror::Object*>(space->Begin() + base_offset);
-      MemberOffset member_offset(raw_member_offset);
-      ObjPtr<mirror::String> referred_string =
-          obj_ptr->GetFieldObject<mirror::String,
-                                  kVerifyNone,
-                                  kWithoutReadBarrier,
-                                  /* kIsVolatile= */ false>(member_offset);
-      DCHECK(referred_string != nullptr);
-
-      auto it = intern_remap.find(referred_string.Ptr());
-      if (it != intern_remap.end()) {
-        obj_ptr->SetFieldObject</* kTransactionActive= */ false,
-                                /* kCheckTransaction= */ false,
-                                kVerifyNone,
-                                /* kIsVolatile= */ false>(member_offset, it->second);
-      } else if (!use_preresolved_strings) {
-        obj_ptr->SetFieldObject</* kTransactionActive= */ false,
-                                /* kCheckTransaction= */ false,
-                                kVerifyNone,
-                                /* kIsVolatile= */ false>(
-            member_offset,
-            intern_table->InternStrong(referred_string));
-      }
-    }
-  }
-}
-
 void AppImageLoadingHelper::HandleAppImageStrings(gc::space::ImageSpace* space) {
   // Iterate over the string reference offsets stored in the image and intern
   // the strings they point to.
@@ -1711,23 +1720,19 @@
       }
     }
   };
-
-  bool update_intern_strings;
-  if (load_startup_cache) {
-    VLOG(image) << "AppImage:load_startup_cache";
-    // Only add the intern table if we are using the startup cache. Otherwise,
-    // UpdateInternStrings adds the strings to the intern table.
-    intern_table->AddImageStringsToTable(space, func);
-    update_intern_strings = kIsDebugBuild || !intern_remap.empty();
+  intern_table->AddImageStringsToTable(space, func);
+  if (!intern_remap.empty()) {
     VLOG(image) << "AppImage:conflictingInternStrings = " << intern_remap.size();
-  } else {
-    update_intern_strings = true;
-  }
-
-  // For debug builds, always run the code below to get coverage.
-  if (update_intern_strings) {
-    // Slow path case is when there are conflicting intern strings to fix up.
-    UpdateInternStrings(space, /*use_preresolved_strings=*/ load_startup_cache, intern_remap);
+    VisitInternedStringReferences(
+        space,
+        load_startup_cache,
+        [&intern_remap](ObjPtr<mirror::String> str) REQUIRES_SHARED(Locks::mutator_lock_) {
+          auto it = intern_remap.find(str.Ptr());
+          if (it != intern_remap.end()) {
+            return ObjPtr<mirror::String>(it->second);
+          }
+          return str;
+        });
   }
 }
 
diff --git a/runtime/intern_table.cc b/runtime/intern_table.cc
index 9ac9927..3f728cb 100644
--- a/runtime/intern_table.cc
+++ b/runtime/intern_table.cc
@@ -275,6 +275,16 @@
   return Insert(s, true, true);
 }
 
+void InternTable::PromoteWeakToStrong() {
+  MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
+  DCHECK_EQ(weak_interns_.tables_.size(), 1u);
+  for (GcRoot<mirror::String>& entry : weak_interns_.tables_.front().set_) {
+    DCHECK(LookupStrongLocked(entry.Read()) == nullptr);
+    InsertStrong(entry.Read());
+  }
+  weak_interns_.tables_.front().set_.clear();
+}
+
 ObjPtr<mirror::String> InternTable::InternStrong(ObjPtr<mirror::String> s) {
   return Insert(s, true, false);
 }
diff --git a/runtime/intern_table.h b/runtime/intern_table.h
index 165d56c..745821d 100644
--- a/runtime/intern_table.h
+++ b/runtime/intern_table.h
@@ -119,6 +119,9 @@
   ObjPtr<mirror::String> InternStrongImageString(ObjPtr<mirror::String> s)
       REQUIRES_SHARED(Locks::mutator_lock_);
 
+  // Only used by image writer. Promote all weak interns to strong interns.
+  void PromoteWeakToStrong() REQUIRES_SHARED(Locks::mutator_lock_);
+
   // Interns a potentially new string in the 'strong' table. May cause thread suspension.
   ObjPtr<mirror::String> InternStrong(const char* utf8_data) REQUIRES_SHARED(Locks::mutator_lock_)
       REQUIRES(!Roles::uninterruptible_);
diff --git a/test/176-app-image-string/expected.txt b/test/176-app-image-string/expected.txt
new file mode 100644
index 0000000..2ae2839
--- /dev/null
+++ b/test/176-app-image-string/expected.txt
@@ -0,0 +1 @@
+pass
diff --git a/test/176-app-image-string/info.txt b/test/176-app-image-string/info.txt
new file mode 100644
index 0000000..ca0951c
--- /dev/null
+++ b/test/176-app-image-string/info.txt
@@ -0,0 +1 @@
+Regression test for strings being wrongly interned in images.
diff --git a/test/176-app-image-string/profile b/test/176-app-image-string/profile
new file mode 100644
index 0000000..6d9e6c8
--- /dev/null
+++ b/test/176-app-image-string/profile
@@ -0,0 +1 @@
+LMain;
diff --git a/test/176-app-image-string/run b/test/176-app-image-string/run
new file mode 100644
index 0000000..52d2b5f
--- /dev/null
+++ b/test/176-app-image-string/run
@@ -0,0 +1,17 @@
+#!/bin/bash
+#
+# Copyright (C) 2019 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.
+
+exec ${RUN} $@ --profile
diff --git a/test/176-app-image-string/src/Main.java b/test/176-app-image-string/src/Main.java
new file mode 100644
index 0000000..f842c10
--- /dev/null
+++ b/test/176-app-image-string/src/Main.java
@@ -0,0 +1,27 @@
+/*
+ * Copyright (C) 2019 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.
+ */
+
+public class Main {
+    public static final String internedString = "test-string";
+    public static final String nonInternedCopy = new String("test-string");
+
+    public static void main(String args[]) throws Exception {
+        if (internedString == nonInternedCopy) {
+            throw new AssertionError();
+        }
+        System.out.println("pass");
+    }
+}