Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(297)

Side by Side Diff: src/compiler/generic-algorithm.h

Issue 767733002: De-generify the GenericGraph. (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: Rebased again. Created 6 years ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « BUILD.gn ('k') | src/compiler/generic-algorithm-inl.h » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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
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_
OLDNEW
« no previous file with comments | « BUILD.gn ('k') | src/compiler/generic-algorithm-inl.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698