Handle String.<init> with a phi input.

We wrongly assumed only irreducible loops could lead
to this situation, but any loop can actually be in between
a String NewInstance and a String.<init>.

bug: 109666561
Test: 563-checker-fakestring
Change-Id: I018a22f7e22c15e140252544415f51d544f7cc13

9 files changed, 265 insertions, 40 deletions

diff --git a/compiler/optimizing/instruction_builder.cc b/compiler/optimizing/instruction_builder.cc
index 7cda6e9da3..4c72434811 100644
--- a/compiler/optimizing/instruction_builder.cc
+++ b/compiler/optimizing/instruction_builder.cc
@@ -1308,29 +1308,25 @@ bool HInstructionBuilder::HandleStringInit(HInvoke* invoke,
   HInstruction* arg_this = LoadLocal(orig_this_reg, DataType::Type::kReference);
 
   // Replacing the NewInstance might render it redundant. Keep a list of these
-  // to be visited once it is clear whether it is has remaining uses.
+  // 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 {
-    // The only reason a HPhi can flow in a String.<init> is when there is an
-    // irreducible loop, which will create HPhi for all dex registers at loop entry.
     DCHECK(arg_this->IsPhi());
-    // TODO(b/109666561): Re-enable.
-    // DCHECK(graph_->HasIrreducibleLoops());
-    // Don't bother compiling a method in that situation. While we could look at all
-    // phis related to the HNewInstance, it's not worth the trouble.
-    MaybeRecordStat(compilation_stats_,
-                    MethodCompilationStat::kNotCompiledIrreducibleAndStringInit);
-    return false;
+    // 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);
   }
-
-  // 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.cc b/compiler/optimizing/nodes.cc
index 661f66a34c..d243331dbe 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -1305,6 +1305,19 @@ void HInstruction::ReplaceUsesDominatedBy(HInstruction* dominator, HInstruction*
   }
 }
 
+void HInstruction::ReplaceEnvUsesDominatedBy(HInstruction* dominator, HInstruction* replacement) {
+  const HUseList<HEnvironment*>& uses = GetEnvUses();
+  for (auto it = uses.begin(), end = uses.end(); it != end; /* ++it below */) {
+    HEnvironment* user = it->GetUser();
+    size_t index = it->GetIndex();
+    // Increment `it` now because `*it` may disappear thanks to user->ReplaceInput().
+    ++it;
+    if (dominator->StrictlyDominates(user->GetHolder())) {
+      user->ReplaceInput(replacement, index);
+    }
+  }
+}
+
 void HInstruction::ReplaceInput(HInstruction* replacement, size_t index) {
   HUserRecord<HInstruction*> input_use = InputRecordAt(index);
   if (input_use.GetInstruction() == replacement) {
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 825779989c..cd8d07a17a 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -2217,6 +2217,7 @@ class HInstruction : public ArenaObject<kArenaAllocInstruction> {
 
   void ReplaceWith(HInstruction* instruction);
   void ReplaceUsesDominatedBy(HInstruction* dominator, HInstruction* replacement);
+  void ReplaceEnvUsesDominatedBy(HInstruction* dominator, HInstruction* replacement);
   void ReplaceInput(HInstruction* replacement, size_t index);
 
   // This is almost the same as doing `ReplaceWith()`. But in this helper, the
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 84863e4357..c69296d20f 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -846,23 +846,23 @@ CodeGenerator* OptimizingCompiler::TryCompile(ArenaAllocator* allocator,
         case kAnalysisSkipped: {
           MaybeRecordStat(compilation_stats_.get(),
                           MethodCompilationStat::kNotCompiledSkipped);
-        }
           break;
+        }
         case kAnalysisInvalidBytecode: {
           MaybeRecordStat(compilation_stats_.get(),
                           MethodCompilationStat::kNotCompiledInvalidBytecode);
-        }
           break;
+        }
         case kAnalysisFailThrowCatchLoop: {
           MaybeRecordStat(compilation_stats_.get(),
                           MethodCompilationStat::kNotCompiledThrowCatchLoop);
-        }
           break;
+        }
         case kAnalysisFailAmbiguousArrayOp: {
           MaybeRecordStat(compilation_stats_.get(),
                           MethodCompilationStat::kNotCompiledAmbiguousArrayOp);
-        }
           break;
+        }
         case kAnalysisSuccess:
           UNREACHABLE();
       }
