| OLD | NEW |
| 1 // Copyright 2013 the V8 project authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 | 4 |
| 5 #ifndef V8_COMPILER_GENERIC_ALGORITHM_H_ | 5 #ifndef V8_COMPILER_GENERIC_ALGORITHM_H_ |
| 6 #define V8_COMPILER_GENERIC_ALGORITHM_H_ | 6 #define V8_COMPILER_GENERIC_ALGORITHM_H_ |
| 7 | 7 |
| 8 #include <deque> | 8 #include <deque> |
| 9 #include <stack> | 9 #include <stack> |
| 10 | 10 |
| (...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 45 typedef typename Traits::Node Node; | 45 typedef typename Traits::Node Node; |
| 46 typedef typename Traits::Iterator Iterator; | 46 typedef typename Traits::Iterator Iterator; |
| 47 typedef std::pair<Iterator, Iterator> NodeState; | 47 typedef std::pair<Iterator, Iterator> NodeState; |
| 48 typedef zone_allocator<NodeState> ZoneNodeStateAllocator; | 48 typedef zone_allocator<NodeState> ZoneNodeStateAllocator; |
| 49 typedef std::deque<NodeState, ZoneNodeStateAllocator> NodeStateDeque; | 49 typedef std::deque<NodeState, ZoneNodeStateAllocator> NodeStateDeque; |
| 50 typedef std::stack<NodeState, NodeStateDeque> NodeStateStack; | 50 typedef std::stack<NodeState, NodeStateDeque> NodeStateStack; |
| 51 NodeStateStack stack((NodeStateDeque(ZoneNodeStateAllocator(zone)))); | 51 NodeStateStack stack((NodeStateDeque(ZoneNodeStateAllocator(zone)))); |
| 52 BoolVector visited(Traits::max_id(graph), false, ZoneBoolAllocator(zone)); | 52 BoolVector visited(Traits::max_id(graph), false, ZoneBoolAllocator(zone)); |
| 53 Node* current = *root_begin; | 53 Node* current = *root_begin; |
| 54 while (true) { | 54 while (true) { |
| 55 ASSERT(current != NULL); | 55 DCHECK(current != NULL); |
| 56 const int id = current->id(); | 56 const int id = current->id(); |
| 57 ASSERT(id >= 0); | 57 DCHECK(id >= 0); |
| 58 ASSERT(id < Traits::max_id(graph)); // Must be a valid id. | 58 DCHECK(id < Traits::max_id(graph)); // Must be a valid id. |
| 59 bool visit = !GetVisited(&visited, id); | 59 bool visit = !GetVisited(&visited, id); |
| 60 if (visit) { | 60 if (visit) { |
| 61 Control control = visitor->Pre(current); | 61 Control control = visitor->Pre(current); |
| 62 visit = !IsSkip(control); | 62 visit = !IsSkip(control); |
| 63 if (!IsReenter(control)) SetVisited(&visited, id, true); | 63 if (!IsReenter(control)) SetVisited(&visited, id, true); |
| 64 } | 64 } |
| 65 Iterator begin(visit ? Traits::begin(current) : Traits::end(current)); | 65 Iterator begin(visit ? Traits::begin(current) : Traits::end(current)); |
| 66 Iterator end(Traits::end(current)); | 66 Iterator end(Traits::end(current)); |
| 67 stack.push(NodeState(begin, end)); | 67 stack.push(NodeState(begin, end)); |
| 68 Node* post_order_node = current; | 68 Node* post_order_node = current; |
| 69 while (true) { | 69 while (true) { |
| 70 NodeState top = stack.top(); | 70 NodeState top = stack.top(); |
| 71 if (top.first == top.second) { | 71 if (top.first == top.second) { |
| 72 if (visit) { | 72 if (visit) { |
| 73 Control control = visitor->Post(post_order_node); | 73 Control control = visitor->Post(post_order_node); |
| 74 ASSERT(!IsSkip(control)); | 74 DCHECK(!IsSkip(control)); |
| 75 SetVisited(&visited, post_order_node->id(), !IsReenter(control)); | 75 SetVisited(&visited, post_order_node->id(), !IsReenter(control)); |
| 76 } | 76 } |
| 77 stack.pop(); | 77 stack.pop(); |
| 78 if (stack.empty()) { | 78 if (stack.empty()) { |
| 79 if (++root_begin == root_end) return; | 79 if (++root_begin == root_end) return; |
| 80 current = *root_begin; | 80 current = *root_begin; |
| 81 break; | 81 break; |
| 82 } | 82 } |
| 83 post_order_node = Traits::from(stack.top().first); | 83 post_order_node = Traits::from(stack.top().first); |
| 84 visit = true; | 84 visit = true; |
| (...skipping 42 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 127 static bool GetVisited(BoolVector* visited, int id) { | 127 static bool GetVisited(BoolVector* visited, int id) { |
| 128 if (id >= static_cast<int>(visited->size())) return false; | 128 if (id >= static_cast<int>(visited->size())) return false; |
| 129 return visited->at(id); | 129 return visited->at(id); |
| 130 } | 130 } |
| 131 }; | 131 }; |
| 132 } | 132 } |
| 133 } | 133 } |
| 134 } // namespace v8::internal::compiler | 134 } // namespace v8::internal::compiler |
| 135 | 135 |
| 136 #endif // V8_COMPILER_GENERIC_ALGORITHM_H_ | 136 #endif // V8_COMPILER_GENERIC_ALGORITHM_H_ |
| OLD | NEW |