| OLD | NEW |
| 1 // Copyright 2013 the V8 project authors. All rights reserved. | 1 // Copyright 2013 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 #ifndef V8_COMPILER_GENERIC_ALGORITHM_H_ | 5 #ifndef V8_COMPILER_GENERIC_ALGORITHM_H_ |
| 6 #define V8_COMPILER_GENERIC_ALGORITHM_H_ | 6 #define V8_COMPILER_GENERIC_ALGORITHM_H_ |
| 7 | 7 |
| 8 #include <stack> | 8 #include <stack> |
| 9 | 9 |
| 10 #include "src/compiler/generic-graph.h" | |
| 11 #include "src/compiler/generic-node.h" | 10 #include "src/compiler/generic-node.h" |
| 12 #include "src/zone-containers.h" | 11 #include "src/zone-containers.h" |
| 13 | 12 |
| 14 namespace v8 { | 13 namespace v8 { |
| 15 namespace internal { | 14 namespace internal { |
| 16 namespace compiler { | 15 namespace compiler { |
| 17 | 16 |
| 18 // GenericGraphVisit allows visitation of graphs of nodes and edges in pre- and | 17 // GenericGraphVisit allows visitation of graphs of nodes and edges in pre- and |
| 19 // post-order. Visitation uses an explicitly allocated stack rather than the | 18 // post-order. Visitation uses an explicitly allocated stack rather than the |
| 20 // execution stack to avoid stack overflow. Although GenericGraphVisit is | 19 // execution stack to avoid stack overflow. Although GenericGraphVisit is |
| 21 // primarily intended to traverse networks of nodes through their | 20 // primarily intended to traverse networks of nodes through their |
| 22 // dependencies and uses, it also can be used to visit any graph-like network | 21 // dependencies and uses, it also can be used to visit any graph-like network |
| 23 // by specifying custom traits. | 22 // by specifying custom traits. |
| 24 class GenericGraphVisit { | 23 class GenericGraphVisit { |
| 25 public: | 24 public: |
| 26 // struct Visitor { | 25 // struct Visitor { |
| 27 // void Pre(Traits::Node* current); | 26 // void Pre(Traits::Node* current); |
| 28 // void Post(Traits::Node* current); | 27 // void Post(Traits::Node* current); |
| 29 // void PreEdge(Traits::Node* from, int index, Traits::Node* to); | 28 // void PreEdge(Traits::Node* from, int index, Traits::Node* to); |
| 30 // void PostEdge(Traits::Node* from, int index, Traits::Node* to); | 29 // void PostEdge(Traits::Node* from, int index, Traits::Node* to); |
| 31 // } | 30 // } |
| 32 template <class Visitor, class Traits, class RootIterator> | 31 template <class Visitor, class Traits, class RootIterator> |
| 33 static void Visit(GenericGraphBase* graph, Zone* zone, | 32 static void Visit(Graph* graph, Zone* zone, RootIterator root_begin, |
| 34 RootIterator root_begin, RootIterator root_end, | 33 RootIterator root_end, Visitor* visitor) { |
| 35 Visitor* visitor) { | |
| 36 typedef typename Traits::Node Node; | 34 typedef typename Traits::Node Node; |
| 37 typedef typename Traits::Iterator Iterator; | 35 typedef typename Traits::Iterator Iterator; |
| 38 typedef std::pair<Iterator, Iterator> NodeState; | 36 typedef std::pair<Iterator, Iterator> NodeState; |
| 39 typedef std::stack<NodeState, ZoneDeque<NodeState> > NodeStateStack; | 37 typedef std::stack<NodeState, ZoneDeque<NodeState> > NodeStateStack; |
| 40 NodeStateStack stack((ZoneDeque<NodeState>(zone))); | 38 NodeStateStack stack((ZoneDeque<NodeState>(zone))); |
| 41 BoolVector visited(Traits::max_id(graph), false, zone); | 39 BoolVector visited(Traits::max_id(graph), false, zone); |
| 42 Node* current = *root_begin; | 40 Node* current = *root_begin; |
| 43 while (true) { | 41 while (true) { |
| 44 DCHECK(current != NULL); | 42 DCHECK(current != NULL); |
| 45 const int id = current->id(); | 43 const int id = current->id(); |
| (...skipping 31 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 77 } | 75 } |
| 78 top = stack.top(); | 76 top = stack.top(); |
| 79 visitor->PostEdge(Traits::from(top.first), top.first.edge().index(), | 77 visitor->PostEdge(Traits::from(top.first), top.first.edge().index(), |
| 80 Traits::to(top.first)); | 78 Traits::to(top.first)); |
| 81 ++stack.top().first; | 79 ++stack.top().first; |
| 82 } | 80 } |
| 83 } | 81 } |
| 84 } | 82 } |
| 85 | 83 |
| 86 template <class Visitor, class Traits> | 84 template <class Visitor, class Traits> |
| 87 static void Visit(GenericGraphBase* graph, Zone* zone, | 85 static void Visit(Graph* graph, Zone* zone, typename Traits::Node* current, |
| 88 typename Traits::Node* current, Visitor* visitor) { | 86 Visitor* visitor) { |
| 89 typename Traits::Node* array[] = {current}; | 87 typename Traits::Node* array[] = {current}; |
| 90 Visit<Visitor, Traits>(graph, zone, &array[0], &array[1], visitor); | 88 Visit<Visitor, Traits>(graph, zone, &array[0], &array[1], visitor); |
| 91 } | 89 } |
| 92 | 90 |
| 93 template <class B, class S> | 91 template <class B, class S> |
| 94 struct NullNodeVisitor { | 92 struct NullNodeVisitor { |
| 95 void Pre(GenericNode<B, S>* node) {} | 93 void Pre(GenericNode<B, S>* node) {} |
| 96 void Post(GenericNode<B, S>* node) {} | 94 void Post(GenericNode<B, S>* node) {} |
| 97 void PreEdge(GenericNode<B, S>* from, int index, GenericNode<B, S>* to) {} | 95 void PreEdge(GenericNode<B, S>* from, int index, GenericNode<B, S>* to) {} |
| 98 void PostEdge(GenericNode<B, S>* from, int index, GenericNode<B, S>* to) {} | 96 void PostEdge(GenericNode<B, S>* from, int index, GenericNode<B, S>* to) {} |
| (...skipping 11 matching lines...) Expand all Loading... |
| 110 static bool GetVisited(BoolVector* visited, int id) { | 108 static bool GetVisited(BoolVector* visited, int id) { |
| 111 if (id >= static_cast<int>(visited->size())) return false; | 109 if (id >= static_cast<int>(visited->size())) return false; |
| 112 return visited->at(id); | 110 return visited->at(id); |
| 113 } | 111 } |
| 114 }; | 112 }; |
| 115 } | 113 } |
| 116 } | 114 } |
| 117 } // namespace v8::internal::compiler | 115 } // namespace v8::internal::compiler |
| 118 | 116 |
| 119 #endif // V8_COMPILER_GENERIC_ALGORITHM_H_ | 117 #endif // V8_COMPILER_GENERIC_ALGORITHM_H_ |
| OLD | NEW |