1 // Copyright 2014 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
5 #include "src/compiler/graph-reducer.h"
9 #include "src/compiler/graph-inl.h"
15 GraphReducer::GraphReducer(Graph* graph)
16 : graph_(graph), reducers_(graph->zone()) {}
19 static bool NodeIdIsLessThan(const Node* node, NodeId id) {
20 return node->id() < id;
24 void GraphReducer::ReduceNode(Node* node) {
25 ZoneVector<Reducer*>::iterator skip = reducers_.end();
26 static const unsigned kMaxAttempts = 16;
28 for (unsigned attempts = 0; attempts <= kMaxAttempts; ++attempts) {
30 reduce = false; // Assume we don't need to rerun any reducers.
31 int before = graph_->NodeCount();
32 for (ZoneVector<Reducer*>::iterator i = reducers_.begin();
33 i != reducers_.end(); ++i) {
34 if (i == skip) continue; // Skip this reducer.
35 Reduction reduction = (*i)->Reduce(node);
36 Node* replacement = reduction.replacement();
37 if (replacement == NULL) {
38 // No change from this reducer.
39 } else if (replacement == node) {
40 // {replacement == node} represents an in-place reduction.
41 // Rerun all the reducers except the current one for this node,
42 // as now there may be more opportunities for reduction.
47 if (node == graph_->start()) graph_->SetStart(replacement);
48 if (node == graph_->end()) graph_->SetEnd(replacement);
49 // If {node} was replaced by an old node, unlink {node} and assume that
50 // {replacement} was already reduced and finish.
51 if (replacement->id() < before) {
52 node->ReplaceUses(replacement);
56 // Otherwise, {node} was replaced by a new node. Replace all old uses of
57 // {node} with {replacement}. New nodes created by this reduction can
60 std::bind2nd(std::ptr_fun(&NodeIdIsLessThan), before), replacement);
61 // Unlink {node} if it's no longer used.
62 if (node->uses().empty()) {
65 // Rerun all the reductions on the {replacement}.
66 skip = reducers_.end();
76 // A helper class to reuse the node traversal algorithm.
77 struct GraphReducerVisitor FINAL : public NullNodeVisitor {
78 explicit GraphReducerVisitor(GraphReducer* reducer) : reducer_(reducer) {}
79 GenericGraphVisit::Control Post(Node* node) {
80 reducer_->ReduceNode(node);
81 return GenericGraphVisit::CONTINUE;
83 GraphReducer* reducer_;
87 void GraphReducer::ReduceGraph() {
88 GraphReducerVisitor visitor(this);
89 // Perform a post-order reduction of all nodes starting from the end.
90 graph()->VisitNodeInputsFromEnd(&visitor);
94 // TODO(titzer): partial graph reductions.
96 } // namespace compiler
97 } // namespace internal