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.
4 
5 #include "src/compiler/graph-reducer.h"
6 
7 #include <functional>
8 
9 #include "src/compiler/graph-inl.h"
10 
11 namespace v8 {
12 namespace internal {
13 namespace compiler {
14 
GraphReducer(Graph * graph)15 GraphReducer::GraphReducer(Graph* graph)
16     : graph_(graph), reducers_(graph->zone()) {}
17 
18 
NodeIdIsLessThan(const Node * node,NodeId id)19 static bool NodeIdIsLessThan(const Node* node, NodeId id) {
20   return node->id() < id;
21 }
22 
23 
ReduceNode(Node * node)24 void GraphReducer::ReduceNode(Node* node) {
25   ZoneVector<Reducer*>::iterator skip = reducers_.end();
26   static const unsigned kMaxAttempts = 16;
27   bool reduce = true;
28   for (unsigned attempts = 0; attempts <= kMaxAttempts; ++attempts) {
29     if (!reduce) return;
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.
43         reduce = true;
44         skip = i;
45         break;
46       } else {
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);
53           node->Kill();
54           return;
55         }
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
58         // use {node}.
59         node->ReplaceUsesIf(
60             std::bind2nd(std::ptr_fun(&NodeIdIsLessThan), before), replacement);
61         // Unlink {node} if it's no longer used.
62         if (node->uses().empty()) {
63           node->Kill();
64         }
65         // Rerun all the reductions on the {replacement}.
66         skip = reducers_.end();
67         node = replacement;
68         reduce = true;
69         break;
70       }
71     }
72   }
73 }
74 
75 
76 // A helper class to reuse the node traversal algorithm.
77 struct GraphReducerVisitor FINAL : public NullNodeVisitor {
GraphReducerVisitorv8::internal::compiler::FINAL78   explicit GraphReducerVisitor(GraphReducer* reducer) : reducer_(reducer) {}
Postv8::internal::compiler::FINAL79   GenericGraphVisit::Control Post(Node* node) {
80     reducer_->ReduceNode(node);
81     return GenericGraphVisit::CONTINUE;
82   }
83   GraphReducer* reducer_;
84 };
85 
86 
ReduceGraph()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);
91 }
92 
93 
94 // TODO(titzer): partial graph reductions.
95 
96 }  // namespace compiler
97 }  // namespace internal
98 }  // namespace v8
99