From 27cc3c685c2fc7f0ce89585499cba2f620f8c4bc Mon Sep 17 00:00:00 2001 From: Benedikt Meurer Date: Fri, 14 Nov 2014 12:48:37 +0100 Subject: [PATCH] Revert "[turbofan] Smartify the GraphReducer." This reverts commit 6e148989a4227a5290a7f8ca72c71f5740870afe for breaking Massive/Embenchen. TBR=machenbach@chromium.org Review URL: https://codereview.chromium.org/727743002 Cr-Commit-Position: refs/heads/master@{#25356} --- src/compiler/graph-reducer.cc | 202 ++++-------------- src/compiler/graph-reducer.h | 25 +-- src/compiler/pipeline.cc | 12 +- src/zone-containers.h | 25 +-- test/cctest/compiler/test-changes-lowering.cc | 2 +- test/cctest/compiler/test-graph-reducer.cc | 28 +-- .../compiler/test-simplified-lowering.cc | 2 +- .../compiler/graph-reducer-unittest.cc | 8 +- 8 files changed, 77 insertions(+), 227 deletions(-) diff --git a/src/compiler/graph-reducer.cc b/src/compiler/graph-reducer.cc index ff04f6ba5..f716b2a57 100644 --- a/src/compiler/graph-reducer.cc +++ b/src/compiler/graph-reducer.cc @@ -12,189 +12,79 @@ namespace v8 { namespace internal { namespace compiler { -enum class GraphReducer::State : uint8_t { - kUnvisited, - kRevisit, - kOnStack, - kVisited -}; - - -GraphReducer::GraphReducer(Graph* graph, Zone* zone) - : graph_(graph), - reducers_(zone), - revisit_(zone), - stack_(zone), - state_(zone) {} +GraphReducer::GraphReducer(Graph* graph) + : graph_(graph), reducers_(graph->zone()) {} -void GraphReducer::AddReducer(Reducer* reducer) { - reducers_.push_back(reducer); +static bool NodeIdIsLessThan(const Node* node, NodeId id) { + return node->id() < id; } void GraphReducer::ReduceNode(Node* node) { - DCHECK(stack_.empty()); - DCHECK(revisit_.empty()); - std::fill(state_.begin(), state_.end(), State::kUnvisited); - Push(node); - for (;;) { - DCHECK(!stack_.empty() || - std::find(state_.begin(), state_.end(), State::kOnStack) == - state_.end()); - if (!stack_.empty()) { - // Process the node on the top of the stack, potentially pushing more or - // popping the node off the stack. - ReduceTop(); - } else if (!revisit_.empty()) { - // If the stack becomes empty, revisit any nodes in the revisit queue. - Node* const node = revisit_.top(); - revisit_.pop(); - if (state_[node->id()] == State::kRevisit) { - // state can change while in queue. - Push(node); - } - } else { - break; - } - } - DCHECK(std::find(state_.begin(), state_.end(), State::kOnStack) == - state_.end()); - DCHECK(revisit_.empty()); - DCHECK(stack_.empty()); -} - - -void GraphReducer::ReduceGraph() { ReduceNode(graph()->end()); } - - -Reduction GraphReducer::Reduce(Node* const node) { - auto skip = reducers_.end(); - for (auto i = reducers_.begin(); i != reducers_.end();) { - if (i != skip) { + static const unsigned kMaxAttempts = 16; + bool reduce = true; + for (unsigned attempts = 0; attempts <= kMaxAttempts; ++attempts) { + if (!reduce) return; + reduce = false; // Assume we don't need to rerun any reducers. + int before = graph_->NodeCount(); + for (ZoneVector::iterator i = reducers_.begin(); + i != reducers_.end(); ++i) { Reduction reduction = (*i)->Reduce(node); - if (!reduction.Changed()) { + Node* replacement = reduction.replacement(); + if (replacement == NULL) { // No change from this reducer. - } else if (reduction.replacement() == node) { - // {replacement} == {node} represents an in-place reduction. Rerun - // all the other reducers for this node, as now there may be more + } else if (replacement == node) { + // {replacement == node} represents an in-place reduction. + // Rerun all the reducers for this node, as now there may be more // opportunities for reduction. - skip = i; - i = reducers_.begin(); - continue; + reduce = true; + break; } else { - // {node} was replaced by another node. - return reduction; - } - } - ++i; - } - if (skip == reducers_.end()) { - // No change from any reducer. - return Reducer::NoChange(); - } - // At least one reducer did some in-place reduction. - return Reducer::Changed(node); -} - - -void GraphReducer::ReduceTop() { - Node* const node = Top(); - if (node->IsDead()) return Pop(); // Node was killed while on stack. - - // Recurse on an input if necessary. - for (auto const input : node->inputs()) { - if (input != node && Recurse(input)) return; - } - - // Remember the node count before reduction. - const int node_count = graph()->NodeCount(); - - // All inputs should be visited or on stack. Apply reductions to node. - Reduction reduction = Reduce(node); - - // After reducing the node, pop it off the stack. - Pop(); - - // If there was a reduction, revisit the uses and reduce the replacement. - if (reduction.Changed()) { - for (Node* const use : node->uses()) { - // Don't revisit this node if it refers to itself. - if (use != node) Revisit(use); - } - Node* const replacement = reduction.replacement(); - if (replacement != node) { - if (node == graph()->start()) graph()->SetStart(replacement); - if (node == graph()->end()) graph()->SetEnd(replacement); - // If {node} was replaced by an old node, unlink {node} and assume that - // {replacement} was already reduced and finish. - if (replacement->id() < node_count) { - node->ReplaceUses(replacement); - node->Kill(); - } else { - // Otherwise {node} was replaced by a new node. Replace all old uses of + if (node == graph_->start()) graph_->SetStart(replacement); + if (node == graph_->end()) graph_->SetEnd(replacement); + // If {node} was replaced by an old node, unlink {node} and assume that + // {replacement} was already reduced and finish. + if (replacement->id() < before) { + node->ReplaceUses(replacement); + node->Kill(); + return; + } + // Otherwise, {node} was replaced by a new node. Replace all old uses of // {node} with {replacement}. New nodes created by this reduction can // use {node}. - node->ReplaceUsesIf([node_count](Node* const node) { - return node->id() < node_count; - }, - replacement); + node->ReplaceUsesIf( + std::bind2nd(std::ptr_fun(&NodeIdIsLessThan), before), replacement); // Unlink {node} if it's no longer used. if (node->uses().empty()) { node->Kill(); } - - // If there was a replacement, reduce it after popping {node}. - Recurse(replacement); + // Rerun all the reductions on the {replacement}. + node = replacement; + reduce = true; + break; } } } } -void GraphReducer::Pop() { - Node* const node = Top(); - state_[node->id()] = State::kVisited; - stack_.pop(); -} - - -void GraphReducer::Push(Node* const node) { - size_t const id = static_cast(node->id()); - if (id >= state_.size()) state_.resize(id + 1); - DCHECK(id < state_.size()); - DCHECK(state_[id] != State::kOnStack); - state_[id] = State::kOnStack; - stack_.push(node); -} - - -Node* GraphReducer::Top() const { - DCHECK(!stack_.empty()); - Node* const node = stack_.top(); - size_t const id = static_cast(node->id()); - DCHECK(id < state_.size()); - DCHECK(state_[id] == State::kOnStack); - USE(id); - return node; -} +// A helper class to reuse the node traversal algorithm. +struct GraphReducerVisitor FINAL : public NullNodeVisitor { + explicit GraphReducerVisitor(GraphReducer* reducer) : reducer_(reducer) {} + void Post(Node* node) { reducer_->ReduceNode(node); } + GraphReducer* reducer_; +}; -bool GraphReducer::Recurse(Node* const node) { - size_t const id = static_cast(node->id()); - if (id < state_.size() && state_[id] > State::kRevisit) return false; - Push(node); - return true; +void GraphReducer::ReduceGraph() { + GraphReducerVisitor visitor(this); + // Perform a post-order reduction of all nodes starting from the end. + graph()->VisitNodeInputsFromEnd(&visitor); } -void GraphReducer::Revisit(Node* const node) { - size_t const id = static_cast(node->id()); - if (id < state_.size() && state_[id] == State::kVisited) { - state_[id] = State::kRevisit; - revisit_.push(node); - } -} +// TODO(titzer): partial graph reductions. } // namespace compiler } // namespace internal diff --git a/src/compiler/graph-reducer.h b/src/compiler/graph-reducer.h index d54c3186c..e0e4f7a3d 100644 --- a/src/compiler/graph-reducer.h +++ b/src/compiler/graph-reducer.h @@ -55,39 +55,20 @@ class Reducer { // Performs an iterative reduction of a node graph. class GraphReducer FINAL { public: - GraphReducer(Graph* graph, Zone* zone); + explicit GraphReducer(Graph* graph); Graph* graph() const { return graph_; } - void AddReducer(Reducer* reducer); + void AddReducer(Reducer* reducer) { reducers_.push_back(reducer); } // Reduce a single node. - void ReduceNode(Node* const); + void ReduceNode(Node* node); // Reduce the whole graph. void ReduceGraph(); private: - enum class State : uint8_t; - - // Reduce a single node. - Reduction Reduce(Node* const); - // Reduce the node on top of the stack. - void ReduceTop(); - - // Node stack operations. - void Pop(); - void Push(Node* const); - Node* Top() const; - - // Revisit queue operations. - bool Recurse(Node* const); - void Revisit(Node* const); - Graph* graph_; ZoneVector reducers_; - ZoneStack revisit_; - ZoneStack stack_; - ZoneDeque state_; DISALLOW_COPY_AND_ASSIGN(GraphReducer); }; diff --git a/src/compiler/pipeline.cc b/src/compiler/pipeline.cc index e4d8c5d46..a05e2b3e3 100644 --- a/src/compiler/pipeline.cc +++ b/src/compiler/pipeline.cc @@ -386,13 +386,12 @@ Handle Pipeline::GenerateCode() { { // Lower JSOperators where we can determine types. PhaseScope phase_scope(pipeline_statistics.get(), "typed lowering"); - ZonePool::Scope zone_scope(data.zone_pool()); SourcePositionTable::Scope pos(data.source_positions(), SourcePosition::Unknown()); ValueNumberingReducer vn_reducer(data.graph_zone()); JSTypedLowering lowering(data.jsgraph()); SimplifiedOperatorReducer simple_reducer(data.jsgraph()); - GraphReducer graph_reducer(data.graph(), zone_scope.zone()); + GraphReducer graph_reducer(data.graph()); graph_reducer.AddReducer(&vn_reducer); graph_reducer.AddReducer(&lowering); graph_reducer.AddReducer(&simple_reducer); @@ -403,14 +402,13 @@ Handle Pipeline::GenerateCode() { { // Lower simplified operators and insert changes. PhaseScope phase_scope(pipeline_statistics.get(), "simplified lowering"); - ZonePool::Scope zone_scope(data.zone_pool()); SourcePositionTable::Scope pos(data.source_positions(), SourcePosition::Unknown()); SimplifiedLowering lowering(data.jsgraph()); lowering.LowerAllNodes(); ValueNumberingReducer vn_reducer(data.graph_zone()); SimplifiedOperatorReducer simple_reducer(data.jsgraph()); - GraphReducer graph_reducer(data.graph(), zone_scope.zone()); + GraphReducer graph_reducer(data.graph()); graph_reducer.AddReducer(&vn_reducer); graph_reducer.AddReducer(&simple_reducer); graph_reducer.ReduceGraph(); @@ -420,7 +418,6 @@ Handle Pipeline::GenerateCode() { { // Lower changes that have been inserted before. PhaseScope phase_scope(pipeline_statistics.get(), "change lowering"); - ZonePool::Scope zone_scope(data.zone_pool()); SourcePositionTable::Scope pos(data.source_positions(), SourcePosition::Unknown()); Linkage linkage(data.graph_zone(), info()); @@ -428,7 +425,7 @@ Handle Pipeline::GenerateCode() { SimplifiedOperatorReducer simple_reducer(data.jsgraph()); ChangeLowering lowering(data.jsgraph(), &linkage); MachineOperatorReducer mach_reducer(data.jsgraph()); - GraphReducer graph_reducer(data.graph(), zone_scope.zone()); + GraphReducer graph_reducer(data.graph()); // TODO(titzer): Figure out if we should run all reducers at once here. graph_reducer.AddReducer(&vn_reducer); graph_reducer.AddReducer(&simple_reducer); @@ -456,12 +453,11 @@ Handle Pipeline::GenerateCode() { { // Lower any remaining generic JSOperators. PhaseScope phase_scope(pipeline_statistics.get(), "generic lowering"); - ZonePool::Scope zone_scope(data.zone_pool()); SourcePositionTable::Scope pos(data.source_positions(), SourcePosition::Unknown()); JSGenericLowering generic(info(), data.jsgraph()); SelectLowering select(data.jsgraph()->graph(), data.jsgraph()->common()); - GraphReducer graph_reducer(data.graph(), zone_scope.zone()); + GraphReducer graph_reducer(data.graph()); graph_reducer.AddReducer(&generic); graph_reducer.AddReducer(&select); graph_reducer.ReduceGraph(); diff --git a/src/zone-containers.h b/src/zone-containers.h index 887ac1c54..4998cbf3f 100644 --- a/src/zone-containers.h +++ b/src/zone-containers.h @@ -7,7 +7,6 @@ #include #include -#include #include #include "src/zone-allocator.h" @@ -37,45 +36,29 @@ class ZoneVector : public std::vector > { } }; - // A wrapper subclass std::deque to make it easy to construct one // that uses a zone allocator. template class ZoneDeque : public std::deque > { public: - // Constructs an empty deque. explicit ZoneDeque(Zone* zone) : std::deque >(zone_allocator(zone)) {} }; - // A wrapper subclass for std::queue to make it easy to construct one // that uses a zone allocator. template -class ZoneQueue : public std::queue> { +class ZoneQueue : public std::queue > > { public: // Constructs an empty queue. explicit ZoneQueue(Zone* zone) - : std::queue>(ZoneDeque(zone)) {} + : std::queue > >( + std::deque >(zone_allocator(zone))) {} }; - -// A wrapper subclass for std::stack to make it easy to construct one that uses -// a zone allocator. -template -class ZoneStack : public std::stack> { - public: - // Constructs an empty stack. - explicit ZoneStack(Zone* zone) - : std::stack>(ZoneDeque(zone)) {} -}; - - // Typedefs to shorten commonly used vectors. typedef ZoneVector BoolVector; typedef ZoneVector IntVector; - -} // namespace internal -} // namespace v8 +} } // namespace v8::internal #endif // V8_ZONE_CONTAINERS_H_ diff --git a/test/cctest/compiler/test-changes-lowering.cc b/test/cctest/compiler/test-changes-lowering.cc index 34c8c5bb6..02ba4a7fb 100644 --- a/test/cctest/compiler/test-changes-lowering.cc +++ b/test/cctest/compiler/test-changes-lowering.cc @@ -129,7 +129,7 @@ class ChangesLoweringTester : public GraphBuilderTester { Linkage linkage(this->zone(), &info); ChangeLowering change_lowering(&jsgraph, &linkage); SelectLowering select_lowering(this->graph(), this->common()); - GraphReducer reducer(this->graph(), this->zone()); + GraphReducer reducer(this->graph()); reducer.AddReducer(&change_lowering); reducer.AddReducer(&select_lowering); reducer.ReduceNode(change); diff --git a/test/cctest/compiler/test-graph-reducer.cc b/test/cctest/compiler/test-graph-reducer.cc index 576fee29e..7f217d705 100644 --- a/test/cctest/compiler/test-graph-reducer.cc +++ b/test/cctest/compiler/test-graph-reducer.cc @@ -202,7 +202,7 @@ TEST(ReduceGraphFromEnd1) { Node* end = graph.NewNode(&OPA1, n1); graph.SetEnd(end); - GraphReducer reducer(&graph, graph.zone()); + GraphReducer reducer(&graph); ReducerRecorder recorder(graph.zone()); reducer.AddReducer(&recorder); reducer.ReduceGraph(); @@ -220,7 +220,7 @@ TEST(ReduceGraphFromEnd2) { Node* end = graph.NewNode(&OPA2, n2, n3); graph.SetEnd(end); - GraphReducer reducer(&graph, graph.zone()); + GraphReducer reducer(&graph); ReducerRecorder recorder(graph.zone()); reducer.AddReducer(&recorder); reducer.ReduceGraph(); @@ -238,7 +238,7 @@ TEST(ReduceInPlace1) { Node* end = graph.NewNode(&OPA1, n1); graph.SetEnd(end); - GraphReducer reducer(&graph, graph.zone()); + GraphReducer reducer(&graph); InPlaceABReducer r; reducer.AddReducer(&r); @@ -263,7 +263,7 @@ TEST(ReduceInPlace2) { Node* end = graph.NewNode(&OPA2, n2, n3); graph.SetEnd(end); - GraphReducer reducer(&graph, graph.zone()); + GraphReducer reducer(&graph); InPlaceABReducer r; reducer.AddReducer(&r); @@ -293,7 +293,7 @@ TEST(ReduceNew1) { Node* end = graph.NewNode(&OPA2, n2, n3); graph.SetEnd(end); - GraphReducer reducer(&graph, graph.zone()); + GraphReducer reducer(&graph); NewABReducer r(&graph); reducer.AddReducer(&r); @@ -330,7 +330,7 @@ TEST(Wrapping1) { graph.SetEnd(end); CHECK_EQ(1, graph.NodeCount()); - GraphReducer reducer(&graph, graph.zone()); + GraphReducer reducer(&graph); A0Wrapper r(&graph); reducer.AddReducer(&r); @@ -352,7 +352,7 @@ TEST(Wrapping2) { graph.SetEnd(end); CHECK_EQ(1, graph.NodeCount()); - GraphReducer reducer(&graph, graph.zone()); + GraphReducer reducer(&graph); B0Wrapper r(&graph); reducer.AddReducer(&r); @@ -379,7 +379,7 @@ TEST(Forwarding1) { Node* end = graph.NewNode(&OPA1, n1); graph.SetEnd(end); - GraphReducer reducer(&graph, graph.zone()); + GraphReducer reducer(&graph); A1Forwarder r; reducer.AddReducer(&r); @@ -403,7 +403,7 @@ TEST(Forwarding2) { Node* end = graph.NewNode(&OPA2, n2, n3); graph.SetEnd(end); - GraphReducer reducer(&graph, graph.zone()); + GraphReducer reducer(&graph); A1Forwarder r; reducer.AddReducer(&r); @@ -434,7 +434,7 @@ TEST(Forwarding3) { } graph.SetEnd(end); - GraphReducer reducer(&graph, graph.zone()); + GraphReducer reducer(&graph); A1Forwarder r; reducer.AddReducer(&r); @@ -458,7 +458,7 @@ TEST(ReduceForward1) { Node* end = graph.NewNode(&OPA2, n2, n3); graph.SetEnd(end); - GraphReducer reducer(&graph, graph.zone()); + GraphReducer reducer(&graph); InPlaceABReducer r; B1Forwarder f; reducer.AddReducer(&r); @@ -501,7 +501,7 @@ TEST(Sorter1) { graph.SetEnd(end); - GraphReducer reducer(&graph, graph.zone()); + GraphReducer reducer(&graph); reducer.AddReducer(&r); int before = graph.NodeCount(); @@ -560,7 +560,7 @@ TEST(SortForwardReduce) { GenDAG(&graph, p3, p2, p1); - GraphReducer reducer(&graph, graph.zone()); + GraphReducer reducer(&graph); AB2Sorter r1; A1Forwarder r2; InPlaceABReducer r3; @@ -599,7 +599,7 @@ TEST(Order) { Node* end = graph.NewNode(&OPA1, n1); graph.SetEnd(end); - GraphReducer reducer(&graph, graph.zone()); + GraphReducer reducer(&graph); InPlaceABReducer abr; InPlaceBCReducer bcr; if (i == 0) { diff --git a/test/cctest/compiler/test-simplified-lowering.cc b/test/cctest/compiler/test-simplified-lowering.cc index a87831728..7fe493366 100644 --- a/test/cctest/compiler/test-simplified-lowering.cc +++ b/test/cctest/compiler/test-simplified-lowering.cc @@ -63,7 +63,7 @@ class SimplifiedLoweringTester : public GraphBuilderTester { Linkage linkage( zone, Linkage::GetSimplifiedCDescriptor(zone, this->machine_sig_)); ChangeLowering lowering(&jsgraph, &linkage); - GraphReducer reducer(this->graph(), this->zone()); + GraphReducer reducer(this->graph()); reducer.AddReducer(&lowering); reducer.ReduceGraph(); Verifier::Run(this->graph()); diff --git a/test/unittests/compiler/graph-reducer-unittest.cc b/test/unittests/compiler/graph-reducer-unittest.cc index dbdd4bb62..88f25f7b1 100644 --- a/test/unittests/compiler/graph-reducer-unittest.cc +++ b/test/unittests/compiler/graph-reducer-unittest.cc @@ -55,20 +55,20 @@ class GraphReducerTest : public TestWithZone { protected: void ReduceNode(Node* node, Reducer* r) { - GraphReducer reducer(graph(), zone()); + GraphReducer reducer(graph()); reducer.AddReducer(r); reducer.ReduceNode(node); } void ReduceNode(Node* node, Reducer* r1, Reducer* r2) { - GraphReducer reducer(graph(), zone()); + GraphReducer reducer(graph()); reducer.AddReducer(r1); reducer.AddReducer(r2); reducer.ReduceNode(node); } void ReduceNode(Node* node, Reducer* r1, Reducer* r2, Reducer* r3) { - GraphReducer reducer(graph(), zone()); + GraphReducer reducer(graph()); reducer.AddReducer(r1); reducer.AddReducer(r2); reducer.AddReducer(r3); @@ -87,7 +87,6 @@ TEST_F(GraphReducerTest, NodeIsDeadAfterReplace) { Node* node0 = graph()->NewNode(&OP0); Node* node1 = graph()->NewNode(&OP1, node0); Node* node2 = graph()->NewNode(&OP1, node0); - EXPECT_CALL(r, Reduce(node0)).WillOnce(Return(Reducer::NoChange())); EXPECT_CALL(r, Reduce(node1)).WillOnce(Return(Reducer::Replace(node2))); ReduceNode(node1, &r); EXPECT_FALSE(node0->IsDead()); @@ -115,6 +114,7 @@ TEST_F(GraphReducerTest, ReduceAgainAfterChanged) { Return(Reducer::Changed(node0))); EXPECT_CALL(r1, Reduce(node0)).InSequence(s1); EXPECT_CALL(r2, Reduce(node0)).InSequence(s2); + EXPECT_CALL(r3, Reduce(node0)).InSequence(s3); ReduceNode(node0, &r1, &r2, &r3); } -- 2.34.1