deps/v8/src/compiler/generic-algorithm.h

   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 #include <vector>
  10
  11 #include "src/compiler/graph.h"
  12 #include "src/compiler/node.h"
  13 #include "src/zone-containers.h"
  14
  15 namespace v8 {
  16 namespace internal {
  17 namespace compiler {
  18
  19 class Graph;
  20 class Node;
  21
  22 // GenericGraphVisit allows visitation of graphs of nodes and edges in pre- and
  23 // post-order. Visitation uses an explicitly allocated stack rather than the
  24 // execution stack to avoid stack overflow.
  25 class GenericGraphVisit {
  26  public:
  27   // struct Visitor {
  28   //   void Pre(Node* current);
  29   //   void Post(Node* current);
  30   //   void PreEdge(Node* from, int index, Node* to);
  31   //   void PostEdge(Node* from, int index, Node* to);
  32   // }
  33   template <class Visitor>
  34   static void Visit(Graph* graph, Zone* zone, Node** root_begin,
  35                     Node** root_end, Visitor* visitor) {
  36     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     Node* current = *root_begin;
  42     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       bool visit = !GetVisited(&visited, id);
  48       if (visit) {
  49         visitor->Pre(current);
  50         SetVisited(&visited, id);
  51       }
  52       Iterator begin(visit ? current->input_edges().begin()
  53                            : current->input_edges().end());
  54       Iterator end(current->input_edges().end());
  55       stack.push(NodeState(begin, end));
  56       Node* post_order_node = current;
  57       while (true) {
  58         NodeState top = stack.top();
  59         if (top.first == top.second) {
  60           if (visit) {
  61             visitor->Post(post_order_node);
  62             SetVisited(&visited, post_order_node->id());
  63           }
  64           stack.pop();
  65           if (stack.empty()) {
  66             if (++root_begin == root_end) return;
  67             current = *root_begin;
  68             break;
  69           }
  70           post_order_node = (*stack.top().first).from();
  71           visit = true;
  72         } else {
  73           visitor->PreEdge((*top.first).from(), (*top.first).index(),
  74                            (*top.first).to());
  75           current = (*top.first).to();
  76           if (!GetVisited(&visited, current->id())) break;
  77         }
  78         top = stack.top();
  79         visitor->PostEdge((*top.first).from(), (*top.first).index(),
  80                           (*top.first).to());
  81         ++stack.top().first;
  82       }
  83     }
  84   }
  85
  86   template <class Visitor>
  87   static void Visit(Graph* graph, Zone* zone, Node* current, Visitor* visitor) {
  88     Node* array[] = {current};
  89     Visit<Visitor>(graph, zone, &array[0], &array[1], visitor);
  90   }
  91
  92   struct NullNodeVisitor {
  93     void Pre(Node* node) {}
  94     void Post(Node* node) {}
  95     void PreEdge(Node* from, int index, Node* to) {}
  96     void PostEdge(Node* from, int index, Node* to) {}
  97   };
  98
  99  private:
 100   static void SetVisited(BoolVector* visited, int id) {
 101     if (id >= static_cast<int>(visited->size())) {
 102       // Resize and set all values to unvisited.
 103       visited->resize((3 * id) / 2, false);
 104     }
 105     visited->at(id) = true;
 106   }
 107
 108   static bool GetVisited(BoolVector* visited, int id) {
 109     if (id >= static_cast<int>(visited->size())) return false;
 110     return visited->at(id);
 111   }
 112 };
 113
 114 typedef GenericGraphVisit::NullNodeVisitor NullNodeVisitor;
 115
 116 }  // namespace compiler
 117 }  // namespace internal
 118 }  // namespace v8
 119
 120 #endif  // V8_COMPILER_GENERIC_ALGORITHM_H_