Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 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_GRAPH_H_ |
| 6 | #define V8_COMPILER_GRAPH_H_ |
| 7 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 8 | #include "src/zone.h" |
| 9 | #include "src/zone-containers.h" |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 10 | |
| 11 | namespace v8 { |
| 12 | namespace internal { |
| 13 | namespace compiler { |
| 14 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 15 | // Forward declarations. |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 16 | class GraphDecorator; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 17 | class Node; |
| 18 | class Operator; |
| 19 | |
| 20 | |
| 21 | // Marks are used during traversal of the graph to distinguish states of nodes. |
| 22 | // Each node has a mark which is a monotonically increasing integer, and a |
| 23 | // {NodeMarker} has a range of values that indicate states of a node. |
| 24 | typedef uint32_t Mark; |
| 25 | |
| 26 | |
| 27 | // NodeIds are identifying numbers for nodes that can be used to index auxiliary |
| 28 | // out-of-line data associated with each node. |
| 29 | typedef uint32_t NodeId; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 30 | |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 31 | class Graph final : public ZoneObject { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 32 | public: |
| 33 | explicit Graph(Zone* zone); |
| 34 | |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 35 | // Scope used when creating a subgraph for inlining. Automatically preserves |
| 36 | // the original start and end nodes of the graph, and resets them when you |
| 37 | // leave the scope. |
| 38 | class SubgraphScope final { |
| 39 | public: |
| 40 | explicit SubgraphScope(Graph* graph) |
| 41 | : graph_(graph), start_(graph->start()), end_(graph->end()) {} |
| 42 | ~SubgraphScope() { |
| 43 | graph_->SetStart(start_); |
| 44 | graph_->SetEnd(end_); |
| 45 | } |
| 46 | |
| 47 | private: |
| 48 | Graph* const graph_; |
| 49 | Node* const start_; |
| 50 | Node* const end_; |
| 51 | |
| 52 | DISALLOW_COPY_AND_ASSIGN(SubgraphScope); |
| 53 | }; |
| 54 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 55 | // Base implementation used by all factory methods. |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 56 | Node* NewNodeUnchecked(const Operator* op, int input_count, |
| 57 | Node* const* inputs, bool incomplete = false); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 58 | |
| 59 | // Factory that checks the input count. |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 60 | Node* NewNode(const Operator* op, int input_count, Node* const* inputs, |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 61 | bool incomplete = false); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 62 | |
| 63 | // Factories for nodes with static input counts. |
| 64 | Node* NewNode(const Operator* op) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 65 | return NewNode(op, 0, static_cast<Node* const*>(nullptr)); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 66 | } |
| 67 | Node* NewNode(const Operator* op, Node* n1) { return NewNode(op, 1, &n1); } |
| 68 | Node* NewNode(const Operator* op, Node* n1, Node* n2) { |
| 69 | Node* nodes[] = {n1, n2}; |
| 70 | return NewNode(op, arraysize(nodes), nodes); |
| 71 | } |
| 72 | Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3) { |
| 73 | Node* nodes[] = {n1, n2, n3}; |
| 74 | return NewNode(op, arraysize(nodes), nodes); |
| 75 | } |
| 76 | Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4) { |
| 77 | Node* nodes[] = {n1, n2, n3, n4}; |
| 78 | return NewNode(op, arraysize(nodes), nodes); |
| 79 | } |
| 80 | Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4, |
| 81 | Node* n5) { |
| 82 | Node* nodes[] = {n1, n2, n3, n4, n5}; |
| 83 | return NewNode(op, arraysize(nodes), nodes); |
| 84 | } |
| 85 | Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4, |
| 86 | Node* n5, Node* n6) { |
| 87 | Node* nodes[] = {n1, n2, n3, n4, n5, n6}; |
| 88 | return NewNode(op, arraysize(nodes), nodes); |
| 89 | } |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 90 | Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4, |
| 91 | Node* n5, Node* n6, Node* n7) { |
| 92 | Node* nodes[] = {n1, n2, n3, n4, n5, n6, n7}; |
| 93 | return NewNode(op, arraysize(nodes), nodes); |
| 94 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 95 | Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4, |
| 96 | Node* n5, Node* n6, Node* n7, Node* n8) { |
| 97 | Node* nodes[] = {n1, n2, n3, n4, n5, n6, n7, n8}; |
| 98 | return NewNode(op, arraysize(nodes), nodes); |
| 99 | } |
| 100 | Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4, |
| 101 | Node* n5, Node* n6, Node* n7, Node* n8, Node* n9) { |
| 102 | Node* nodes[] = {n1, n2, n3, n4, n5, n6, n7, n8, n9}; |
| 103 | return NewNode(op, arraysize(nodes), nodes); |
| 104 | } |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 105 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 106 | // Clone the {node}, and assign a new node id to the copy. |
| 107 | Node* CloneNode(const Node* node); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 108 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 109 | Zone* zone() const { return zone_; } |
| 110 | Node* start() const { return start_; } |
| 111 | Node* end() const { return end_; } |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 112 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 113 | void SetStart(Node* start) { start_ = start; } |
| 114 | void SetEnd(Node* end) { end_ = end; } |
| 115 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 116 | size_t NodeCount() const { return next_node_id_; } |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 117 | |
| 118 | void Decorate(Node* node); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 119 | void AddDecorator(GraphDecorator* decorator); |
| 120 | void RemoveDecorator(GraphDecorator* decorator); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 121 | |
| 122 | private: |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 123 | friend class NodeMarkerBase; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 124 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 125 | inline NodeId NextNodeId(); |
| 126 | |
| 127 | Zone* const zone_; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 128 | Node* start_; |
| 129 | Node* end_; |
| 130 | Mark mark_max_; |
| 131 | NodeId next_node_id_; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 132 | ZoneVector<GraphDecorator*> decorators_; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 133 | |
| 134 | DISALLOW_COPY_AND_ASSIGN(Graph); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 135 | }; |
| 136 | |
| 137 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 138 | // A graph decorator can be used to add behavior to the creation of nodes |
| 139 | // in a graph. |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 140 | class GraphDecorator : public ZoneObject { |
| 141 | public: |
| 142 | virtual ~GraphDecorator() {} |
| 143 | virtual void Decorate(Node* node) = 0; |
| 144 | }; |
| 145 | |
| 146 | } // namespace compiler |
| 147 | } // namespace internal |
| 148 | } // namespace v8 |
| 149 | |
| 150 | #endif // V8_COMPILER_GRAPH_H_ |