diff --git a/compiler/optimizing/builder.cc b/compiler/optimizing/builder.cc
index fe52c44..31d6412 100644
--- a/compiler/optimizing/builder.cc
+++ b/compiler/optimizing/builder.cc
@@ -756,6 +756,35 @@
   current_block_ = nullptr;
 }
 
+void HGraphBuilder::PotentiallySimplifyFakeString(uint16_t original_dex_register,
+                                                  uint32_t dex_pc,
+                                                  HInvoke* actual_string) {
+  if (!graph_->IsDebuggable()) {
+    // Notify that we cannot compile with baseline. The dex registers aliasing
+    // with `original_dex_register` will be handled when we optimize
+    // (see HInstructionSimplifer::VisitFakeString).
+    can_use_baseline_for_string_init_ = false;
+    return;
+  }
+  const VerifiedMethod* verified_method =
+      compiler_driver_->GetVerifiedMethod(dex_file_, dex_compilation_unit_->GetDexMethodIndex());
+  if (verified_method != nullptr) {
+    UpdateLocal(original_dex_register, actual_string);
+    const SafeMap<uint32_t, std::set<uint32_t>>& string_init_map =
+        verified_method->GetStringInitPcRegMap();
+    auto map_it = string_init_map.find(dex_pc);
+    if (map_it != string_init_map.end()) {
+      std::set<uint32_t> reg_set = map_it->second;
+      for (auto set_it = reg_set.begin(); set_it != reg_set.end(); ++set_it) {
+        HInstruction* load_local = LoadLocal(original_dex_register, Primitive::kPrimNot);
+        UpdateLocal(*set_it, load_local);
+      }
+    }
+  } else {
+    can_use_baseline_for_string_init_ = false;
+  }
+}
+
 bool HGraphBuilder::BuildInvoke(const Instruction& instruction,
                                 uint32_t dex_pc,
                                 uint32_t method_idx,
@@ -997,34 +1026,23 @@
   if (clinit_check_requirement == HInvokeStaticOrDirect::ClinitCheckRequirement::kExplicit) {
     // Add the class initialization check as last input of `invoke`.
     DCHECK(clinit_check != nullptr);
+    DCHECK(!is_string_init);
     invoke->SetArgumentAt(argument_index, clinit_check);
+    argument_index++;
   }
 
-  current_block_->AddInstruction(invoke);
-  latest_result_ = invoke;
-
   // Add move-result for StringFactory method.
   if (is_string_init) {
     uint32_t orig_this_reg = is_range ? register_index : args[0];
-    UpdateLocal(orig_this_reg, invoke);
-    const VerifiedMethod* verified_method =
-        compiler_driver_->GetVerifiedMethod(dex_file_, dex_compilation_unit_->GetDexMethodIndex());
-    if (verified_method == nullptr) {
-      LOG(WARNING) << "No verified method for method calling String.<init>: "
-                   << PrettyMethod(dex_compilation_unit_->GetDexMethodIndex(), *dex_file_);
-      return false;
-    }
-    const SafeMap<uint32_t, std::set<uint32_t>>& string_init_map =
-        verified_method->GetStringInitPcRegMap();
-    auto map_it = string_init_map.find(dex_pc);
-    if (map_it != string_init_map.end()) {
-      std::set<uint32_t> reg_set = map_it->second;
-      for (auto set_it = reg_set.begin(); set_it != reg_set.end(); ++set_it) {
-        HInstruction* load_local = LoadLocal(orig_this_reg, Primitive::kPrimNot);
-        UpdateLocal(*set_it, load_local);
-      }
-    }
+    HInstruction* fake_string = LoadLocal(orig_this_reg, Primitive::kPrimNot);
+    invoke->SetArgumentAt(argument_index, fake_string);
+    current_block_->AddInstruction(invoke);
+    PotentiallySimplifyFakeString(orig_this_reg, dex_pc, invoke);
+  } else {
+    current_block_->AddInstruction(invoke);
   }
+  latest_result_ = invoke;
+
   return true;
 }
 
