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

Unified Diff: src/compiler/generic-algorithm.h

Issue 426233002: Land the Fan (disabled) (Closed) Base URL: https://v8.googlecode.com/svn/branches/bleeding_edge
Patch Set: Review feedback, rebase and "git cl format" Created 6 years, 5 months 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 side-by-side diff with in-line comments
Download patch
« no previous file with comments | « src/compiler/gap-resolver.cc ('k') | src/compiler/generic-algorithm-inl.h » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/compiler/generic-algorithm.h
diff --git a/src/compiler/generic-algorithm.h b/src/compiler/generic-algorithm.h
new file mode 100644
index 0000000000000000000000000000000000000000..f7bb2fe9e729dc00514bd486c26b9d894c102fda
--- /dev/null
+++ b/src/compiler/generic-algorithm.h
@@ -0,0 +1,136 @@
+// 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 <deque>
+#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:
+ enum Control {
+ CONTINUE = 0x0, // Continue depth-first normally
+ SKIP = 0x1, // Skip this node and its successors
+ REENTER = 0x2, // Allow reentering this node
+ DEFER = SKIP | REENTER
+ };
+
+ // struct Visitor {
+ // Control Pre(Traits::Node* current);
+ // Control 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, RootIterator root_begin,
+ RootIterator root_end, Visitor* visitor) {
+ // TODO(bmeurer): Pass "local" zone as parameter.
+ Zone* zone = graph->zone();
+ typedef typename Traits::Node Node;
+ typedef typename Traits::Iterator Iterator;
+ typedef std::pair<Iterator, Iterator> NodeState;
+ typedef zone_allocator<NodeState> ZoneNodeStateAllocator;
+ typedef std::deque<NodeState, ZoneNodeStateAllocator> NodeStateDeque;
+ typedef std::stack<NodeState, NodeStateDeque> NodeStateStack;
+ NodeStateStack stack((NodeStateDeque(ZoneNodeStateAllocator(zone))));
+ BoolVector visited(Traits::max_id(graph), false, ZoneBoolAllocator(zone));
+ Node* current = *root_begin;
+ while (true) {
+ ASSERT(current != NULL);
+ const int id = current->id();
+ ASSERT(id >= 0);
+ ASSERT(id < Traits::max_id(graph)); // Must be a valid id.
+ bool visit = !GetVisited(&visited, id);
+ if (visit) {
+ Control control = visitor->Pre(current);
+ visit = !IsSkip(control);
+ if (!IsReenter(control)) SetVisited(&visited, id, true);
+ }
+ 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) {
+ Control control = visitor->Post(post_order_node);
+ ASSERT(!IsSkip(control));
+ SetVisited(&visited, post_order_node->id(), !IsReenter(control));
+ }
+ 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, typename Traits::Node* current,
+ Visitor* visitor) {
+ typename Traits::Node* array[] = {current};
+ Visit<Visitor, Traits>(graph, &array[0], &array[1], visitor);
+ }
+
+ template <class B, class S>
+ struct NullNodeVisitor {
+ Control Pre(GenericNode<B, S>* node) { return CONTINUE; }
+ Control Post(GenericNode<B, S>* node) { return CONTINUE; }
+ 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 bool IsSkip(Control c) { return c & SKIP; }
+ static bool IsReenter(Control c) { return c & REENTER; }
+
+ // TODO(turbofan): resizing could be optionally templatized away.
+ static void SetVisited(BoolVector* visited, int id, bool value) {
+ if (id >= static_cast<int>(visited->size())) {
+ // Resize and set all values to unvisited.
+ visited->resize((3 * id) / 2, false);
+ }
+ visited->at(id) = value;
+ }
+
+ 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_
« no previous file with comments | « src/compiler/gap-resolver.cc ('k') | src/compiler/generic-algorithm-inl.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698