Fix issue with propagating partial values
We would incorrectly not propagate or calculate partial read values
sometimes in the presence of loops. This fixes that issue by correctly
interpreting merged-unknowns as being phis when before escapes and
propagating uses of removed reads when needed.
Test: ./test.py --host
Test: ./art/tools/compile-jar.py --dex2oat `which dex2oatd64` --profile-line 'HSLcom/android/textclassifier/common/statsd/GenerateLinksLogger;->logGenerateLinks(Ljava/lang/CharSequence;Landroid/view/textclassifier/TextLinks;Ljava/lang/String;JLcom/google/common/base/Optional;Lcom/google/common/base/Optional;)V' --arch arm64 ~/GoogleExtServices.apk -j1 --runtime-arg -verbose:compiler --dump-stats
Bug: 183554067
Change-Id: I7f6e99934237174922ef2da2b77092e74cfb6a77
diff --git a/compiler/optimizing/load_store_elimination.cc b/compiler/optimizing/load_store_elimination.cc
index 1ea2ece..c4279c7 100644
--- a/compiler/optimizing/load_store_elimination.cc
+++ b/compiler/optimizing/load_store_elimination.cc
@@ -2833,7 +2833,7 @@
std::replace_if(
phi_placeholder_replacements_.begin(),
phi_placeholder_replacements_.end(),
- [](const Value& val) { return val.IsPureUnknown(); },
+ [](const Value& val) { return !val.IsDefault() && !val.IsInstruction(); },
Value::Invalid());
}
@@ -2978,7 +2978,7 @@
}
ReplaceInput(to_replace);
- RemoveInput(to_remove);
+ RemoveAndReplaceInputs(to_remove);
CreateConstructorFences(constructor_fences);
PredicateInstructions(to_predicate);
@@ -3092,7 +3092,7 @@
}
}
- void RemoveInput(const ScopedArenaVector<HInstruction*>& to_remove) {
+ void RemoveAndReplaceInputs(const ScopedArenaVector<HInstruction*>& to_remove) {
for (HInstruction* ins : to_remove) {
if (ins->GetBlock() == nullptr) {
// Already dealt with.
@@ -3100,6 +3100,30 @@
}
DCHECK(BeforeAllEscapes(ins->GetBlock())) << *ins;
if (ins->IsInstanceFieldGet() || ins->IsInstanceFieldSet()) {
+ bool instruction_has_users =
+ ins->IsInstanceFieldGet() && (!ins->GetUses().empty() || !ins->GetEnvUses().empty());
+ if (instruction_has_users) {
+ // Make sure any remaining users of read are replaced.
+ HInstruction* replacement =
+ helper_->lse_->GetPartialValueAt(OriginalNewInstance(), ins);
+ // NB ReplaceInput will remove a use from the list so this is
+ // guaranteed to finish eventually.
+ while (!ins->GetUses().empty()) {
+ const HUseListNode<HInstruction*>& use = ins->GetUses().front();
+ use.GetUser()->ReplaceInput(replacement, use.GetIndex());
+ }
+ while (!ins->GetEnvUses().empty()) {
+ const HUseListNode<HEnvironment*>& use = ins->GetEnvUses().front();
+ use.GetUser()->ReplaceInput(replacement, use.GetIndex());
+ }
+ } else {
+ DCHECK(ins->GetUses().empty())
+ << "Instruction has users!\n"
+ << ins->DumpWithArgs() << "\nUsers are " << ins->GetUses();
+ DCHECK(ins->GetEnvUses().empty())
+ << "Instruction has users!\n"
+ << ins->DumpWithArgs() << "\nUsers are " << ins->GetEnvUses();
+ }
ins->GetBlock()->RemoveInstruction(ins);
} else {
// Can only be obj == other, obj != other, obj == obj (!?) or, obj != obj (!?)
@@ -3554,9 +3578,8 @@
info = field_infos_[loc_off];
DCHECK(loc->GetIndex() == nullptr);
Value value = ReplacementOrValue(heap_values_for_[old_pred->GetBlockId()][loc_off].value);
- if (value.NeedsLoopPhi()) {
+ if (value.NeedsLoopPhi() || value.IsMergedUnknown()) {
Value repl = phi_placeholder_replacements_[PhiPlaceholderIndex(value.GetPhiPlaceholder())];
- DCHECK(!repl.IsUnknown());
DCHECK(repl.IsDefault() || repl.IsInvalid() || repl.IsInstruction())
<< repl << " from " << value << " pred is " << old_pred->GetBlockId();
if (!repl.IsInvalid()) {
diff --git a/compiler/optimizing/load_store_elimination_test.cc b/compiler/optimizing/load_store_elimination_test.cc
index eb5079f..9aa0da9 100644
--- a/compiler/optimizing/load_store_elimination_test.cc
+++ b/compiler/optimizing/load_store_elimination_test.cc
@@ -5866,6 +5866,152 @@
EXPECT_INS_EQ(bottom_phi->InputAt(1), moved_ni2);
}
+// // ENTRY
+// obj = new Obj();
+// if (param1) {
+// obj.field = 3;
+// noescape();
+// } else {
+// obj.field = 2;
+// noescape();
+// }
+// int abc;
+// if (parameter_value) {
+// // LEFT
+// abc = 4;
+// escape(obj);
+// } else {
+// // RIGHT
+// // ELIMINATE
+// noescape();
+// abc = obj.field + 4;
+// }
+// abc = phi
+// EXIT
+// predicated-ELIMINATE
+// return obj.field + abc
+TEST_F(LoadStoreEliminationTest, PredicatedLoad4) {
+ VariableSizedHandleScope vshs(Thread::Current());
+ CreateGraph(/*handles=*/&vshs);
+ AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
+ "exit",
+ {{"entry", "start_left"},
+ {"entry", "start_right"},
+ {"start_left", "mid"},
+ {"start_right", "mid"},
+ {"mid", "left"},
+ {"mid", "right"},
+ {"left", "breturn"},
+ {"right", "breturn"},
+ {"breturn", "exit"}}));
+#define GET_BLOCK(name) HBasicBlock* name = blks.Get(#name)
+ GET_BLOCK(entry);
+ GET_BLOCK(exit);
+ GET_BLOCK(breturn);
+ GET_BLOCK(left);
+ GET_BLOCK(right);
+ GET_BLOCK(mid);
+ GET_BLOCK(start_left);
+ GET_BLOCK(start_right);
+#undef GET_BLOCK
+ EnsurePredecessorOrder(breturn, {left, right});
+ EnsurePredecessorOrder(mid, {start_left, start_right});
+ HInstruction* bool_value = MakeParam(DataType::Type::kBool);
+ HInstruction* bool_value2 = MakeParam(DataType::Type::kBool);
+ HInstruction* null_const = graph_->GetNullConstant();
+ HInstruction* c2 = graph_->GetIntConstant(2);
+ HInstruction* c3 = graph_->GetIntConstant(3);
+ HInstruction* c4 = graph_->GetIntConstant(4);
+
+ HInstruction* cls = MakeClassLoad();
+ HInstruction* new_inst = MakeNewInstance(cls);
+ HInstruction* if_inst = new (GetAllocator()) HIf(bool_value);
+ entry->AddInstruction(cls);
+ entry->AddInstruction(new_inst);
+ entry->AddInstruction(if_inst);
+ ManuallyBuildEnvFor(cls, {});
+ new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ HInstruction* write_start_left = MakeIFieldSet(new_inst, c3, MemberOffset(32));
+ HInstruction* call_start_left = MakeInvoke(DataType::Type::kVoid, { });
+ start_left->AddInstruction(write_start_left);
+ start_left->AddInstruction(call_start_left);
+ start_left->AddInstruction(new (GetAllocator()) HGoto());
+ call_start_left->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ HInstruction* write_start_right = MakeIFieldSet(new_inst, c2, MemberOffset(32));
+ HInstruction* call_start_right = MakeInvoke(DataType::Type::kVoid, { });
+ start_right->AddInstruction(write_start_right);
+ start_right->AddInstruction(call_start_right);
+ start_right->AddInstruction(new (GetAllocator()) HGoto());
+ call_start_right->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ mid->AddInstruction(new (GetAllocator()) HIf(bool_value2));
+
+ HInstruction* call_left = MakeInvoke(DataType::Type::kVoid, { new_inst });
+ HInstruction* goto_left = new (GetAllocator()) HGoto();
+ left->AddInstruction(call_left);
+ left->AddInstruction(goto_left);
+ call_left->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ HInstruction* call_right = MakeInvoke(DataType::Type::kVoid, { });
+ HInstruction* read_right = MakeIFieldGet(new_inst, DataType::Type::kInt32, MemberOffset(32));
+ HInstruction* add_right = new (GetAllocator()) HAdd(DataType::Type::kInt32, read_right, c4);
+ HInstruction* goto_right = new (GetAllocator()) HGoto();
+ right->AddInstruction(call_right);
+ right->AddInstruction(read_right);
+ right->AddInstruction(add_right);
+ right->AddInstruction(goto_right);
+ call_right->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ HPhi* phi_bottom = MakePhi({c4, add_right});
+ HInstruction* read_bottom = MakeIFieldGet(new_inst, DataType::Type::kInt32, MemberOffset(32));
+ HInstruction* add_bottom =
+ new (GetAllocator()) HAdd(DataType::Type::kInt32, read_bottom, phi_bottom);
+ HInstruction* return_exit = new (GetAllocator()) HReturn(add_bottom);
+ breturn->AddPhi(phi_bottom);
+ breturn->AddInstruction(read_bottom);
+ breturn->AddInstruction(add_bottom);
+ breturn->AddInstruction(return_exit);
+
+ SetupExit(exit);
+
+ // PerformLSE expects this to be empty.
+ graph_->ClearDominanceInformation();
+ LOG(INFO) << "Pre LSE " << blks;
+ PerformLSEWithPartial();
+ LOG(INFO) << "Post LSE " << blks;
+
+ EXPECT_INS_REMOVED(read_bottom);
+ EXPECT_INS_REMOVED(read_right);
+ EXPECT_INS_RETAINED(call_left);
+ EXPECT_INS_RETAINED(call_right);
+ EXPECT_INS_RETAINED(call_start_left);
+ EXPECT_INS_RETAINED(call_start_right);
+ std::vector<HPhi*> merges;
+ HPredicatedInstanceFieldGet* pred_get =
+ FindSingleInstruction<HPredicatedInstanceFieldGet>(graph_, breturn);
+ std::tie(merges) = FindAllInstructions<HPhi>(graph_, breturn);
+ ASSERT_EQ(merges.size(), 3u);
+ HPhi* merge_value_return = FindOrNull(merges.begin(), merges.end(), [&](HPhi* p) {
+ return p != phi_bottom && p->GetType() == DataType::Type::kInt32;
+ });
+ HPhi* merge_alloc = FindOrNull(merges.begin(), merges.end(), [](HPhi* p) {
+ return p->GetType() == DataType::Type::kReference;
+ });
+ ASSERT_NE(merge_alloc, nullptr);
+ EXPECT_TRUE(merge_alloc->InputAt(0)->IsNewInstance()) << *merge_alloc;
+ EXPECT_EQ(merge_alloc->InputAt(0)->InputAt(0), cls) << *merge_alloc << " cls? " << *cls;
+ EXPECT_EQ(merge_alloc->InputAt(1), null_const);
+ ASSERT_NE(pred_get, nullptr);
+ EXPECT_INS_EQ(pred_get->GetTarget(), merge_alloc);
+ EXPECT_INS_EQ(pred_get->GetDefaultValue(), merge_value_return) << " pred-get is: " << *pred_get;
+ EXPECT_INS_EQ(merge_value_return->InputAt(0), graph_->GetIntConstant(0))
+ << " merge val is: " << *merge_value_return;
+ EXPECT_INS_EQ(merge_value_return->InputAt(1), FindSingleInstruction<HPhi>(graph_, mid))
+ << " merge val is: " << *merge_value_return;
+}
+
// Based on structure seen in `java.util.Set java.util.Collections$UnmodifiableMap.entrySet()`
// We end up having to update a PHI generated by normal LSE.
// // ENTRY
@@ -7136,6 +7282,170 @@
EXPECT_INS_REMOVED(write_pre_header) << *write_pre_header;
}
+// // ENTRY
+// obj = new Obj();
+// obj.field = 3;
+// if (param) {
+// while (!test()) {
+// if (test2()) {
+// noescape();
+// } else {
+// abc = obj.field;
+// obj.field = abc + 5;
+// noescape();
+// }
+// }
+// escape(obj);
+// } else {
+// }
+// return obj.field
+TEST_F(LoadStoreEliminationTest, PartialLoopPhis6) {
+ VariableSizedHandleScope vshs(Thread::Current());
+ CreateGraph(/*handles=*/&vshs);
+ AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
+ "exit",
+ {{"entry", "start"},
+ {"start", "left"},
+ {"start", "right"},
+ {"left", "loop_pre_header"},
+
+ {"loop_pre_header", "loop_header"},
+ {"loop_header", "escape"},
+ {"loop_header", "loop_body"},
+ {"loop_body", "loop_if_left"},
+ {"loop_body", "loop_if_right"},
+ {"loop_if_left", "loop_header"},
+ {"loop_if_right", "loop_header"},
+
+ {"escape", "breturn"},
+ {"right", "breturn"},
+ {"breturn", "exit"}}));
+#define GET_BLOCK(name) HBasicBlock* name = blks.Get(#name)
+ GET_BLOCK(entry);
+ GET_BLOCK(exit);
+ GET_BLOCK(breturn);
+ GET_BLOCK(left);
+ GET_BLOCK(right);
+ GET_BLOCK(start);
+ GET_BLOCK(escape);
+
+ GET_BLOCK(loop_pre_header);
+ GET_BLOCK(loop_header);
+ GET_BLOCK(loop_body);
+ GET_BLOCK(loop_if_left);
+ GET_BLOCK(loop_if_right);
+#undef GET_BLOCK
+ EnsurePredecessorOrder(breturn, {escape, right});
+ EnsurePredecessorOrder(loop_header, {loop_pre_header, loop_if_left, loop_if_right});
+ CHECK_SUBROUTINE_FAILURE();
+ HInstruction* bool_val = MakeParam(DataType::Type::kBool);
+ HInstruction* c3 = graph_->GetIntConstant(3);
+ HInstruction* c5 = graph_->GetIntConstant(5);
+
+ HInstruction* cls = MakeClassLoad();
+ HInstruction* new_inst = MakeNewInstance(cls);
+ HInstruction* write_entry = MakeIFieldSet(new_inst, c3, MemberOffset(32));
+ HInstruction* entry_goto = new (GetAllocator()) HGoto();
+ entry->AddInstruction(cls);
+ entry->AddInstruction(new_inst);
+ entry->AddInstruction(write_entry);
+ entry->AddInstruction(entry_goto);
+ ManuallyBuildEnvFor(cls, {});
+ new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ start->AddInstruction(new (GetAllocator()) HIf(bool_val));
+
+ HInstruction* left_goto = new (GetAllocator()) HGoto();
+ left->AddInstruction(left_goto);
+
+ HInstruction* goto_preheader = new (GetAllocator()) HGoto();
+ loop_pre_header->AddInstruction(goto_preheader);
+
+ HInstruction* suspend_check_header = new (GetAllocator()) HSuspendCheck();
+ HInstruction* call_header = MakeInvoke(DataType::Type::kBool, {});
+ HInstruction* if_header = new (GetAllocator()) HIf(call_header);
+ loop_header->AddInstruction(suspend_check_header);
+ loop_header->AddInstruction(call_header);
+ loop_header->AddInstruction(if_header);
+ call_header->CopyEnvironmentFrom(cls->GetEnvironment());
+ suspend_check_header->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ HInstruction* call_loop_body = MakeInvoke(DataType::Type::kBool, {});
+ HInstruction* if_loop_body = new (GetAllocator()) HIf(call_loop_body);
+ loop_body->AddInstruction(call_loop_body);
+ loop_body->AddInstruction(if_loop_body);
+ call_loop_body->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ HInstruction* call_loop_left = MakeInvoke(DataType::Type::kVoid, {});
+ HInstruction* goto_loop_left = new (GetAllocator()) HGoto();
+ loop_if_left->AddInstruction(call_loop_left);
+ loop_if_left->AddInstruction(goto_loop_left);
+ call_loop_left->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ HInstruction* read_loop_right = MakeIFieldGet(new_inst, DataType::Type::kInt32, MemberOffset(32));
+ HInstruction* add_loop_right =
+ new (GetAllocator()) HAdd(DataType::Type::kInt32, c5, read_loop_right);
+ HInstruction* write_loop_right = MakeIFieldSet(new_inst, add_loop_right, MemberOffset(32));
+ HInstruction* call_loop_right = MakeInvoke(DataType::Type::kVoid, {});
+ HInstruction* goto_loop_right = new (GetAllocator()) HGoto();
+ loop_if_right->AddInstruction(read_loop_right);
+ loop_if_right->AddInstruction(add_loop_right);
+ loop_if_right->AddInstruction(write_loop_right);
+ loop_if_right->AddInstruction(call_loop_right);
+ loop_if_right->AddInstruction(goto_loop_right);
+ call_loop_right->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ HInstruction* call_escape = MakeInvoke(DataType::Type::kVoid, { new_inst });
+ HInstruction* goto_escape = new (GetAllocator()) HGoto();
+ escape->AddInstruction(call_escape);
+ escape->AddInstruction(goto_escape);
+ call_escape->CopyEnvironmentFrom(cls->GetEnvironment());
+
+ HInstruction* goto_right = new (GetAllocator()) HGoto();
+ right->AddInstruction(goto_right);
+
+ HInstruction* read_bottom = MakeIFieldGet(new_inst, DataType::Type::kInt32, MemberOffset(32));
+ HInstruction* return_exit = new (GetAllocator()) HReturn(read_bottom);
+ breturn->AddInstruction(read_bottom);
+ breturn->AddInstruction(return_exit);
+
+ SetupExit(exit);
+
+ // PerformLSE expects this to be empty.
+ graph_->ClearDominanceInformation();
+ LOG(INFO) << "Pre LSE " << blks;
+ PerformLSEWithPartial();
+ LOG(INFO) << "Post LSE " << blks;
+
+ HPredicatedInstanceFieldGet* pred_get =
+ FindSingleInstruction<HPredicatedInstanceFieldGet>(graph_, breturn);
+ EXPECT_INS_REMOVED(read_bottom) << *read_bottom;
+ ASSERT_TRUE(pred_get != nullptr);
+ HPhi* inst_return_phi = pred_get->GetTarget()->AsPhi();
+ ASSERT_TRUE(inst_return_phi != nullptr) << pred_get->GetTarget()->DumpWithArgs();
+ EXPECT_INS_EQ(inst_return_phi->InputAt(0),
+ FindSingleInstruction<HNewInstance>(graph_, escape->GetSinglePredecessor()));
+ EXPECT_INS_EQ(inst_return_phi->InputAt(1), graph_->GetNullConstant());
+ EXPECT_INS_EQ(pred_get->GetDefaultValue()->InputAt(0), graph_->GetIntConstant(0));
+ EXPECT_INS_EQ(pred_get->GetDefaultValue()->InputAt(1), c3);
+ HPhi* loop_header_phi = FindSingleInstruction<HPhi>(graph_, loop_header);
+ ASSERT_NE(loop_header_phi, nullptr);
+ EXPECT_INS_EQ(loop_header_phi->InputAt(0), c3);
+ EXPECT_INS_EQ(loop_header_phi->InputAt(1), loop_header_phi);
+ EXPECT_INS_EQ(loop_header_phi->InputAt(2), add_loop_right);
+ EXPECT_INS_EQ(add_loop_right->InputAt(0), c5);
+ EXPECT_INS_EQ(add_loop_right->InputAt(1), loop_header_phi);
+ HInstanceFieldSet* mat_set =
+ FindSingleInstruction<HInstanceFieldSet>(graph_, escape->GetSinglePredecessor());
+ ASSERT_NE(mat_set, nullptr);
+ EXPECT_INS_EQ(mat_set->InputAt(1), loop_header_phi);
+ EXPECT_INS_REMOVED(write_loop_right);
+ EXPECT_INS_REMOVED(write_entry);
+ EXPECT_INS_RETAINED(call_header);
+ EXPECT_INS_RETAINED(call_loop_left);
+ EXPECT_INS_RETAINED(call_loop_right);
+}
+
// TODO This should really be in an Instruction simplifier Gtest but (1) that
// doesn't exist and (2) we should move this simplification to directly in the
// LSE pass since there is more information then.