OLD | NEW |
(Empty) | |
| 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_ |
OLD | NEW |