Home | History | Annotate | Download | only in compiler 
      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 
     14 namespace v8 {
     15 namespace internal {
     16 namespace 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.
     24 class 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