OLD | NEW |
1 // Copyright 2014 the V8 project authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "src/compiler/graph-reducer.h" | 5 #include "src/compiler/graph-reducer.h" |
6 | 6 |
7 #include <functional> | 7 #include <functional> |
8 | 8 |
9 #include "src/compiler/graph-inl.h" | 9 #include "src/compiler/graph-inl.h" |
10 | 10 |
11 namespace v8 { | 11 namespace v8 { |
12 namespace internal { | 12 namespace internal { |
13 namespace compiler { | 13 namespace compiler { |
14 | 14 |
15 GraphReducer::GraphReducer(Graph* graph) | 15 GraphReducer::GraphReducer(Graph* graph) |
16 : graph_(graph), reducers_(graph->zone()) {} | 16 : graph_(graph), reducers_(graph->zone()) {} |
17 | 17 |
18 | 18 |
19 static bool NodeIdIsLessThan(const Node* node, NodeId id) { | 19 static bool NodeIdIsLessThan(const Node* node, NodeId id) { |
20 return node->id() < id; | 20 return node->id() < id; |
21 } | 21 } |
22 | 22 |
23 | 23 |
24 void GraphReducer::ReduceNode(Node* node) { | 24 void GraphReducer::ReduceNode(Node* node) { |
25 ZoneVector<Reducer*>::iterator skip = reducers_.end(); | |
26 static const unsigned kMaxAttempts = 16; | 25 static const unsigned kMaxAttempts = 16; |
27 bool reduce = true; | 26 bool reduce = true; |
28 for (unsigned attempts = 0; attempts <= kMaxAttempts; ++attempts) { | 27 for (unsigned attempts = 0; attempts <= kMaxAttempts; ++attempts) { |
29 if (!reduce) return; | 28 if (!reduce) return; |
30 reduce = false; // Assume we don't need to rerun any reducers. | 29 reduce = false; // Assume we don't need to rerun any reducers. |
31 int before = graph_->NodeCount(); | 30 int before = graph_->NodeCount(); |
32 for (ZoneVector<Reducer*>::iterator i = reducers_.begin(); | 31 for (ZoneVector<Reducer*>::iterator i = reducers_.begin(); |
33 i != reducers_.end(); ++i) { | 32 i != reducers_.end(); ++i) { |
34 if (i == skip) continue; // Skip this reducer. | |
35 Reduction reduction = (*i)->Reduce(node); | 33 Reduction reduction = (*i)->Reduce(node); |
36 Node* replacement = reduction.replacement(); | 34 Node* replacement = reduction.replacement(); |
37 if (replacement == NULL) { | 35 if (replacement == NULL) { |
38 // No change from this reducer. | 36 // No change from this reducer. |
39 } else if (replacement == node) { | 37 } else if (replacement == node) { |
40 // {replacement == node} represents an in-place reduction. | 38 // {replacement == node} represents an in-place reduction. |
41 // Rerun all the reducers except the current one for this node, | 39 // Rerun all the reducers for this node, as now there may be more |
42 // as now there may be more opportunities for reduction. | 40 // opportunities for reduction. |
43 reduce = true; | 41 reduce = true; |
44 skip = i; | |
45 break; | 42 break; |
46 } else { | 43 } else { |
47 if (node == graph_->start()) graph_->SetStart(replacement); | 44 if (node == graph_->start()) graph_->SetStart(replacement); |
48 if (node == graph_->end()) graph_->SetEnd(replacement); | 45 if (node == graph_->end()) graph_->SetEnd(replacement); |
49 // If {node} was replaced by an old node, unlink {node} and assume that | 46 // If {node} was replaced by an old node, unlink {node} and assume that |
50 // {replacement} was already reduced and finish. | 47 // {replacement} was already reduced and finish. |
51 if (replacement->id() < before) { | 48 if (replacement->id() < before) { |
52 node->ReplaceUses(replacement); | 49 node->ReplaceUses(replacement); |
53 node->Kill(); | 50 node->Kill(); |
54 return; | 51 return; |
55 } | 52 } |
56 // Otherwise, {node} was replaced by a new node. Replace all old uses of | 53 // Otherwise, {node} was replaced by a new node. Replace all old uses of |
57 // {node} with {replacement}. New nodes created by this reduction can | 54 // {node} with {replacement}. New nodes created by this reduction can |
58 // use {node}. | 55 // use {node}. |
59 node->ReplaceUsesIf( | 56 node->ReplaceUsesIf( |
60 std::bind2nd(std::ptr_fun(&NodeIdIsLessThan), before), replacement); | 57 std::bind2nd(std::ptr_fun(&NodeIdIsLessThan), before), replacement); |
61 // Unlink {node} if it's no longer used. | 58 // Unlink {node} if it's no longer used. |
62 if (node->uses().empty()) { | 59 if (node->uses().empty()) { |
63 node->Kill(); | 60 node->Kill(); |
64 } | 61 } |
65 // Rerun all the reductions on the {replacement}. | 62 // Rerun all the reductions on the {replacement}. |
66 skip = reducers_.end(); | |
67 node = replacement; | 63 node = replacement; |
68 reduce = true; | 64 reduce = true; |
69 break; | 65 break; |
70 } | 66 } |
71 } | 67 } |
72 } | 68 } |
73 } | 69 } |
74 | 70 |
75 | 71 |
76 // A helper class to reuse the node traversal algorithm. | 72 // A helper class to reuse the node traversal algorithm. |
(...skipping 12 matching lines...) Expand all Loading... |
89 // Perform a post-order reduction of all nodes starting from the end. | 85 // Perform a post-order reduction of all nodes starting from the end. |
90 graph()->VisitNodeInputsFromEnd(&visitor); | 86 graph()->VisitNodeInputsFromEnd(&visitor); |
91 } | 87 } |
92 | 88 |
93 | 89 |
94 // TODO(titzer): partial graph reductions. | 90 // TODO(titzer): partial graph reductions. |
95 | 91 |
96 } // namespace compiler | 92 } // namespace compiler |
97 } // namespace internal | 93 } // namespace internal |
98 } // namespace v8 | 94 } // namespace v8 |
OLD | NEW |