[vm/compiler] Fix non-convergence in constant propagator.
Given cyclic phi which participates in strict or equality comparison
with its own argument
y <- phi(x, y);
z <- y == x
CP pass would sometimes fail to converge because it would mark the phi
as unwrapped and then add it to the worklist, which would cause the
phi uses to be revisited: equality would mark the phi again and then
phi will be visited as its own use, which would add it to the worklist
because it is marked and so on.
The fix is to only add marked phis to worklist when reachability of
one of the predecessor blocks changes and that affects whether phi
can be unwrapped or not.
Test is included in a separate CL to make this fix easy to cherry pick.
Fixes https://github.com/flutter/flutter/issues/53903
Change-Id: I9e09a155d7109b7e19ba3ae5aff3fab57dc67fb8
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/143581
Reviewed-by: Martin Kustermann <kustermann@google.com>
Reviewed-by: Alexander Markov <alexmarkov@google.com>
diff --git a/runtime/vm/compiler/backend/constant_propagator.cc b/runtime/vm/compiler/backend/constant_propagator.cc
index 77c9aca..bbaeaab 100644
--- a/runtime/vm/compiler/backend/constant_propagator.cc
+++ b/runtime/vm/compiler/backend/constant_propagator.cc
@@ -36,7 +36,8 @@
non_constant_(Object::non_constant()),
constant_value_(Object::Handle(Z)),
reachable_(new (Z) BitVector(Z, graph->preorder().length())),
- marked_phis_(new (Z) BitVector(Z, graph->max_virtual_register_number())),
+ unwrapped_phis_(new (Z)
+ BitVector(Z, graph->max_virtual_register_number())),
block_worklist_(),
definition_worklist_(graph, 10) {}
@@ -218,7 +219,16 @@
// Phi value depends on the reachability of a predecessor. We have
// to revisit phis every time a predecessor becomes reachable.
for (PhiIterator it(instr->successor()); !it.Done(); it.Advance()) {
- it.Current()->Accept(this);
+ PhiInstr* phi = it.Current();
+ phi->Accept(this);
+
+ // If this phi was previously unwrapped as redundant and it is no longer
+ // redundant (does not unwrap) then we need to revisit the uses.
+ if (unwrapped_phis_->Contains(phi->ssa_temp_index()) &&
+ (UnwrapPhi(phi) == phi)) {
+ unwrapped_phis_->Remove(phi->ssa_temp_index());
+ definition_worklist_.Add(phi);
+ }
}
}
@@ -313,9 +323,9 @@
return defn;
}
-void ConstantPropagator::MarkPhi(Definition* phi) {
+void ConstantPropagator::MarkUnwrappedPhi(Definition* phi) {
ASSERT(phi->IsPhi());
- marked_phis_->Add(phi->ssa_temp_index());
+ unwrapped_phis_->Add(phi->ssa_temp_index());
}
// --------------------------------------------------------------------------
@@ -332,11 +342,7 @@
Join(&value, instr->InputAt(pred_idx)->definition()->constant_value());
}
}
- if (!SetValue(instr, value) &&
- marked_phis_->Contains(instr->ssa_temp_index())) {
- marked_phis_->Remove(instr->ssa_temp_index());
- definition_worklist_.Add(instr);
- }
+ SetValue(instr, value);
}
void ConstantPropagator::VisitRedefinition(RedefinitionInstr* instr) {
@@ -521,12 +527,13 @@
Definition* unwrapped_right_defn = UnwrapPhi(right_defn);
if (unwrapped_left_defn == unwrapped_right_defn) {
// Fold x === x, and x !== x to true/false.
- SetValue(instr, Bool::Get(instr->kind() == Token::kEQ_STRICT));
- if (unwrapped_left_defn != left_defn) {
- MarkPhi(left_defn);
- }
- if (unwrapped_right_defn != right_defn) {
- MarkPhi(right_defn);
+ if (SetValue(instr, Bool::Get(instr->kind() == Token::kEQ_STRICT))) {
+ if (unwrapped_left_defn != left_defn) {
+ MarkUnwrappedPhi(left_defn);
+ }
+ if (unwrapped_right_defn != right_defn) {
+ MarkUnwrappedPhi(right_defn);
+ }
}
return;
}
@@ -624,12 +631,13 @@
Definition* unwrapped_right_defn = UnwrapPhi(right_defn);
if (unwrapped_left_defn == unwrapped_right_defn) {
// Fold x === x, and x !== x to true/false.
- SetValue(instr, Bool::Get(instr->kind() == Token::kEQ));
- if (unwrapped_left_defn != left_defn) {
- MarkPhi(left_defn);
- }
- if (unwrapped_right_defn != right_defn) {
- MarkPhi(right_defn);
+ if (SetValue(instr, Bool::Get(instr->kind() == Token::kEQ))) {
+ if (unwrapped_left_defn != left_defn) {
+ MarkUnwrappedPhi(left_defn);
+ }
+ if (unwrapped_right_defn != right_defn) {
+ MarkUnwrappedPhi(right_defn);
+ }
}
return;
}
diff --git a/runtime/vm/compiler/backend/constant_propagator.h b/runtime/vm/compiler/backend/constant_propagator.h
index a5b939a..f303fc6 100644
--- a/runtime/vm/compiler/backend/constant_propagator.h
+++ b/runtime/vm/compiler/backend/constant_propagator.h
@@ -49,8 +49,12 @@
void SetReachable(BlockEntryInstr* block);
bool SetValue(Definition* definition, const Object& value);
+ // Phi might be viewed as redundant based on current reachability of
+ // predecessor blocks (i.e. the same definition is flowing from all
+ // reachable predecessors). We can use this information to constant
+ // fold phi(x) == x and phi(x) != x comparisons.
Definition* UnwrapPhi(Definition* defn);
- void MarkPhi(Definition* defn);
+ void MarkUnwrappedPhi(Definition* defn);
// Assign the join (least upper bound) of a pair of abstract values to the
// first one.
@@ -88,7 +92,11 @@
// preorder number.
BitVector* reachable_;
- BitVector* marked_phis_;
+ // Bitvector of phis that were "unwrapped" into one of their inputs
+ // when visiting one of their uses. These uses of these phis
+ // should be revisited if reachability of the predecessor blocks
+ // changes even if that does not change constant value of the phi.
+ BitVector* unwrapped_phis_;
// Worklists of blocks and definitions.
GrowableArray<BlockEntryInstr*> block_worklist_;
