Fix ReplaceUninitializedStringPhis.
Move the analysis after redundant phi and dead phi elimination,
knowing that only graphs with irreducible loops may still have
a phi as input of the invoke. In such a case, we bail.
bug: 112537407
Test: 563-checker-fake-string
Change-Id: Ib9eefa4ce905b7fb418ca9b2a3c26ea4df74ce8f
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);
};