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/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