Land the Fan (disabled)

src/compiler/generic-algorithm.h

+// 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_