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