@@ -2239,10 +2257,10 @@
     case Instruction::NEW_INSTANCE: {
       uint16_t type_index = instruction.VRegB_21c();
       if (compiler_driver_->IsStringTypeIndex(type_index, dex_file_)) {
-        // Turn new-instance of string into a const 0.
         int32_t register_index = instruction.VRegA();
-        HNullConstant* constant = graph_->GetNullConstant();
-        UpdateLocal(register_index, constant);
+        HFakeString* fake_string = new (arena_) HFakeString();
+        current_block_->AddInstruction(fake_string);
+        UpdateLocal(register_index, fake_string);
       } else {
         QuickEntrypointEnum entrypoint = NeedsAccessCheck(type_index)
             ? kQuickAllocObjectWithAccessCheck
diff --git a/compiler/optimizing/builder.h b/compiler/optimizing/builder.h
index 7098eb8..76610f5 100644
--- a/compiler/optimizing/builder.h
+++ b/compiler/optimizing/builder.h
@@ -54,6 +54,7 @@
         return_type_(Primitive::GetType(dex_compilation_unit_->GetShorty()[0])),
         code_start_(nullptr),
         latest_result_(nullptr),
+        can_use_baseline_for_string_init_(true),
         compilation_stats_(compiler_stats) {}
 
   // Only for unit testing.
@@ -72,10 +73,15 @@
         return_type_(return_type),
         code_start_(nullptr),
         latest_result_(nullptr),
+        can_use_baseline_for_string_init_(true),
         compilation_stats_(nullptr) {}
 
   bool BuildGraph(const DexFile::CodeItem& code);
 
+  bool CanUseBaselineForStringInit() const {
+    return can_use_baseline_for_string_init_;
+  }
+
   static constexpr const char* kBuilderPassName = "builder";
 
  private:
@@ -251,6 +257,10 @@
   // Returns whether `type_index` points to the outer-most compiling method's class.
   bool IsOutermostCompilingClass(uint16_t type_index) const;
 
+  void PotentiallySimplifyFakeString(uint16_t original_dex_register,
+                                     uint32_t dex_pc,
+                                     HInvoke* invoke);
+
   ArenaAllocator* const arena_;
 
   // A list of the size of the dex code holding block information for
@@ -290,6 +300,11 @@
   // used by move-result instructions.
   HInstruction* latest_result_;
 
+  // We need to know whether we have built a graph that has calls to StringFactory
+  // and hasn't gone through the verifier. If the following flag is `false`, then
+  // we cannot compile with baseline.
+  bool can_use_baseline_for_string_init_;
+
   OptimizingCompilerStats* compilation_stats_;
 
   DISALLOW_COPY_AND_ASSIGN(HGraphBuilder);
diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc
index e3683ef..0e099a8 100644
--- a/compiler/optimizing/code_generator_arm.cc
+++ b/compiler/optimizing/code_generator_arm.cc
@@ -4365,6 +4365,18 @@
   LOG(FATAL) << "Unreachable";
 }
 
+void LocationsBuilderARM::VisitFakeString(HFakeString* instruction) {
+  DCHECK(codegen_->IsBaseline());
+  LocationSummary* locations =
+      new (GetGraph()->GetArena()) LocationSummary(instruction, LocationSummary::kNoCall);
+  locations->SetOut(Location::ConstantLocation(GetGraph()->GetNullConstant()));
+}
+
+void InstructionCodeGeneratorARM::VisitFakeString(HFakeString* instruction ATTRIBUTE_UNUSED) {
+  DCHECK(codegen_->IsBaseline());
+  // Will be generated at use site.
+}
+
 #undef __
 #undef QUICK_ENTRY_POINT
 
diff --git a/compiler/optimizing/code_generator_arm64.cc b/compiler/optimizing/code_generator_arm64.cc
index f64e801..88d9df2 100644
--- a/compiler/optimizing/code_generator_arm64.cc
+++ b/compiler/optimizing/code_generator_arm64.cc
@@ -3039,6 +3039,18 @@
   LOG(FATAL) << "Unreachable";
 }
 
+void LocationsBuilderARM64::VisitFakeString(HFakeString* instruction) {
+  DCHECK(codegen_->IsBaseline());
+  LocationSummary* locations =
+      new (GetGraph()->GetArena()) LocationSummary(instruction, LocationSummary::kNoCall);
+  locations->SetOut(Location::ConstantLocation(GetGraph()->GetNullConstant()));
+}
+
+void InstructionCodeGeneratorARM64::VisitFakeString(HFakeString* instruction ATTRIBUTE_UNUSED) {
+  DCHECK(codegen_->IsBaseline());
+  // Will be generated at use site.
+}
+
 #undef __
 #undef QUICK_ENTRY_POINT
 
diff --git a/compiler/optimizing/code_generator_mips64.cc b/compiler/optimizing/code_generator_mips64.cc
index aa4fd26..e7d2ec6 100644
--- a/compiler/optimizing/code_generator_mips64.cc
+++ b/compiler/optimizing/code_generator_mips64.cc
@@ -3292,5 +3292,17 @@
   VisitCondition(comp);
 }
 
