[vm/compiler] Add check to detect constant propagator divergence.
Add test for https://github.com/flutter/flutter/issues/53903
Change-Id: Iae7253e022c07358697a155718d3b5745ed6bee5
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/143582
Commit-Queue: Vyacheslav Egorov <vegorov@google.com>
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 bbaeaab..60c3670 100644
--- a/runtime/vm/compiler/backend/constant_propagator.cc
+++ b/runtime/vm/compiler/backend/constant_propagator.cc
@@ -328,11 +328,50 @@
unwrapped_phis_->Add(phi->ssa_temp_index());
}
+ConstantPropagator::PhiInfo* ConstantPropagator::GetPhiInfo(PhiInstr* phi) {
+ if (phi->HasPassSpecificId(CompilerPass::kConstantPropagation)) {
+ const intptr_t id =
+ phi->GetPassSpecificId(CompilerPass::kConstantPropagation);
+ // Note: id might have been assigned by the previous round of constant
+ // propagation, so we need to verify it before using it.
+ if (id < phis_.length() && phis_[id].phi == phi) {
+ return &phis_[id];
+ }
+ }
+
+ phi->SetPassSpecificId(CompilerPass::kConstantPropagation, phis_.length());
+ phis_.Add({phi, 0});
+ return &phis_.Last();
+}
+
// --------------------------------------------------------------------------
// Analysis of definitions. Compute the constant value. If it has changed
// and the definition has input uses, add the definition to the definition
// worklist so that the used can be processed.
void ConstantPropagator::VisitPhi(PhiInstr* instr) {
+ // Detect convergence issues by checking if visit count for this phi
+ // is too high. We should only visit this phi once for every predecessor
+ // becoming reachable, once for every input changing its constant value and
+ // once for an unwrapped redundant phi becoming non-redundant.
+ // Inputs can only change their constant value at most three times: from
+ // non-constant to unknown to specific constant to non-constant. The first
+ // link (non-constant to ...) can happen when we run the second round of
+ // constant propagation - some instructions can have non-constant assigned to
+ // them at the end of the previous constant propagation.
+ auto info = GetPhiInfo(instr);
+ info->visit_count++;
+ const intptr_t kMaxVisitsExpected = 5 * instr->InputCount();
+ if (info->visit_count > kMaxVisitsExpected) {
+ OS::PrintErr(
+ "ConstantPropagation pass is failing to converge on graph for %s\n",
+ graph_->parsed_function().function().ToCString());
+ OS::PrintErr("Phi %s was visited %" Pd " times\n", instr->ToCString(),
+ info->visit_count);
+ NOT_IN_PRODUCT(
+ FlowGraphPrinter::PrintGraph("Constant Propagation", graph_));
+ FATAL("Aborting due to non-covergence.");
+ }
+
// Compute the join over all the reachable predecessor values.
JoinEntryInstr* block = instr->block();
Object& value = Object::ZoneHandle(Z, Unknown());
diff --git a/runtime/vm/compiler/backend/constant_propagator.h b/runtime/vm/compiler/backend/constant_propagator.h
index f303fc6..6150081 100644
--- a/runtime/vm/compiler/backend/constant_propagator.h
+++ b/runtime/vm/compiler/backend/constant_propagator.h
@@ -75,7 +75,18 @@
#define DECLARE_VISIT(type, attrs) virtual void Visit##type(type##Instr* instr);
FOR_EACH_INSTRUCTION(DECLARE_VISIT)
+
#undef DECLARE_VISIT
+ // Structure tracking visit counts for phis. Used to detect infinite loops.
+ struct PhiInfo {
+ PhiInstr* phi;
+ intptr_t visit_count;
+ };
+
+ // Returns PhiInfo associated with the given phi. Note that this
+ // pointer can be invalidated by subsequent call to GetPhiInfo and
+ // thus should not be stored anywhere.
+ PhiInfo* GetPhiInfo(PhiInstr* phi);
Isolate* isolate() const { return graph_->isolate(); }
@@ -98,6 +109,10 @@
// changes even if that does not change constant value of the phi.
BitVector* unwrapped_phis_;
+ // List of visited phis indexed by their id (stored as pass specific id on
+ // a phi instruction).
+ GrowableArray<PhiInfo> phis_;
+
// Worklists of blocks and definitions.
GrowableArray<BlockEntryInstr*> block_worklist_;
DefinitionWorklist definition_worklist_;
diff --git a/runtime/vm/compiler/backend/constant_propagator_test.cc b/runtime/vm/compiler/backend/constant_propagator_test.cc
new file mode 100644
index 0000000..40db6b4
--- /dev/null
+++ b/runtime/vm/compiler/backend/constant_propagator_test.cc
@@ -0,0 +1,94 @@
+// Copyright (c) 2020, the Dart project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+#include "vm/compiler/backend/constant_propagator.h"
+
+#include "vm/compiler/backend/block_builder.h"
+#include "vm/compiler/backend/il_test_helper.h"
+#include "vm/unit_test.h"
+
+namespace dart {
+
+// Test issue https://github.com/flutter/flutter/issues/53903.
+//
+// If graph contains a cyclic phi which participates in an EqualityCompare
+// or StrictCompare with its input like phi(x, ...) == x then constant
+// propagation might fail to converge by constantly revisiting this phi and
+// its uses (which includes comparison and the phi itself).
+ISOLATE_UNIT_TEST_CASE(ConstantPropagation_PhiUnwrappingAndConvergence) {
+ using compiler::BlockBuilder;
+ CompilerState S(thread, /*is_aot=*/false);
+ FlowGraphBuilderHelper H;
+
+ // We are going to build the following graph:
+ //
+ // B0[graph_entry]
+ // B1[function_entry]:
+ // v0 <- Constant(0)
+ // goto B2
+ // B2:
+ // v1 <- phi(v0, v1)
+ // v2 <- EqualityCompare(v1 == v0)
+ // if v2 == true then B4 else B3
+ // B3:
+ // goto B2
+ // B4:
+ // Return(v1)
+
+ PhiInstr* v1;
+ ConstantInstr* v0 = H.IntConstant(0);
+ auto b1 = H.flow_graph()->graph_entry()->normal_entry();
+ auto b2 = H.JoinEntry();
+ auto b3 = H.TargetEntry();
+ auto b4 = H.TargetEntry();
+
+ {
+ BlockBuilder builder(H.flow_graph(), b1);
+ builder.AddInstruction(new GotoInstr(b2, S.GetNextDeoptId()));
+ }
+
+ {
+ BlockBuilder builder(H.flow_graph(), b2);
+ v1 = H.Phi(b2, {{b1, v0}, {b3, FlowGraphBuilderHelper::kPhiSelfReference}});
+ builder.AddPhi(v1);
+ auto v2 = builder.AddDefinition(new EqualityCompareInstr(
+ TokenPosition::kNoSource, Token::kEQ, new Value(v1), new Value(v0),
+ kSmiCid, S.GetNextDeoptId()));
+ builder.AddBranch(
+ new StrictCompareInstr(
+ TokenPosition::kNoSource, Token::kEQ_STRICT, new Value(v2),
+ new Value(H.flow_graph()->GetConstant(Bool::True())),
+ /*needs_number_check=*/false, S.GetNextDeoptId()),
+ b4, b3);
+ }
+
+ {
+ BlockBuilder builder(H.flow_graph(), b3);
+ builder.AddInstruction(new GotoInstr(b2, S.GetNextDeoptId()));
+ }
+
+ {
+ BlockBuilder builder(H.flow_graph(), b4);
+ builder.AddReturn(new Value(v1));
+ }
+
+ H.FinishGraph();
+
+ // Graph transformations will attempt to copy deopt information from
+ // branches and block entries which we did not assign.
+ // To disable copying we mark graph to disable LICM.
+ H.flow_graph()->disallow_licm();
+
+ ConstantPropagator::Optimize(H.flow_graph());
+
+ auto& blocks = H.flow_graph()->reverse_postorder();
+ EXPECT_EQ(2, blocks.length());
+ EXPECT_PROPERTY(blocks[0], it.IsGraphEntry());
+ EXPECT_PROPERTY(blocks[1], it.IsFunctionEntry());
+ EXPECT_PROPERTY(blocks[1]->next(), it.IsReturn());
+ EXPECT_PROPERTY(blocks[1]->next()->AsReturn(),
+ it.value()->definition() == v0);
+}
+
+} // namespace dart
diff --git a/runtime/vm/compiler/backend/il_test_helper.h b/runtime/vm/compiler/backend/il_test_helper.h
index 9655791..5232aabb 100644
--- a/runtime/vm/compiler/backend/il_test_helper.h
+++ b/runtime/vm/compiler/backend/il_test_helper.h
@@ -253,17 +253,20 @@
return flow_graph_.GetConstant(Double::Handle(Double::NewCanonical(value)));
}
+ static constexpr Definition* kPhiSelfReference = nullptr;
+
PhiInstr* Phi(JoinEntryInstr* join,
std::initializer_list<std::pair<BlockEntryInstr*, Definition*>>
- incomming) {
- auto phi = new PhiInstr(join, incomming.size());
- for (size_t i = 0; i < incomming.size(); i++) {
+ incoming) {
+ auto phi = new PhiInstr(join, incoming.size());
+ for (size_t i = 0; i < incoming.size(); i++) {
auto input = new Value(flow_graph_.constant_dead());
phi->SetInputAt(i, input);
input->definition()->AddInputUse(input);
}
- for (auto pair : incomming) {
- pending_phis_.Add({phi, pair.first, pair.second});
+ for (auto pair : incoming) {
+ pending_phis_.Add({phi, pair.first,
+ pair.second == kPhiSelfReference ? phi : pair.second});
}
return phi;
}
diff --git a/runtime/vm/compiler/compiler_sources.gni b/runtime/vm/compiler/compiler_sources.gni
index f39d83a..6b59f94 100644
--- a/runtime/vm/compiler/compiler_sources.gni
+++ b/runtime/vm/compiler/compiler_sources.gni
@@ -166,6 +166,7 @@
"assembler/assembler_x64_test.cc",
"assembler/disassembler_test.cc",
"backend/bce_test.cc",
+ "backend/constant_propagator_test.cc",
"backend/il_test.cc",
"backend/il_test_helper.h",
"backend/il_test_helper.cc",
