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