+void LocationsBuilderMIPS64::VisitFakeString(HFakeString* instruction) {
+  DCHECK(codegen_->IsBaseline());
+  LocationSummary* locations =
+      new (GetGraph()->GetArena()) LocationSummary(instruction, LocationSummary::kNoCall);
+  locations->SetOut(Location::ConstantLocation(GetGraph()->GetNullConstant()));
+}
+
+void InstructionCodeGeneratorMIPS64::VisitFakeString(HFakeString* instruction ATTRIBUTE_UNUSED) {
+  DCHECK(codegen_->IsBaseline());
+  // Will be generated at use site.
+}
+
 }  // namespace mips64
 }  // namespace art
diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc
index be71443..97709dd 100644
--- a/compiler/optimizing/code_generator_x86.cc
+++ b/compiler/optimizing/code_generator_x86.cc
@@ -4990,6 +4990,18 @@
   LOG(FATAL) << "Unreachable";
 }
 
+void LocationsBuilderX86::VisitFakeString(HFakeString* instruction) {
+  DCHECK(codegen_->IsBaseline());
+  LocationSummary* locations =
+      new (GetGraph()->GetArena()) LocationSummary(instruction, LocationSummary::kNoCall);
+  locations->SetOut(Location::ConstantLocation(GetGraph()->GetNullConstant()));
+}
+
+void InstructionCodeGeneratorX86::VisitFakeString(HFakeString* instruction ATTRIBUTE_UNUSED) {
+  DCHECK(codegen_->IsBaseline());
+  // Will be generated at use site.
+}
+
 #undef __
 
 }  // namespace x86
diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc
index ddaa60d..bcf2444 100644
--- a/compiler/optimizing/code_generator_x86_64.cc
+++ b/compiler/optimizing/code_generator_x86_64.cc
@@ -4792,6 +4792,18 @@
   LOG(FATAL) << "Unreachable";
 }
 
+void LocationsBuilderX86_64::VisitFakeString(HFakeString* instruction) {
+  DCHECK(codegen_->IsBaseline());
+  LocationSummary* locations =
+      new (GetGraph()->GetArena()) LocationSummary(instruction, LocationSummary::kNoCall);
+  locations->SetOut(Location::ConstantLocation(GetGraph()->GetNullConstant()));
+}
+
+void InstructionCodeGeneratorX86_64::VisitFakeString(HFakeString* instruction ATTRIBUTE_UNUSED) {
+  DCHECK(codegen_->IsBaseline());
+  // Will be generated at use site.
+}
+
 void CodeGeneratorX86_64::Load64BitValue(CpuRegister dest, int64_t value) {
   if (value == 0) {
     __ xorl(dest, dest);
diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc
index 337cf5b..da07a8c 100644
--- a/compiler/optimizing/instruction_simplifier.cc
+++ b/compiler/optimizing/instruction_simplifier.cc
@@ -70,6 +70,7 @@
   void VisitUShr(HUShr* instruction) OVERRIDE;
   void VisitXor(HXor* instruction) OVERRIDE;
   void VisitInstanceOf(HInstanceOf* instruction) OVERRIDE;
+  void VisitFakeString(HFakeString* fake_string) OVERRIDE;
   bool IsDominatedByInputNullCheck(HInstruction* instr);
 
   OptimizingCompilerStats* stats_;
@@ -903,4 +904,46 @@
   }
 }
 
+void InstructionSimplifierVisitor::VisitFakeString(HFakeString* instruction) {
+  HInstruction* actual_string = nullptr;
+
+  // Find the string we need to replace this instruction with. The actual string is
+  // the return value of a StringFactory call.
+  for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) {
+    HInstruction* use = it.Current()->GetUser();
+    if (use->IsInvokeStaticOrDirect()
+        && use->AsInvokeStaticOrDirect()->IsStringFactoryFor(instruction)) {
+      use->AsInvokeStaticOrDirect()->RemoveFakeStringArgumentAsLastInput();
+      actual_string = use;
+      break;
+    }
+  }
+
+  // Check that there is no other instruction that thinks it is the factory for that string.
+  if (kIsDebugBuild) {
+    CHECK(actual_string != nullptr);
+    for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) {
+      HInstruction* use = it.Current()->GetUser();
+      if (use->IsInvokeStaticOrDirect()) {
+        CHECK(!use->AsInvokeStaticOrDirect()->IsStringFactoryFor(instruction));
+      }
+    }
+  }
+
+  // We need to remove any environment uses of the fake string that are not dominated by
+  // `actual_string` to null.
+  for (HUseIterator<HEnvironment*> it(instruction->GetEnvUses()); !it.Done(); it.Advance()) {
+    HEnvironment* environment = it.Current()->GetUser();
+    if (!actual_string->StrictlyDominates(environment->GetHolder())) {
+      environment->RemoveAsUserOfInput(it.Current()->GetIndex());
+      environment->SetRawEnvAt(it.Current()->GetIndex(), nullptr);
+    }
+  }
+
+  // Only uses dominated by `actual_string` must remain. We can safely replace and remove
+  // `instruction`.
+  instruction->ReplaceWith(actual_string);
+  instruction->GetBlock()->RemoveInstruction(instruction);
+}
+
 }  // namespace art
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 59255d1..b628806 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -38,6 +38,7 @@
 class HCurrentMethod;
 class HDoubleConstant;
 class HEnvironment;
