diff --git a/compiler/optimizing/instruction_builder.cc b/compiler/optimizing/instruction_builder.cc
index 72b6748..b576f83 100644
--- a/compiler/optimizing/instruction_builder.cc
+++ b/compiler/optimizing/instruction_builder.cc
@@ -1497,21 +1497,22 @@
   // to be visited once it is clear whether it has remaining uses.
   if (arg_this->IsNewInstance()) {
     ssa_builder_->AddUninitializedString(arg_this->AsNewInstance());
-    // Walk over all vregs and replace any occurrence of `arg_this` with `invoke`.
-    for (size_t vreg = 0, e = current_locals_->size(); vreg < e; ++vreg) {
-      if ((*current_locals_)[vreg] == arg_this) {
-        (*current_locals_)[vreg] = invoke;
-      }
-    }
   } else {
     DCHECK(arg_this->IsPhi());
     // We can get a phi as input of a String.<init> if there is a loop between the
     // allocation and the String.<init> call. As we don't know which other phis might alias
-    // with `arg_this`, we keep a record of these phis and will analyze their inputs and
-    // uses once the inputs and users are populated (in ssa_builder.cc).
-    // Note: we only do this for phis, as it is a somewhat more expensive operation than
-    // what we're doing above when the input is the `HNewInstance`.
-    ssa_builder_->AddUninitializedStringPhi(arg_this->AsPhi(), invoke);
+    // with `arg_this`, we keep a record of those invocations so we can later replace
+    // the allocation with the invocation.
+    // Add the actual 'this' input so the analysis knows what is the allocation instruction.
+    // The input will be removed during the analysis.
+    invoke->AddInput(arg_this);
+    ssa_builder_->AddUninitializedStringPhi(invoke);
+  }
+  // Walk over all vregs and replace any occurrence of `arg_this` with `invoke`.
+  for (size_t vreg = 0, e = current_locals_->size(); vreg < e; ++vreg) {
+    if ((*current_locals_)[vreg] == arg_this) {
+      (*current_locals_)[vreg] = invoke;
+    }
   }
   return true;
 }
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 218b447..7921061 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -129,6 +129,7 @@
   kAnalysisInvalidBytecode,
   kAnalysisFailThrowCatchLoop,
   kAnalysisFailAmbiguousArrayOp,
+  kAnalysisFailIrreducibleLoopAndStringInit,
   kAnalysisSuccess,
 };
 
@@ -4537,8 +4538,7 @@
                 allocator,
                 number_of_arguments,
                 // There is potentially one extra argument for the HCurrentMethod node, and
-                // potentially one other if the clinit check is explicit, and potentially
-                // one other if the method is a string factory.
+                // potentially one other if the clinit check is explicit.
                 (NeedsCurrentMethodInput(dispatch_info.method_load_kind) ? 1u : 0u) +
                     (clinit_check_requirement == ClinitCheckRequirement::kExplicit ? 1u : 0u),
                 return_type,
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 7d339cd..46754fe 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -847,6 +847,11 @@
                           MethodCompilationStat::kNotCompiledAmbiguousArrayOp);
           break;
         }
+        case kAnalysisFailIrreducibleLoopAndStringInit: {
+          MaybeRecordStat(compilation_stats_.get(),
+                          MethodCompilationStat::kNotCompiledIrreducibleLoopAndStringInit);
+          break;
+        }
         case kAnalysisSuccess:
           UNREACHABLE();
       }
diff --git a/compiler/optimizing/optimizing_compiler_stats.h b/compiler/optimizing/optimizing_compiler_stats.h
index 9a26f2f..1f4f6d5 100644
--- a/compiler/optimizing/optimizing_compiler_stats.h
+++ b/compiler/optimizing/optimizing_compiler_stats.h
@@ -59,6 +59,7 @@
   kNotCompiledUnsupportedIsa,
   kNotCompiledVerificationError,
   kNotCompiledVerifyAtRuntime,
+  kNotCompiledIrreducibleLoopAndStringInit,
   kInlinedMonomorphicCall,
   kInlinedPolymorphicCall,
   kMonomorphicCall,
diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index db96e41..16c23c8 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -16,6 +16,8 @@
 
 #include "ssa_builder.h"
 
