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
diff --git a/compiler/optimizing/instruction_builder.cc b/compiler/optimizing/instruction_builder.cc
index 7cda6e9..4c72434 100644
--- a/compiler/optimizing/instruction_builder.cc
+++ b/compiler/optimizing/instruction_builder.cc
@@ -1308,29 +1308,25 @@
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());
- } 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;
- }
-
- // 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;
+ // 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);
}
-
return true;
}
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 661f66a..d243331 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -1305,6 +1305,19 @@
}
}
+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 8257799..cd8d07a 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -2217,6 +2217,7 @@
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 84863e4..c69296d 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -846,23 +846,23 @@
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 f246228..9a26f2f 100644
--- a/compiler/optimizing/optimizing_compiler_stats.h
+++ b/compiler/optimizing/optimizing_compiler_stats.h
@@ -50,7 +50,6 @@
kNotCompiledThrowCatchLoop,
kNotCompiledAmbiguousArrayOp,
kNotCompiledHugeMethod,
- kNotCompiledIrreducibleAndStringInit,
kNotCompiledLargeMethodNoBranches,
kNotCompiledMalformedOpcode,
kNotCompiledNoCodegen,
diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index dd54468..dda29a1 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -440,6 +440,62 @@
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 @@
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 @@
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 @@
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 @@
// 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 60831a9..7655445 100644
--- a/compiler/optimizing/ssa_builder.h
+++ b/compiler/optimizing/ssa_builder.h
@@ -61,7 +61,8 @@
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 @@
}
}
+ 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 @@
HArrayGet* GetFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget);
void RemoveRedundantUninitializedStrings();
+ void ReplaceUninitializedStringPhis();
HGraph* const graph_;
Handle<mirror::ClassLoader> class_loader_;
@@ -131,6 +137,7 @@
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 8898c48..9d10bd7 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 d38b7f4..3639d59 100644
--- a/test/563-checker-fakestring/src/Main.java
+++ b/test/563-checker-fakestring/src/Main.java
@@ -23,12 +23,19 @@
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 @@
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;