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