generic-algorithm.h 3.76 KB
Newer Older
1 2 3 4 5 6 7 8
// 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>
9
#include <vector>
10

11 12
#include "src/compiler/graph.h"
#include "src/compiler/node.h"
13 14 15 16 17 18
#include "src/zone-containers.h"

namespace v8 {
namespace internal {
namespace compiler {

19 20 21
class Graph;
class Node;

22 23
// GenericGraphVisit allows visitation of graphs of nodes and edges in pre- and
// post-order. Visitation uses an explicitly allocated stack rather than the
24
// execution stack to avoid stack overflow.
25 26 27
class GenericGraphVisit {
 public:
  // struct Visitor {
28 29 30 31
  //   void Pre(Node* current);
  //   void Post(Node* current);
  //   void PreEdge(Node* from, int index, Node* to);
  //   void PostEdge(Node* from, int index, Node* to);
32
  // }
33 34 35 36
  template <class Visitor>
  static void Visit(Graph* graph, Zone* zone, Node** root_begin,
                    Node** root_end, Visitor* visitor) {
    typedef typename Node::InputEdges::iterator Iterator;
37
    typedef std::pair<Iterator, Iterator> NodeState;
38
    typedef std::stack<NodeState, ZoneDeque<NodeState> > NodeStateStack;
39
    NodeStateStack stack((ZoneDeque<NodeState>(zone)));
40
    BoolVector visited(graph->NodeCount(), false, zone);
41 42
    Node* current = *root_begin;
    while (true) {
43
      DCHECK(current != NULL);
44
      const int id = current->id();
45
      DCHECK(id >= 0);
46
      DCHECK(id < graph->NodeCount());  // Must be a valid id.
47 48
      bool visit = !GetVisited(&visited, id);
      if (visit) {
49 50
        visitor->Pre(current);
        SetVisited(&visited, id);
51
      }
52 53 54
      Iterator begin(visit ? current->input_edges().begin()
                           : current->input_edges().end());
      Iterator end(current->input_edges().end());
55 56 57 58 59 60
      stack.push(NodeState(begin, end));
      Node* post_order_node = current;
      while (true) {
        NodeState top = stack.top();
        if (top.first == top.second) {
          if (visit) {
61 62
            visitor->Post(post_order_node);
            SetVisited(&visited, post_order_node->id());
63 64 65 66 67 68 69
          }
          stack.pop();
          if (stack.empty()) {
            if (++root_begin == root_end) return;
            current = *root_begin;
            break;
          }
70
          post_order_node = (*stack.top().first).from();
71 72
          visit = true;
        } else {
73 74 75
          visitor->PreEdge((*top.first).from(), (*top.first).index(),
                           (*top.first).to());
          current = (*top.first).to();
76 77 78
          if (!GetVisited(&visited, current->id())) break;
        }
        top = stack.top();
79 80
        visitor->PostEdge((*top.first).from(), (*top.first).index(),
                          (*top.first).to());
81 82 83 84 85
        ++stack.top().first;
      }
    }
  }

86 87 88 89
  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);
90 91 92
  }

  struct NullNodeVisitor {
93 94 95 96
    void Pre(Node* node) {}
    void Post(Node* node) {}
    void PreEdge(Node* from, int index, Node* to) {}
    void PostEdge(Node* from, int index, Node* to) {}
97 98 99
  };

 private:
100
  static void SetVisited(BoolVector* visited, int id) {
101 102 103 104
    if (id >= static_cast<int>(visited->size())) {
      // Resize and set all values to unvisited.
      visited->resize((3 * id) / 2, false);
    }
105
    visited->at(id) = true;
106 107 108 109 110 111 112
  }

  static bool GetVisited(BoolVector* visited, int id) {
    if (id >= static_cast<int>(visited->size())) return false;
    return visited->at(id);
  }
};
113 114 115 116 117 118

typedef GenericGraphVisit::NullNodeVisitor NullNodeVisitor;

}  // namespace compiler
}  // namespace internal
}  // namespace v8
119 120

#endif  // V8_COMPILER_GENERIC_ALGORITHM_H_