OLD | NEW |
(Empty) | |
| 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 |
| 15 GraphReducer::GraphReducer(Graph* graph) |
| 16 : graph_(graph), reducers_(Reducers::allocator_type(graph->zone())) {} |
| 17 |
| 18 |
| 19 static bool NodeIdIsLessThan(const Node* node, NodeId id) { |
| 20 return node->id() < id; |
| 21 } |
| 22 |
| 23 |
| 24 void GraphReducer::ReduceNode(Node* node) { |
| 25 Reducers::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 (Reducers::iterator i = reducers_.begin(); i != reducers_.end(); ++i) { |
| 33 if (i == skip) continue; // Skip this reducer. |
| 34 Reduction reduction = (*i)->Reduce(node); |
| 35 Node* replacement = reduction.replacement(); |
| 36 if (replacement == NULL) { |
| 37 // No change from this reducer. |
| 38 } else if (replacement == node) { |
| 39 // {replacement == node} represents an in-place reduction. |
| 40 // Rerun all the reducers except the current one for this node, |
| 41 // as now there may be more opportunities for reduction. |
| 42 reduce = true; |
| 43 skip = i; |
| 44 break; |
| 45 } else { |
| 46 if (node == graph_->start()) graph_->SetStart(replacement); |
| 47 if (node == graph_->end()) graph_->SetEnd(replacement); |
| 48 // If {node} was replaced by an old node, unlink {node} and assume that |
| 49 // {replacement} was already reduced and finish. |
| 50 if (replacement->id() < before) { |
| 51 node->RemoveAllInputs(); |
| 52 node->ReplaceUses(replacement); |
| 53 return; |
| 54 } |
| 55 // Otherwise, {node} was replaced by a new node. Replace all old uses of |
| 56 // {node} with {replacement}. New nodes created by this reduction can |
| 57 // use {node}. |
| 58 node->ReplaceUsesIf( |
| 59 std::bind2nd(std::ptr_fun(&NodeIdIsLessThan), before), replacement); |
| 60 // Unlink {node} if it's no longer used. |
| 61 if (node->uses().empty()) node->RemoveAllInputs(); |
| 62 // Rerun all the reductions on the {replacement}. |
| 63 skip = reducers_.end(); |
| 64 node = replacement; |
| 65 reduce = true; |
| 66 break; |
| 67 } |
| 68 } |
| 69 } |
| 70 } |
| 71 |
| 72 |
| 73 // A helper class to reuse the node traversal algorithm. |
| 74 struct GraphReducerVisitor V8_FINAL : public NullNodeVisitor { |
| 75 explicit GraphReducerVisitor(GraphReducer* reducer) : reducer_(reducer) {} |
| 76 GenericGraphVisit::Control Post(Node* node) { |
| 77 reducer_->ReduceNode(node); |
| 78 return GenericGraphVisit::CONTINUE; |
| 79 } |
| 80 GraphReducer* reducer_; |
| 81 }; |
| 82 |
| 83 |
| 84 void GraphReducer::ReduceGraph() { |
| 85 GraphReducerVisitor visitor(this); |
| 86 // Perform a post-order reduction of all nodes starting from the end. |
| 87 graph()->VisitNodeInputsFromEnd(&visitor); |
| 88 } |
| 89 |
| 90 |
| 91 // TODO(titzer): partial graph reductions. |
| 92 } |
| 93 } |
| 94 } // namespace v8::internal::compiler |
OLD | NEW |