17d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org// Copyright 2013 the V8 project authors. All rights reserved. 27d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org// Use of this source code is governed by a BSD-style license that can be 37d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org// found in the LICENSE file. 47d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 57d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#ifndef V8_COMPILER_GENERIC_ALGORITHM_H_ 67d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#define V8_COMPILER_GENERIC_ALGORITHM_H_ 77d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 87d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#include <stack> 97d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 107d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#include "src/compiler/generic-graph.h" 117d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#include "src/compiler/generic-node.h" 127d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#include "src/zone-containers.h" 137d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 147d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgnamespace v8 { 157d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgnamespace internal { 167d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgnamespace compiler { 177d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 187d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org// GenericGraphVisit allows visitation of graphs of nodes and edges in pre- and 197d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org// post-order. Visitation uses an explicitly allocated stack rather than the 207d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org// execution stack to avoid stack overflow. Although GenericGraphVisit is 217d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org// primarily intended to traverse networks of nodes through their 227d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org// dependencies and uses, it also can be used to visit any graph-like network 237d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org// by specifying custom traits. 247d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgclass GenericGraphVisit { 257d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org public: 267d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org enum Control { 277d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org CONTINUE = 0x0, // Continue depth-first normally 287d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org SKIP = 0x1, // Skip this node and its successors 297d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org REENTER = 0x2, // Allow reentering this node 307d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org DEFER = SKIP | REENTER 317d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org }; 327d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 337d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // struct Visitor { 347d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Control Pre(Traits::Node* current); 357d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Control Post(Traits::Node* current); 367d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // void PreEdge(Traits::Node* from, int index, Traits::Node* to); 377d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // void PostEdge(Traits::Node* from, int index, Traits::Node* to); 387d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // } 397d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org template <class Visitor, class Traits, class RootIterator> 405e57059e20217fd540b60c237d326414afe2171emachenbach@chromium.org static void Visit(GenericGraphBase* graph, Zone* zone, 415e57059e20217fd540b60c237d326414afe2171emachenbach@chromium.org RootIterator root_begin, RootIterator root_end, 425e57059e20217fd540b60c237d326414afe2171emachenbach@chromium.org Visitor* visitor) { 437d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org typedef typename Traits::Node Node; 447d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org typedef typename Traits::Iterator Iterator; 457d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org typedef std::pair<Iterator, Iterator> NodeState; 46946ae75ed85d2c5839a2d6630c4b443f0264e6e0machenbach@chromium.org typedef std::stack<NodeState, ZoneDeque<NodeState> > NodeStateStack; 47fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org NodeStateStack stack((ZoneDeque<NodeState>(zone))); 48fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org BoolVector visited(Traits::max_id(graph), false, zone); 497d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org Node* current = *root_begin; 507d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org while (true) { 51e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(current != NULL); 527d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org const int id = current->id(); 53e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(id >= 0); 54e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(id < Traits::max_id(graph)); // Must be a valid id. 557d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org bool visit = !GetVisited(&visited, id); 567d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (visit) { 577d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org Control control = visitor->Pre(current); 587d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org visit = !IsSkip(control); 597d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (!IsReenter(control)) SetVisited(&visited, id, true); 607d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 617d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org Iterator begin(visit ? Traits::begin(current) : Traits::end(current)); 627d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org Iterator end(Traits::end(current)); 637d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org stack.push(NodeState(begin, end)); 647d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org Node* post_order_node = current; 657d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org while (true) { 667d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org NodeState top = stack.top(); 677d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (top.first == top.second) { 687d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (visit) { 697d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org Control control = visitor->Post(post_order_node); 70e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(!IsSkip(control)); 717d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org SetVisited(&visited, post_order_node->id(), !IsReenter(control)); 727d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 737d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org stack.pop(); 747d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (stack.empty()) { 757d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (++root_begin == root_end) return; 767d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org current = *root_begin; 777d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org break; 787d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 797d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org post_order_node = Traits::from(stack.top().first); 807d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org visit = true; 817d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } else { 827d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org visitor->PreEdge(Traits::from(top.first), top.first.edge().index(), 837d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org Traits::to(top.first)); 847d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org current = Traits::to(top.first); 857d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (!GetVisited(&visited, current->id())) break; 867d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 877d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org top = stack.top(); 887d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org visitor->PostEdge(Traits::from(top.first), top.first.edge().index(), 897d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org Traits::to(top.first)); 907d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org ++stack.top().first; 917d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 927d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 937d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 947d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 957d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org template <class Visitor, class Traits> 965e57059e20217fd540b60c237d326414afe2171emachenbach@chromium.org static void Visit(GenericGraphBase* graph, Zone* zone, 975e57059e20217fd540b60c237d326414afe2171emachenbach@chromium.org typename Traits::Node* current, Visitor* visitor) { 987d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org typename Traits::Node* array[] = {current}; 995e57059e20217fd540b60c237d326414afe2171emachenbach@chromium.org Visit<Visitor, Traits>(graph, zone, &array[0], &array[1], visitor); 1007d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 1017d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 1027d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org template <class B, class S> 1037d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org struct NullNodeVisitor { 1047d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org Control Pre(GenericNode<B, S>* node) { return CONTINUE; } 1057d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org Control Post(GenericNode<B, S>* node) { return CONTINUE; } 1067d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org void PreEdge(GenericNode<B, S>* from, int index, GenericNode<B, S>* to) {} 1077d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org void PostEdge(GenericNode<B, S>* from, int index, GenericNode<B, S>* to) {} 1087d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org }; 1097d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 1107d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org private: 1117d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org static bool IsSkip(Control c) { return c & SKIP; } 1127d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org static bool IsReenter(Control c) { return c & REENTER; } 1137d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 1147d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // TODO(turbofan): resizing could be optionally templatized away. 1157d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org static void SetVisited(BoolVector* visited, int id, bool value) { 1167d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (id >= static_cast<int>(visited->size())) { 1177d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Resize and set all values to unvisited. 1187d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org visited->resize((3 * id) / 2, false); 1197d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 1207d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org visited->at(id) = value; 1217d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 1227d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 1237d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org static bool GetVisited(BoolVector* visited, int id) { 1247d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (id >= static_cast<int>(visited->size())) return false; 1257d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org return visited->at(id); 1267d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 1277d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org}; 1287d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org} 1297d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org} 1307d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org} // namespace v8::internal::compiler 1317d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 1327d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#endif // V8_COMPILER_GENERIC_ALGORITHM_H_ 133