diff --git a/compiler/optimizing/optimizing_compiler_stats.h b/compiler/optimizing/optimizing_compiler_stats.h
index f246228074..9a26f2f6c4 100644
--- a/compiler/optimizing/optimizing_compiler_stats.h
+++ b/compiler/optimizing/optimizing_compiler_stats.h
@@ -50,7 +50,6 @@ enum class MethodCompilationStat {
   kNotCompiledThrowCatchLoop,
   kNotCompiledAmbiguousArrayOp,
   kNotCompiledHugeMethod,
-  kNotCompiledIrreducibleAndStringInit,
   kNotCompiledLargeMethodNoBranches,
   kNotCompiledMalformedOpcode,
   kNotCompiledNoCodegen,
diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index dd54468217..dda29a1b4b 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -440,6 +440,62 @@ static bool HasAliasInEnvironments(HInstruction* instruction) {
   return false;
 }
 
+void 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 {
+          DCHECK(found_instance == current);
+        }
+      } else if (current->IsPhi()) {
+        // Push all inputs to the worklist. Those should be Phis or NewInstance.
+        for (HInstruction* input : current->GetInputs()) {
+          DCHECK(input->IsPhi() || input->IsNewInstance()) << input->DebugName();
+          worklist.push_back(input);
+        }
+      } else {
+        // The verifier prevents any other DEX uses of the uninitialized string.
+        DCHECK(current->IsEqual() || current->IsNotEqual());
+        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();
+        DCHECK(user->IsPhi() || user->IsEqual() || user->IsNotEqual()) << user->DebugName();
+        worklist.push_back(user);
+      }
+    } while (!worklist.empty());
+    seen_instructions.clear();
+    DCHECK(found_instance != nullptr);
+  }
+}
+
 void SsaBuilder::RemoveRedundantUninitializedStrings() {
   if (graph_->IsDebuggable()) {
     // Do not perform the optimization for consistency with the interpreter
@@ -488,27 +544,32 @@ void SsaBuilder::RemoveRedundantUninitializedStrings() {
 GraphAnalysisResult SsaBuilder::BuildSsa() {
   DCHECK(!graph_->IsInSsaForm());
 
-  // 1) Propagate types of phis. At this point, phis are typed void in the general
+  // 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`.
+  ReplaceUninitializedStringPhis();
+
+  // 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
   // conflict is detected in this stage, the phi is marked dead.
   RunPrimitiveTypePropagation();
 
-  // 2) Now that the correct primitive types have been assigned, we can get rid
+  // Now that the correct primitive types have been assigned, we can get rid
   // of redundant phis. Note that we cannot do this phase before type propagation,
   // otherwise we could get rid of phi equivalents, whose presence is a requirement
   // for the type propagation phase. Note that this is to satisfy statement (a)
   // of the SsaBuilder (see ssa_builder.h).
   SsaRedundantPhiElimination(graph_).Run();
 
-  // 3) Fix the type for null constants which are part of an equality comparison.
+  // Fix the type for null constants which are part of an equality comparison.
   // We need to do this after redundant phi elimination, to ensure the only cases
   // that we can see are reference comparison against 0. The redundant phi
   // elimination ensures we do not see a phi taking two 0 constants in a HEqual
   // or HNotEqual.
   FixNullConstantType();
 
-  // 4) Compute type of reference type instructions. The pass assumes that
+  // Compute type of reference type instructions. The pass assumes that
   // NullConstant has been fixed up.
   ReferenceTypePropagation(graph_,
                            class_loader_,
@@ -516,7 +577,7 @@ GraphAnalysisResult SsaBuilder::BuildSsa() {
                            handles_,
                            /* is_first_run */ true).Run();
 
-  // 5) HInstructionBuilder duplicated ArrayGet instructions with ambiguous type
+  // HInstructionBuilder duplicated ArrayGet instructions with ambiguous type
   // (int/float or long/double) and marked ArraySets with ambiguous input type.
   // Now that RTP computed the type of the array input, the ambiguity can be
   // resolved and the correct equivalents kept.
@@ -524,13 +585,13 @@ GraphAnalysisResult SsaBuilder::BuildSsa() {
     return kAnalysisFailAmbiguousArrayOp;
   }
 
-  // 6) Mark dead phis. This will mark phis which are not used by instructions
+  // Mark dead phis. This will mark phis which are not used by instructions
   // or other live phis. If compiling as debuggable code, phis will also be kept
   // live if they have an environment use.
   SsaDeadPhiElimination dead_phi_elimimation(graph_);
   dead_phi_elimimation.MarkDeadPhis();
 
-  // 7) Make sure environments use the right phi equivalent: a phi marked dead
+  // Make sure environments use the right phi equivalent: a phi marked dead
   // can have a phi equivalent that is not dead. In that case we have to replace
   // it with the live equivalent because deoptimization and try/catch rely on
   // environments containing values of all live vregs at that point. Note that
@@ -539,14 +600,14 @@ GraphAnalysisResult SsaBuilder::BuildSsa() {
   // environments to just reference one.
   FixEnvironmentPhis();
 
-  // 8) Now that the right phis are used for the environments, we can eliminate
+  // Now that the right phis are used for the environments, we can eliminate
   // phis we do not need. Regardless of the debuggable status, this phase is
   /// necessary for statement (b) of the SsaBuilder (see ssa_builder.h), as well
   // as for the code generation, which does not deal with phis of conflicting
   // input types.
   dead_phi_elimimation.EliminateDeadPhis();
 
-  // 9) HInstructionBuidler replaced uses of NewInstances of String with the
+  // 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
   // NullConstant. Note that this optimization is valid only if unsimplified
diff --git a/compiler/optimizing/ssa_builder.h b/compiler/optimizing/ssa_builder.h
index 60831a9e6a..765544508e 100644
--- a/compiler/optimizing/ssa_builder.h
+++ b/compiler/optimizing/ssa_builder.h
@@ -61,7 +61,8 @@ class SsaBuilder : public ValueObject {
         local_allocator_(local_allocator),
         ambiguous_agets_(local_allocator->Adapter(kArenaAllocGraphBuilder)),
         ambiguous_asets_(local_allocator->Adapter(kArenaAllocGraphBuilder)),
-        uninitialized_strings_(local_allocator->Adapter(kArenaAllocGraphBuilder)) {
+        uninitialized_strings_(local_allocator->Adapter(kArenaAllocGraphBuilder)),
+        uninitialized_string_phis_(local_allocator->Adapter(kArenaAllocGraphBuilder)) {
     graph_->InitializeInexactObjectRTI(handles);
   }
 
@@ -96,6 +97,10 @@ class SsaBuilder : public ValueObject {
     }
   }
 
+  void AddUninitializedStringPhi(HPhi* phi, HInvoke* invoke) {
+    uninitialized_string_phis_.push_back(std::make_pair(phi, invoke));
+  }
+
  private:
   void SetLoopHeaderPhiInputs();
   void FixEnvironmentPhis();
@@ -118,6 +123,7 @@ class SsaBuilder : public ValueObject {
   HArrayGet* GetFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget);
 
   void RemoveRedundantUninitializedStrings();
+  void ReplaceUninitializedStringPhis();
 
   HGraph* const graph_;
   Handle<mirror::ClassLoader> class_loader_;
@@ -131,6 +137,7 @@ class SsaBuilder : public ValueObject {
   ScopedArenaVector<HArrayGet*> ambiguous_agets_;
   ScopedArenaVector<HArraySet*> ambiguous_asets_;
   ScopedArenaVector<HNewInstance*> uninitialized_strings_;
+  ScopedArenaVector<std::pair<HPhi*, HInvoke*>> uninitialized_string_phis_;
 
   DISALLOW_COPY_AND_ASSIGN(SsaBuilder);
 };
diff --git a/test/563-checker-fakestring/smali/TestCase.smali b/test/563-checker-fakestring/smali/TestCase.smali
index 8898c48ea1..9d10bd77dd 100644
--- a/test/563-checker-fakestring/smali/TestCase.smali
+++ b/test/563-checker-fakestring/smali/TestCase.smali
@@ -142,8 +142,7 @@
    # Irreducible loop
    if-eqz p1, :loop_entry
    :loop_header
-   const v1, 0x1
-   xor-int p1, p1, v1
+   xor-int/lit8 p1, p1, 0x1
    :loop_entry
    if-eqz p1, :string_init
    goto :loop_header
@@ -166,8 +165,7 @@
    :loop_header
    if-eqz p1, :string_init
    :loop_entry
-   const v1, 0x1
-   xor-int p1, p1, v1
+   xor-int/lit8 p1, p1, 0x1
    goto :loop_header
 
    :string_init
@@ -187,8 +185,7 @@
    # Irreducible loop
    if-eqz p1, :loop_entry
    :loop_header
-   const v1, 0x1
-   xor-int p1, p1, v1
+   xor-int/lit8 p1, p1, 0x1
    :loop_entry
    if-eqz p1, :string_init
    goto :loop_header
@@ -199,3 +196,112 @@
    return-object v2
 
 .end method
+
+# Test with a loop between allocation and String.<init>.
+.method public static loopAndStringInit([BZ)Ljava/lang/String;
+   .registers 5
+
+   new-instance v0, Ljava/lang/String;
+
+   # Loop
+   :loop_header
+   if-eqz p1, :loop_exit
+   xor-int/lit8 p1, p1, 0x1
+   goto :loop_header
+
+   :loop_exit
+   const-string v1, "UTF8"
+   invoke-direct {v0, p0, v1}, Ljava/lang/String;-><init>([BLjava/lang/String;)V
+   return-object v0
+
+.end method
+
+# Test with a loop and aliases between allocation and String.<init>.
+.method public static loopAndStringInitAlias([BZ)Ljava/lang/String;
+   .registers 5
+
+   new-instance v0, Ljava/lang/String;
+   move-object v2, v0
+
+   # Loop
+   :loop_header
+   if-eqz p1, :loop_exit
+   xor-int/lit8 p1, p1, 0x1
+   goto :loop_header
+
+   :loop_exit
+   const-string v1, "UTF8"
+   invoke-direct {v0, p0, v1}, Ljava/lang/String;-><init>([BLjava/lang/String;)V
+   return-object v2
+
+.end method
+
+# Test deoptimization after String initialization of a phi.
+## CHECK-START: int TestCase.deoptimizeNewInstanceAfterLoop(int[], byte[], int) register (after)
+## CHECK:         <<Invoke:l\d+>> InvokeStaticOrDirect method_name:java.lang.String.<init>
+## CHECK:                         Deoptimize env:[[<<Invoke>>,{{.*]]}}
+
+.method public static deoptimizeNewInstanceAfterLoop([I[BI)I
+   .registers 8
+
+   const v2, 0x0
+   const v1, 0x1
+
+   new-instance v0, Ljava/lang/String; # HNewInstance(String)
+   move-object v4, v0
+   # Loop
+   :loop_header
+   if-eqz p2, :loop_exit
+   xor-int/lit8 p2, p2, 0x1
+   goto :loop_header
+
+   :loop_exit
+   const-string v3, "UTF8"
+   invoke-direct {v0, p1, v3}, Ljava/lang/String;-><init>([BLjava/lang/String;)V
+
+   # Deoptimize here if the array is too short.
+   aget v1, p0, v1              # v1 = int_array[0x1]
+   add-int/2addr v2, v1         # v2 = 0x0 + v1
+
+   # Check that we're being executed by the interpreter.
+   invoke-static {}, LMain;->assertIsInterpreted()V
+
+   # Check that the environments contain the right string.
+   invoke-static {p1, v0}, LMain;->assertEqual([BLjava/lang/String;)V
+   invoke-static {p1, v4}, LMain;->assertEqual([BLjava/lang/String;)V
+
+   # This ArrayGet will throw ArrayIndexOutOfBoundsException.
+   const v1, 0x4
+   aget v1, p0, v1
+   add-int/2addr v2, v1
+
+   return v2
+
+.end method
+
+# Test with a loop between allocation and String.<init> and a null check.
+## CHECK-START: java.lang.String TestCase.loopAndStringInitAndTest(byte[], boolean) builder (after)
+## CHECK-DAG:     <<Null:l\d+>>   NullConstant
+## CHECK-DAG:     <<String:l\d+>> NewInstance
+## CHECK-DAG:     <<Cond:z\d+>>   NotEqual [<<String>>,<<Null>>]
+
+## CHECK-START: java.lang.String TestCase.loopAndStringInitAndTest(byte[], boolean) register (after)
+## CHECK-DAG:     <<String:l\d+>> NewInstance
+.method public static loopAndStringInitAndTest([BZ)Ljava/lang/String;
+   .registers 5
+
+   new-instance v0, Ljava/lang/String;
+
+   # Loop
+   :loop_header
+   # Use the new-instance in the only way it can be used.
+   if-nez v0, :loop_exit
+   xor-int/lit8 p1, p1, 0x1
+   goto :loop_header
+
+   :loop_exit
+   const-string v1, "UTF8"
+   invoke-direct {v0, p0, v1}, Ljava/lang/String;-><init>([BLjava/lang/String;)V
+   return-object v0
+
+.end method
diff --git a/test/563-checker-fakestring/src/Main.java b/test/563-checker-fakestring/src/Main.java
index d38b7f4f23..3639d59878 100644
--- a/test/563-checker-fakestring/src/Main.java
+++ b/test/563-checker-fakestring/src/Main.java
@@ -23,12 +23,19 @@ public class Main {
 
   public static native void assertIsInterpreted();
 
-  private static void assertEqual(String expected, String actual) {
+  public static void assertEqual(String expected, String actual) {
     if (!expected.equals(actual)) {
       throw new Error("Assertion failed: " + expected + " != " + actual);
     }
   }
 
+  public static void assertEqual(byte[] expected, String actual) throws Exception {
+    String str = new String(expected, "UTF8");
+    if (!str.equals(actual)) {
+      throw new Error("Assertion failed: " + str + " != " + actual);
+    }
+  }
+
   public static void main(String[] args) throws Throwable {
     System.loadLibrary(args[0]);
     Class<?> c = Class.forName("TestCase");
@@ -85,6 +92,41 @@ public class Main {
       result = (String) m.invoke(null, new Object[] { testData, false });
       assertEqual(testString, result);
     }
+    {
+      Method m = c.getMethod("loopAndStringInit", byte[].class, boolean.class);
+      String result = (String) m.invoke(null, new Object[] { testData, true });
+      assertEqual(testString, result);
+      result = (String) m.invoke(null, new Object[] { testData, false });
+      assertEqual(testString, result);
+    }
+    {
+      Method m = c.getMethod("loopAndStringInitAlias", byte[].class, boolean.class);
+      String result = (String) m.invoke(null, new Object[] { testData, true });
+      assertEqual(testString, result);
+      result = (String) m.invoke(null, new Object[] { testData, false });
+      assertEqual(testString, result);
+    }
+    {
+      Method m = c.getMethod("loopAndStringInitAndTest", byte[].class, boolean.class);
+      String result = (String) m.invoke(null, new Object[] { testData, true });
+      assertEqual(testString, result);
+      result = (String) m.invoke(null, new Object[] { testData, false });
+      assertEqual(testString, result);
+    }
+
+    {
+      Method m = c.getMethod(
+          "deoptimizeNewInstanceAfterLoop", int[].class, byte[].class, int.class);
+      try {
+        m.invoke(null, new Object[] { new int[] { 1, 2, 3 }, testData, 0 });
+      } catch (InvocationTargetException ex) {
+        if (ex.getCause() instanceof ArrayIndexOutOfBoundsException) {
+          // Expected.
+        } else {
+          throw ex.getCause();
+        }
+      }
+    }
   }
 
   public static boolean doThrow = false;