+class HFakeString;
 class HFloatConstant;
 class HGraphBuilder;
 class HGraphVisitor;
@@ -914,6 +915,7 @@
   M(DoubleConstant, Constant)                                           \
   M(Equal, Condition)                                                   \
   M(Exit, Instruction)                                                  \
+  M(FakeString, Instruction)                                            \
   M(FloatConstant, Constant)                                            \
   M(Goto, Instruction)                                                  \
   M(GreaterThan, Condition)                                             \
@@ -1339,8 +1341,7 @@
   const uint32_t dex_pc_;
   const InvokeType invoke_type_;
 
-  // The instruction that holds this environment. Only used in debug mode
-  // to ensure the graph is consistent.
+  // The instruction that holds this environment.
   HInstruction* const holder_;
 
   friend class HInstruction;
@@ -2730,9 +2731,11 @@
                         ClinitCheckRequirement clinit_check_requirement)
       : HInvoke(arena,
                 number_of_arguments,
-                // There is one extra argument for the  HCurrentMethod node, and
-                // potentially one other if the clinit check is explicit.
-                clinit_check_requirement == ClinitCheckRequirement::kExplicit ? 2u : 1u,
+                // There is one extra argument for the HCurrentMethod node, and
+                // potentially one other if the clinit check is explicit, and one other
+                // if the method is a string factory.
+                1u + (clinit_check_requirement == ClinitCheckRequirement::kExplicit ? 1u : 0u)
+                   + (string_init_offset ? 1u : 0u),
                 return_type,
                 dex_pc,
                 dex_method_index,
@@ -2777,6 +2780,23 @@
     DCHECK(IsStaticWithImplicitClinitCheck());
   }
 
+  bool IsStringFactoryFor(HFakeString* str) const {
+    if (!IsStringInit()) return false;
+    // +1 for the current method.
+    if (InputCount() == (number_of_arguments_ + 1)) return false;
+    return InputAt(InputCount() - 1)->AsFakeString() == str;
+  }
+
+  void RemoveFakeStringArgumentAsLastInput() {
+    DCHECK(IsStringInit());
+    size_t last_input_index = InputCount() - 1;
+    HInstruction* last_input = InputAt(last_input_index);
+    DCHECK(last_input != nullptr);
+    DCHECK(last_input->IsFakeString()) << last_input->DebugName();
+    RemoveAsUserOfInput(last_input_index);
+    inputs_.DeleteAt(last_input_index);
+  }
+
   // Is this a call to a static method whose declaring class has an
   // explicit intialization check in the graph?
   bool IsStaticWithExplicitClinitCheck() const {
@@ -4159,6 +4179,25 @@
   DISALLOW_COPY_AND_ASSIGN(HMonitorOperation);
 };
 
+/**
+ * A HInstruction used as a marker for the replacement of new + <init>
+ * of a String to a call to a StringFactory. Only baseline will see
+ * the node at code generation, where it will be be treated as null.
+ * When compiling non-baseline, `HFakeString` instructions are being removed
+ * in the instruction simplifier.
+ */
+class HFakeString : public HTemplateInstruction<0> {
+ public:
+  HFakeString() : HTemplateInstruction(SideEffects::None()) {}
+
+  Primitive::Type GetType() const OVERRIDE { return Primitive::kPrimNot; }
+
+  DECLARE_INSTRUCTION(FakeString);
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(HFakeString);
+};
+
 class MoveOperands : public ArenaObject<kArenaAllocMisc> {
  public:
   MoveOperands(Location source,
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 1e51530..4568a46 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -627,7 +627,7 @@
   // `run_optimizations_` is set explicitly (either through a compiler filter
   // or the debuggable flag). If it is set, we can run baseline. Otherwise, we fall back
   // to Quick.
-  bool can_use_baseline = !run_optimizations_;
+  bool can_use_baseline = !run_optimizations_ && builder.CanUseBaselineForStringInit();
   if (run_optimizations_ && can_optimize && can_allocate_registers) {
     VLOG(compiler) << "Optimizing " << method_name;