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
3 // found in the LICENSE file.
5 #ifndef V8_COMPILER_GENERIC_ALGORITHM_H_
6 #define V8_COMPILER_GENERIC_ALGORITHM_H_
11 #include "src/compiler/graph.h"
12 #include "src/compiler/node.h"
13 #include "src/zone-containers.h"
22 // GenericGraphVisit allows visitation of graphs of nodes and edges in pre- and
23 // post-order. Visitation uses an explicitly allocated stack rather than the
24 // execution stack to avoid stack overflow.
25 class GenericGraphVisit {
28 // void Pre(Node* current);
29 // void Post(Node* current);
30 // void PreEdge(Node* from, int index, Node* to);
31 // void PostEdge(Node* from, int index, Node* to);
33 template <class Visitor>
34 static void Visit(Graph* graph, Zone* zone, Node** root_begin,
35 Node** root_end, Visitor* visitor) {
36 typedef typename Node::InputEdges::iterator Iterator;
37 typedef std::pair<Iterator, Iterator> NodeState;
38 typedef std::stack<NodeState, ZoneDeque<NodeState> > NodeStateStack;
39 NodeStateStack stack((ZoneDeque<NodeState>(zone)));
40 BoolVector visited(graph->NodeCount(), false, zone);
41 Node* current = *root_begin;
43 DCHECK(current != NULL);
44 const int id = current->id();
46 DCHECK(id < graph->NodeCount()); // Must be a valid id.
47 bool visit = !GetVisited(&visited, id);
49 visitor->Pre(current);
50 SetVisited(&visited, id);
52 Iterator begin(visit ? current->input_edges().begin()
53 : current->input_edges().end());
54 Iterator end(current->input_edges().end());
55 stack.push(NodeState(begin, end));
56 Node* post_order_node = current;
58 NodeState top = stack.top();
59 if (top.first == top.second) {
61 visitor->Post(post_order_node);
62 SetVisited(&visited, post_order_node->id());
66 if (++root_begin == root_end) return;
67 current = *root_begin;
70 post_order_node = (*stack.top().first).from();
73 visitor->PreEdge((*top.first).from(), (*top.first).index(),
75 current = (*top.first).to();
76 if (!GetVisited(&visited, current->id())) break;
79 visitor->PostEdge((*top.first).from(), (*top.first).index(),
86 template <class Visitor>
87 static void Visit(Graph* graph, Zone* zone, Node* current, Visitor* visitor) {
88 Node* array[] = {current};
89 Visit<Visitor>(graph, zone, &array[0], &array[1], visitor);
92 struct NullNodeVisitor {
93 void Pre(Node* node) {}
94 void Post(Node* node) {}
95 void PreEdge(Node* from, int index, Node* to) {}
96 void PostEdge(Node* from, int index, Node* to) {}
100 static void SetVisited(BoolVector* visited, int id) {
101 if (id >= static_cast<int>(visited->size())) {
102 // Resize and set all values to unvisited.
103 visited->resize((3 * id) / 2, false);
105 visited->at(id) = true;
108 static bool GetVisited(BoolVector* visited, int id) {
109 if (id >= static_cast<int>(visited->size())) return false;
110 return visited->at(id);
114 typedef GenericGraphVisit::NullNodeVisitor NullNodeVisitor;
116 } // namespace compiler
117 } // namespace internal
120 #endif // V8_COMPILER_GENERIC_ALGORITHM_H_