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

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

Issue 941963003: Revert of [turbofan] Finally get rid of the generic algorithm. (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: Created 5 years, 10 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 | « BUILD.gn ('k') | src/compiler/graph-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..391757ecb8beefa068b528c57240144879ef8f20
--- /dev/null
+++ b/src/compiler/generic-algorithm.h
@@ -0,0 +1,120 @@
+// 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 <vector>
+
+#include "src/compiler/graph.h"
+#include "src/compiler/node.h"
+#include "src/zone-containers.h"
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+class Graph;
+class Node;
+
+// 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.
+class GenericGraphVisit {
+ public:
+ // struct Visitor {
+ // void Pre(Node* current);
+ // void Post(Node* current);
+ // void PreEdge(Node* from, int index, Node* to);
+ // void PostEdge(Node* from, int index, Node* to);
+ // }
+ template <class Visitor>
+ static void Visit(Graph* graph, Zone* zone, Node** root_begin,
+ Node** root_end, Visitor* visitor) {
+ typedef typename Node::InputEdges::iterator Iterator;
+ typedef std::pair<Iterator, Iterator> NodeState;
+ typedef std::stack<NodeState, ZoneDeque<NodeState> > NodeStateStack;
+ NodeStateStack stack((ZoneDeque<NodeState>(zone)));
+ BoolVector visited(graph->NodeCount(), false, zone);
+ Node* current = *root_begin;
+ while (true) {
+ DCHECK(current != NULL);
+ const int id = current->id();
+ DCHECK(id >= 0);
+ DCHECK(id < graph->NodeCount()); // Must be a valid id.
+ bool visit = !GetVisited(&visited, id);
+ if (visit) {
+ visitor->Pre(current);
+ SetVisited(&visited, id);
+ }
+ Iterator begin(visit ? current->input_edges().begin()
+ : current->input_edges().end());
+ Iterator end(current->input_edges().end());
+ 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 = (*stack.top().first).from();
+ visit = true;
+ } else {
+ visitor->PreEdge((*top.first).from(), (*top.first).index(),
+ (*top.first).to());
+ current = (*top.first).to();
+ if (!GetVisited(&visited, current->id())) break;
+ }
+ top = stack.top();
+ visitor->PostEdge((*top.first).from(), (*top.first).index(),
+ (*top.first).to());
+ ++stack.top().first;
+ }
+ }
+ }
+
+ template <class Visitor>
+ static void Visit(Graph* graph, Zone* zone, Node* current, Visitor* visitor) {
+ Node* array[] = {current};
+ Visit<Visitor>(graph, zone, &array[0], &array[1], visitor);
+ }
+
+ struct NullNodeVisitor {
+ void Pre(Node* node) {}
+ void Post(Node* node) {}
+ void PreEdge(Node* from, int index, Node* to) {}
+ void PostEdge(Node* from, int index, Node* 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);
+ }
+};
+
+typedef GenericGraphVisit::NullNodeVisitor NullNodeVisitor;
+
+} // namespace compiler
+} // namespace internal
+} // namespace v8
+
+#endif // V8_COMPILER_GENERIC_ALGORITHM_H_
« no previous file with comments | « BUILD.gn ('k') | src/compiler/graph-inl.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698