diff --git a/compiler/optimizing/code_generator_arm64.cc b/compiler/optimizing/code_generator_arm64.cc
index ff99a3e..3086882 100644
--- a/compiler/optimizing/code_generator_arm64.cc
+++ b/compiler/optimizing/code_generator_arm64.cc
@@ -4840,7 +4840,6 @@
       // Add ADRP with its PC-relative String .bss entry patch.
       const DexFile& dex_file = load->GetDexFile();
       const dex::StringIndex string_index = load->GetStringIndex();
-      DCHECK(!codegen_->GetCompilerOptions().IsBootImage());
       Register temp = XRegisterFrom(out_loc);
       vixl::aarch64::Label* adrp_label = codegen_->NewStringBssEntryPatch(dex_file, string_index);
       codegen_->EmitAdrpPlaceholder(adrp_label, temp);
diff --git a/compiler/optimizing/code_generator_arm_vixl.cc b/compiler/optimizing/code_generator_arm_vixl.cc
index 9c155f8..c8db3d6 100644
--- a/compiler/optimizing/code_generator_arm_vixl.cc
+++ b/compiler/optimizing/code_generator_arm_vixl.cc
@@ -7246,7 +7246,6 @@
       return;
     }
     case HLoadString::LoadKind::kBssEntry: {
-      DCHECK(!codegen_->GetCompilerOptions().IsBootImage());
       CodeGeneratorARMVIXL::PcRelativePatchInfo* labels =
           codegen_->NewStringBssEntryPatch(load->GetDexFile(), load->GetStringIndex());
       codegen_->EmitMovwMovtPlaceholder(labels, out);
diff --git a/compiler/optimizing/code_generator_mips.cc b/compiler/optimizing/code_generator_mips.cc
index f7f37db..72334af 100644
--- a/compiler/optimizing/code_generator_mips.cc
+++ b/compiler/optimizing/code_generator_mips.cc
@@ -8449,7 +8449,6 @@
       return;
     }
     case HLoadString::LoadKind::kBssEntry: {
-      DCHECK(!codegen_->GetCompilerOptions().IsBootImage());
       CodeGeneratorMIPS::PcRelativePatchInfo* info_high =
           codegen_->NewStringBssEntryPatch(load->GetDexFile(), load->GetStringIndex());
       CodeGeneratorMIPS::PcRelativePatchInfo* info_low =
diff --git a/compiler/optimizing/code_generator_mips64.cc b/compiler/optimizing/code_generator_mips64.cc
index 8b6328f..0d3cb3b 100644
--- a/compiler/optimizing/code_generator_mips64.cc
+++ b/compiler/optimizing/code_generator_mips64.cc
@@ -6442,7 +6442,6 @@
       return;
     }
     case HLoadString::LoadKind::kBssEntry: {
-      DCHECK(!codegen_->GetCompilerOptions().IsBootImage());
       CodeGeneratorMIPS64::PcRelativePatchInfo* info_high =
           codegen_->NewStringBssEntryPatch(load->GetDexFile(), load->GetStringIndex());
       CodeGeneratorMIPS64::PcRelativePatchInfo* info_low =
diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc
index 766ff78..95118b0 100644
--- a/compiler/optimizing/code_generator_x86.cc
+++ b/compiler/optimizing/code_generator_x86.cc
@@ -4991,7 +4991,6 @@
 }
 
 Label* CodeGeneratorX86::NewStringBssEntryPatch(HLoadString* load_string) {
-  DCHECK(!GetCompilerOptions().IsBootImage());
   HX86ComputeBaseMethodAddress* method_address =
       load_string->InputAt(0)->AsX86ComputeBaseMethodAddress();
   string_bss_entry_patches_.emplace_back(
diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc
index 67a2aa5..7c293b8 100644
--- a/compiler/optimizing/code_generator_x86_64.cc
+++ b/compiler/optimizing/code_generator_x86_64.cc
@@ -1115,7 +1115,6 @@
 }
 
 Label* CodeGeneratorX86_64::NewStringBssEntryPatch(HLoadString* load_string) {
-  DCHECK(!GetCompilerOptions().IsBootImage());
   string_bss_entry_patches_.emplace_back(
       &load_string->GetDexFile(), load_string->GetStringIndex().index_);
   return &string_bss_entry_patches_.back().label;
diff --git a/compiler/optimizing/sharpening.cc b/compiler/optimizing/sharpening.cc
index 885a08d..8637db1 100644
--- a/compiler/optimizing/sharpening.cc
+++ b/compiler/optimizing/sharpening.cc
@@ -303,11 +303,26 @@
       // Compiling boot image. Resolve the string and allocate it if needed, to ensure
       // the string will be added to the boot image.
       DCHECK(!runtime->UseJitCompilation());
-      string = class_linker->ResolveString(string_index, dex_cache);
-      CHECK(string != nullptr);
       if (compiler_options.GetCompilePic()) {
         DCHECK(ContainsElement(compiler_options.GetDexFilesForOatFile(), &dex_file));
-        desired_load_kind = HLoadString::LoadKind::kBootImageLinkTimePcRelative;
+        if (compiler_options.IsForceDeterminism()) {
+          // Strings for methods we're compiling should be pre-resolved but Strings in inlined
+          // methods may not be if these inlined methods are not in the boot image profile.
+          // Multiple threads allocating new Strings can cause non-deterministic boot image
+          // because of the image relying on the order of GC roots we walk. (We could fix that
+          // by ordering the roots we walk in ImageWriter.) Therefore we avoid allocating these
+          // strings even if that results in omitting them from the boot image and using the
+          // sub-optimal load kind kBssEntry.
+          string = class_linker->LookupString(string_index, dex_cache.Get());
+        } else {
+          string = class_linker->ResolveString(string_index, dex_cache);
+          CHECK(string != nullptr);
+        }
+        if (string != nullptr) {
+          desired_load_kind = HLoadString::LoadKind::kBootImageLinkTimePcRelative;
+        } else {
+          desired_load_kind = HLoadString::LoadKind::kBssEntry;
+        }
       } else {
         // Test configuration, do not sharpen.
         desired_load_kind = HLoadString::LoadKind::kRuntimeCall;
diff --git a/dex2oat/linker/oat_writer.cc b/dex2oat/linker/oat_writer.cc
index be9a0cb..f7de593 100644
--- a/dex2oat/linker/oat_writer.cc
+++ b/dex2oat/linker/oat_writer.cc
@@ -2309,9 +2309,6 @@
   }
 
   DCHECK_EQ(bss_size_, 0u);
-  if (GetCompilerOptions().IsBootImage()) {
-    DCHECK(bss_string_entries_.empty());
-  }
   if (bss_method_entries_.empty() &&
       bss_type_entries_.empty() &&
       bss_string_entries_.empty()) {