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 #include <vector> |
9 | 10 |
| 11 #include "src/compiler/graph.h" |
| 12 #include "src/compiler/node.h" |
10 #include "src/zone-containers.h" | 13 #include "src/zone-containers.h" |
11 | 14 |
12 namespace v8 { | 15 namespace v8 { |
13 namespace internal { | 16 namespace internal { |
14 namespace compiler { | 17 namespace compiler { |
15 | 18 |
16 class Graph; | 19 class Graph; |
17 class Node; | 20 class Node; |
18 | 21 |
19 // GenericGraphVisit allows visitation of graphs of nodes and edges in pre- and | 22 // GenericGraphVisit allows visitation of graphs of nodes and edges in pre- and |
20 // post-order. Visitation uses an explicitly allocated stack rather than the | 23 // post-order. Visitation uses an explicitly allocated stack rather than the |
21 // execution stack to avoid stack overflow. Although GenericGraphVisit is | 24 // execution stack to avoid stack overflow. |
22 // primarily intended to traverse networks of nodes through their | |
23 // dependencies and uses, it also can be used to visit any graph-like network | |
24 // by specifying custom traits. | |
25 class GenericGraphVisit { | 25 class GenericGraphVisit { |
26 public: | 26 public: |
27 // struct Visitor { | 27 // struct Visitor { |
28 // void Pre(Traits::Node* current); | 28 // void Pre(Node* current); |
29 // void Post(Traits::Node* current); | 29 // void Post(Node* current); |
30 // void PreEdge(Traits::Node* from, int index, Traits::Node* to); | 30 // void PreEdge(Node* from, int index, Node* to); |
31 // void PostEdge(Traits::Node* from, int index, Traits::Node* to); | 31 // void PostEdge(Node* from, int index, Node* to); |
32 // } | 32 // } |
33 template <class Visitor, class Traits, class RootIterator> | 33 template <class Visitor> |
34 static void Visit(Graph* graph, Zone* zone, RootIterator root_begin, | 34 static void Visit(Graph* graph, Zone* zone, Node** root_begin, |
35 RootIterator root_end, Visitor* visitor) { | 35 Node** root_end, Visitor* visitor) { |
36 typedef typename Traits::Node Node; | 36 typedef typename Node::InputEdges::iterator Iterator; |
37 typedef typename Traits::Iterator Iterator; | |
38 typedef std::pair<Iterator, Iterator> NodeState; | 37 typedef std::pair<Iterator, Iterator> NodeState; |
39 typedef std::stack<NodeState, ZoneDeque<NodeState> > NodeStateStack; | 38 typedef std::stack<NodeState, ZoneDeque<NodeState> > NodeStateStack; |
40 NodeStateStack stack((ZoneDeque<NodeState>(zone))); | 39 NodeStateStack stack((ZoneDeque<NodeState>(zone))); |
41 BoolVector visited(Traits::max_id(graph), false, zone); | 40 BoolVector visited(graph->NodeCount(), false, zone); |
42 Node* current = *root_begin; | 41 Node* current = *root_begin; |
43 while (true) { | 42 while (true) { |
44 DCHECK(current != NULL); | 43 DCHECK(current != NULL); |
45 const int id = current->id(); | 44 const int id = current->id(); |
46 DCHECK(id >= 0); | 45 DCHECK(id >= 0); |
47 DCHECK(id < Traits::max_id(graph)); // Must be a valid id. | 46 DCHECK(id < graph->NodeCount()); // Must be a valid id. |
48 bool visit = !GetVisited(&visited, id); | 47 bool visit = !GetVisited(&visited, id); |
49 if (visit) { | 48 if (visit) { |
50 visitor->Pre(current); | 49 visitor->Pre(current); |
51 SetVisited(&visited, id); | 50 SetVisited(&visited, id); |
52 } | 51 } |
53 Iterator begin(visit ? Traits::begin(current) : Traits::end(current)); | 52 Iterator begin(visit ? current->input_edges().begin() |
54 Iterator end(Traits::end(current)); | 53 : current->input_edges().end()); |
| 54 Iterator end(current->input_edges().end()); |
55 stack.push(NodeState(begin, end)); | 55 stack.push(NodeState(begin, end)); |
56 Node* post_order_node = current; | 56 Node* post_order_node = current; |
57 while (true) { | 57 while (true) { |
58 NodeState top = stack.top(); | 58 NodeState top = stack.top(); |
59 if (top.first == top.second) { | 59 if (top.first == top.second) { |
60 if (visit) { | 60 if (visit) { |
61 visitor->Post(post_order_node); | 61 visitor->Post(post_order_node); |
62 SetVisited(&visited, post_order_node->id()); | 62 SetVisited(&visited, post_order_node->id()); |
63 } | 63 } |
64 stack.pop(); | 64 stack.pop(); |
65 if (stack.empty()) { | 65 if (stack.empty()) { |
66 if (++root_begin == root_end) return; | 66 if (++root_begin == root_end) return; |
67 current = *root_begin; | 67 current = *root_begin; |
68 break; | 68 break; |
69 } | 69 } |
70 post_order_node = Traits::from(stack.top().first); | 70 post_order_node = (*stack.top().first).from(); |
71 visit = true; | 71 visit = true; |
72 } else { | 72 } else { |
73 visitor->PreEdge(Traits::from(top.first), (*top.first).index(), | 73 visitor->PreEdge((*top.first).from(), (*top.first).index(), |
74 Traits::to(top.first)); | 74 (*top.first).to()); |
75 current = Traits::to(top.first); | 75 current = (*top.first).to(); |
76 if (!GetVisited(&visited, current->id())) break; | 76 if (!GetVisited(&visited, current->id())) break; |
77 } | 77 } |
78 top = stack.top(); | 78 top = stack.top(); |
79 visitor->PostEdge(Traits::from(top.first), (*top.first).index(), | 79 visitor->PostEdge((*top.first).from(), (*top.first).index(), |
80 Traits::to(top.first)); | 80 (*top.first).to()); |
81 ++stack.top().first; | 81 ++stack.top().first; |
82 } | 82 } |
83 } | 83 } |
84 } | 84 } |
85 | 85 |
86 template <class Visitor, class Traits> | 86 template <class Visitor> |
87 static void Visit(Graph* graph, Zone* zone, typename Traits::Node* current, | 87 static void Visit(Graph* graph, Zone* zone, Node* current, Visitor* visitor) { |
88 Visitor* visitor) { | 88 Node* array[] = {current}; |
89 typename Traits::Node* array[] = {current}; | 89 Visit<Visitor>(graph, zone, &array[0], &array[1], visitor); |
90 Visit<Visitor, Traits>(graph, zone, &array[0], &array[1], visitor); | |
91 } | 90 } |
92 | 91 |
93 struct NullNodeVisitor { | 92 struct NullNodeVisitor { |
94 void Pre(Node* node) {} | 93 void Pre(Node* node) {} |
95 void Post(Node* node) {} | 94 void Post(Node* node) {} |
96 void PreEdge(Node* from, int index, Node* to) {} | 95 void PreEdge(Node* from, int index, Node* to) {} |
97 void PostEdge(Node* from, int index, Node* to) {} | 96 void PostEdge(Node* from, int index, Node* to) {} |
98 }; | 97 }; |
99 | 98 |
100 private: | 99 private: |
101 static void SetVisited(BoolVector* visited, int id) { | 100 static void SetVisited(BoolVector* visited, int id) { |
102 if (id >= static_cast<int>(visited->size())) { | 101 if (id >= static_cast<int>(visited->size())) { |
103 // Resize and set all values to unvisited. | 102 // Resize and set all values to unvisited. |
104 visited->resize((3 * id) / 2, false); | 103 visited->resize((3 * id) / 2, false); |
105 } | 104 } |
106 visited->at(id) = true; | 105 visited->at(id) = true; |
107 } | 106 } |
108 | 107 |
109 static bool GetVisited(BoolVector* visited, int id) { | 108 static bool GetVisited(BoolVector* visited, int id) { |
110 if (id >= static_cast<int>(visited->size())) return false; | 109 if (id >= static_cast<int>(visited->size())) return false; |
111 return visited->at(id); | 110 return visited->at(id); |
112 } | 111 } |
113 }; | 112 }; |
114 } | 113 |
115 } | 114 typedef GenericGraphVisit::NullNodeVisitor NullNodeVisitor; |
116 } // namespace v8::internal::compiler | 115 |
| 116 } // namespace compiler |
| 117 } // namespace internal |
| 118 } // namespace v8 |
117 | 119 |
118 #endif // V8_COMPILER_GENERIC_ALGORITHM_H_ | 120 #endif // V8_COMPILER_GENERIC_ALGORITHM_H_ |
OLD | NEW |