+#include "base/arena_bit_vector.h"
+#include "base/bit_vector-inl.h"
 #include "data_type-inl.h"
 #include "dex/bytecode_utils.h"
 #include "mirror/class-inl.h"
@@ -415,97 +417,34 @@
   return true;
 }
 
-static bool HasAliasInEnvironments(HInstruction* instruction) {
-  HEnvironment* last_user = nullptr;
+bool SsaBuilder::HasAliasInEnvironments(HInstruction* instruction) {
+  ScopedArenaHashSet<size_t> seen_users(
+      local_allocator_->Adapter(kArenaAllocGraphBuilder));
   for (const HUseListNode<HEnvironment*>& use : instruction->GetEnvUses()) {
     DCHECK(use.GetUser() != nullptr);
-    // Note: The first comparison (== null) always fails.
-    if (use.GetUser() == last_user) {
+    size_t id = use.GetUser()->GetHolder()->GetId();
+    if (seen_users.find(id) != seen_users.end()) {
       return true;
     }
-    last_user = use.GetUser();
-  }
-
-  if (kIsDebugBuild) {
-    // Do a quadratic search to ensure same environment uses are next
-    // to each other.
-    const HUseList<HEnvironment*>& env_uses = instruction->GetEnvUses();
-    for (auto current = env_uses.begin(), end = env_uses.end(); current != end; ++current) {
-      auto next = current;
-      for (++next; next != end; ++next) {
-        DCHECK(next->GetUser() != current->GetUser());
-      }
-    }
+    seen_users.insert(id);
   }
   return false;
 }
 
-// Returns whether the analysis succeeded. If it did not, we are going to bail
-// to interpreter.
-// TODO(ngeoffray): Remove this workaround.
 bool SsaBuilder::ReplaceUninitializedStringPhis() {
-  ScopedArenaHashSet<HInstruction*> seen_instructions(
-      local_allocator_->Adapter(kArenaAllocGraphBuilder));
-  ScopedArenaVector<HInstruction*> worklist(local_allocator_->Adapter(kArenaAllocGraphBuilder));
-
-  // Iterate over all inputs and uses of the phi, recursively, until all related instructions
-  // have been visited.
-  for (const auto& pair : uninitialized_string_phis_) {
-    HPhi* string_phi = pair.first;
-    HInvoke* invoke = pair.second;
-    worklist.push_back(string_phi);
-    HNewInstance* found_instance = nullptr;
-    do {
-      HInstruction* current = worklist.back();
-      worklist.pop_back();
-      if (seen_instructions.find(current) != seen_instructions.end()) {
-        continue;
-      }
-      seen_instructions.insert(current);
-      if (current->IsNewInstance()) {
-        // If it is the first time we see the allocation, replace its uses. We don't register
-        // it through `RemoveRedundantUninitializedStrings`, as that method makes assumption about
-        // aliasing and environment uses that don't hold when the string escapes to phis.
-        // Note that this also means we will keep the (useless) allocation.
-        if (found_instance == nullptr) {
-          found_instance = current->AsNewInstance();
-        } else {
-          if (found_instance != current) {
-            return false;
-          }
-        }
-      } else if (current->IsPhi()) {
-        // Push all inputs to the worklist. Those should be Phis or NewInstance.
-        for (HInstruction* input : current->GetInputs()) {
-          if (!input->IsPhi() && !input->IsNewInstance()) {
-            return false;
-          }
-          worklist.push_back(input);
-        }
-      } else {
-        // The verifier prevents any other DEX uses of the uninitialized string.
-        if (!current->IsEqual() && !current->IsNotEqual()) {
-          return false;
-        }
-        continue;
-      }
-      current->ReplaceUsesDominatedBy(invoke, invoke);
-      current->ReplaceEnvUsesDominatedBy(invoke, invoke);
-      // Push all users to the worklist. Now that we have replaced
-      // the uses dominated by the invokes, the remaining users should only
-      // be Phi, or Equal/NotEqual.
-      for (const HUseListNode<HInstruction*>& use : current->GetUses()) {
-        HInstruction* user = use.GetUser();
-        if (!user->IsPhi() && !user->IsEqual() && !user->IsNotEqual()) {
-          return false;
-        }
-        worklist.push_back(user);
-      }
-    } while (!worklist.empty());
-    seen_instructions.clear();
-    if (found_instance == nullptr) {
+  for (HInvoke* invoke : uninitialized_string_phis_) {
+    HInstruction* str = invoke->InputAt(invoke->InputCount() - 1);
+    if (str->IsPhi()) {
+      // If after redundant phi and dead phi elimination, it's still a phi that feeds
+      // the invoke, then we must be compiling a method with irreducible loops. Just bail.
+      DCHECK(graph_->HasIrreducibleLoops());
       return false;
     }
+    DCHECK(str->IsNewInstance());
+    AddUninitializedString(str->AsNewInstance());
+    str->ReplaceUsesDominatedBy(invoke, invoke);
+    str->ReplaceEnvUsesDominatedBy(invoke, invoke);
+    invoke->RemoveInputAt(invoke->InputCount() - 1);
   }
   return true;
 }
@@ -522,8 +461,9 @@
     DCHECK(new_instance->IsStringAlloc());
 
     // Replace NewInstance of String with NullConstant if not used prior to
-    // calling StringFactory. In case of deoptimization, the interpreter is
-    // expected to skip null check on the `this` argument of the StringFactory call.
+    // calling StringFactory. We check for alias environments in case of deoptimization.
+    // The interpreter is expected to skip null check on the `this` argument of the
+    // StringFactory call.
     if (!new_instance->HasNonEnvironmentUses() && !HasAliasInEnvironments(new_instance)) {
       new_instance->ReplaceWith(graph_->GetNullConstant());
       new_instance->GetBlock()->RemoveInstruction(new_instance);
@@ -558,13 +498,6 @@
 GraphAnalysisResult SsaBuilder::BuildSsa() {
   DCHECK(!graph_->IsInSsaForm());
 
-  // Replace Phis that feed in a String.<init>, as well as their aliases, with
-  // the actual String allocation invocation. We do this first, as the phis stored in
-  // the data structure might get removed from the graph in later stages during `BuildSsa`.
-  if (!ReplaceUninitializedStringPhis()) {
-    return kAnalysisSkipped;
-  }
-
   // Propagate types of phis. At this point, phis are typed void in the general
   // case, or float/double/reference if we created an equivalent phi. So we need
   // to propagate the types across phis to give them a correct type. If a type
@@ -623,6 +556,14 @@
   // input types.
   dead_phi_elimimation.EliminateDeadPhis();
 
+  // Replace Phis that feed in a String.<init> during instruction building. We
+  // run this after redundant and dead phi elimination to make sure the phi will have
+  // been replaced by the actual allocation. Only with an irreducible loop
+  // a phi can still be the input, in which case we bail.
+  if (!ReplaceUninitializedStringPhis()) {
+    return kAnalysisFailIrreducibleLoopAndStringInit;
+  }
+
   // HInstructionBuidler replaced uses of NewInstances of String with the
   // results of their corresponding StringFactory calls. Unless the String
   // objects are used before they are initialized, they can be replaced with
diff --git a/compiler/optimizing/ssa_builder.h b/compiler/optimizing/ssa_builder.h
index bae15ac..bb892c9 100644
--- a/compiler/optimizing/ssa_builder.h
+++ b/compiler/optimizing/ssa_builder.h
@@ -97,8 +97,8 @@
     }
   }
 
-  void AddUninitializedStringPhi(HPhi* phi, HInvoke* invoke) {
-    uninitialized_string_phis_.push_back(std::make_pair(phi, invoke));
+  void AddUninitializedStringPhi(HInvoke* invoke) {
+    uninitialized_string_phis_.push_back(invoke);
   }
 
  private:
@@ -124,6 +124,7 @@
 
   void RemoveRedundantUninitializedStrings();
   bool ReplaceUninitializedStringPhis();
+  bool HasAliasInEnvironments(HInstruction* instruction);
 
   HGraph* const graph_;
   Handle<mirror::ClassLoader> class_loader_;
@@ -137,7 +138,7 @@
   ScopedArenaVector<HArrayGet*> ambiguous_agets_;
   ScopedArenaVector<HArraySet*> ambiguous_asets_;
   ScopedArenaVector<HNewInstance*> uninitialized_strings_;
-  ScopedArenaVector<std::pair<HPhi*, HInvoke*>> uninitialized_string_phis_;
+  ScopedArenaVector<HInvoke*> uninitialized_string_phis_;
 
   DISALLOW_COPY_AND_ASSIGN(SsaBuilder);
 };