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
8 #include "src/base/compiler-specific.h"
9 #include "src/globals.h"
10 #include "src/zone/zone-containers.h"
11 #include "src/zone/zone.h"
12
13 namespace v8 {
14 namespace internal {
15 namespace compiler {
16
17 // Forward declarations.
18 class GraphDecorator;
19 class Node;
20 class Operator;
21
22
23 // Marks are used during traversal of the graph to distinguish states of nodes.
24 // Each node has a mark which is a monotonically increasing integer, and a
25 // {NodeMarker} has a range of values that indicate states of a node.
26 typedef uint32_t Mark;
27
28
29 // NodeIds are identifying numbers for nodes that can be used to index auxiliary
30 // out-of-line data associated with each node.
31 typedef uint32_t NodeId;
32
NON_EXPORTED_BASE(ZoneObject)33 class V8_EXPORT_PRIVATE Graph final : public NON_EXPORTED_BASE(ZoneObject) {
34 public:
35 explicit Graph(Zone* zone);
36
37 // Scope used when creating a subgraph for inlining. Automatically preserves
38 // the original start and end nodes of the graph, and resets them when you
39 // leave the scope.
40 class SubgraphScope final {
41 public:
42 explicit SubgraphScope(Graph* graph)
43 : graph_(graph), start_(graph->start()), end_(graph->end()) {}
44 ~SubgraphScope() {
45 graph_->SetStart(start_);
46 graph_->SetEnd(end_);
47 }
48
49 private:
50 Graph* const graph_;
51 Node* const start_;
52 Node* const end_;
53
54 DISALLOW_COPY_AND_ASSIGN(SubgraphScope);
55 };
56
57 // Base implementation used by all factory methods.
58 Node* NewNodeUnchecked(const Operator* op, int input_count,
59 Node* const* inputs, bool incomplete = false);
60
61 // Factory that checks the input count.
62 Node* NewNode(const Operator* op, int input_count, Node* const* inputs,
63 bool incomplete = false);
64
65 // Factories for nodes with static input counts.
66 Node* NewNode(const Operator* op) {
67 return NewNode(op, 0, static_cast<Node* const*>(nullptr));
68 }
69 Node* NewNode(const Operator* op, Node* n1) { return NewNode(op, 1, &n1); }
70 Node* NewNode(const Operator* op, Node* n1, Node* n2) {
71 Node* nodes[] = {n1, n2};
72 return NewNode(op, arraysize(nodes), nodes);
73 }
74 Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3) {
75 Node* nodes[] = {n1, n2, n3};
76 return NewNode(op, arraysize(nodes), nodes);
77 }
78 Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4) {
79 Node* nodes[] = {n1, n2, n3, n4};
80 return NewNode(op, arraysize(nodes), nodes);
81 }
82 Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4,
83 Node* n5) {
84 Node* nodes[] = {n1, n2, n3, n4, n5};
85 return NewNode(op, arraysize(nodes), nodes);
86 }
87 Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4,
88 Node* n5, Node* n6) {
89 Node* nodes[] = {n1, n2, n3, n4, n5, n6};
90 return NewNode(op, arraysize(nodes), nodes);
91 }
92 Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4,
93 Node* n5, Node* n6, Node* n7) {
94 Node* nodes[] = {n1, n2, n3, n4, n5, n6, n7};
95 return NewNode(op, arraysize(nodes), nodes);
96 }
97 Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4,
98 Node* n5, Node* n6, Node* n7, Node* n8) {
99 Node* nodes[] = {n1, n2, n3, n4, n5, n6, n7, n8};
100 return NewNode(op, arraysize(nodes), nodes);
101 }
102 Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4,
103 Node* n5, Node* n6, Node* n7, Node* n8, Node* n9) {
104 Node* nodes[] = {n1, n2, n3, n4, n5, n6, n7, n8, n9};
105 return NewNode(op, arraysize(nodes), nodes);
106 }
107 Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4,
108 Node* n5, Node* n6, Node* n7, Node* n8, Node* n9, Node* n10) {
109 Node* nodes[] = {n1, n2, n3, n4, n5, n6, n7, n8, n9, n10};
110 return NewNode(op, arraysize(nodes), nodes);
111 }
112 Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4,
113 Node* n5, Node* n6, Node* n7, Node* n8, Node* n9, Node* n10,
114 Node* n11) {
115 Node* nodes[] = {n1, n2, n3, n4, n5, n6, n7, n8, n9, n10, n11};
116 return NewNode(op, arraysize(nodes), nodes);
117 }
118 Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4,
119 Node* n5, Node* n6, Node* n7, Node* n8, Node* n9, Node* n10,
120 Node* n11, Node* n12) {
121 Node* nodes[] = {n1, n2, n3, n4, n5, n6, n7, n8, n9, n10, n11, n12};
122 return NewNode(op, arraysize(nodes), nodes);
123 }
124 Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4,
125 Node* n5, Node* n6, Node* n7, Node* n8, Node* n9, Node* n10,
126 Node* n11, Node* n12, Node* n13) {
127 Node* nodes[] = {n1, n2, n3, n4, n5, n6, n7, n8, n9, n10, n11, n12, n13};
128 return NewNode(op, arraysize(nodes), nodes);
129 }
130 Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4,
131 Node* n5, Node* n6, Node* n7, Node* n8, Node* n9, Node* n10,
132 Node* n11, Node* n12, Node* n13, Node* n14) {
133 Node* nodes[] = {n1, n2, n3, n4, n5, n6, n7,
134 n8, n9, n10, n11, n12, n13, n14};
135 return NewNode(op, arraysize(nodes), nodes);
136 }
137 Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4,
138 Node* n5, Node* n6, Node* n7, Node* n8, Node* n9, Node* n10,
139 Node* n11, Node* n12, Node* n13, Node* n14, Node* n15) {
140 Node* nodes[] = {n1, n2, n3, n4, n5, n6, n7, n8,
141 n9, n10, n11, n12, n13, n14, n15};
142 return NewNode(op, arraysize(nodes), nodes);
143 }
144 Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4,
145 Node* n5, Node* n6, Node* n7, Node* n8, Node* n9, Node* n10,
146 Node* n11, Node* n12, Node* n13, Node* n14, Node* n15,
147 Node* n16) {
148 Node* nodes[] = {n1, n2, n3, n4, n5, n6, n7, n8,
149 n9, n10, n11, n12, n13, n14, n15, n16};
150 return NewNode(op, arraysize(nodes), nodes);
151 }
152 Node* NewNode(const Operator* op, Node* n1, Node* n2, Node* n3, Node* n4,
153 Node* n5, Node* n6, Node* n7, Node* n8, Node* n9, Node* n10,
154 Node* n11, Node* n12, Node* n13, Node* n14, Node* n15,
155 Node* n16, Node* n17) {
156 Node* nodes[] = {n1, n2, n3, n4, n5, n6, n7, n8, n9,
157 n10, n11, n12, n13, n14, n15, n16, n17};
158 return NewNode(op, arraysize(nodes), nodes);
159 }
160
161 // Clone the {node}, and assign a new node id to the copy.
162 Node* CloneNode(const Node* node);
163
164 Zone* zone() const { return zone_; }
165 Node* start() const { return start_; }
166 Node* end() const { return end_; }
167
168 void SetStart(Node* start) { start_ = start; }
169 void SetEnd(Node* end) { end_ = end; }
170
171 size_t NodeCount() const { return next_node_id_; }
172
173 void Decorate(Node* node);
174 void AddDecorator(GraphDecorator* decorator);
175 void RemoveDecorator(GraphDecorator* decorator);
176
177 // Very simple print API usable in a debugger.
178 void Print() const;
179
180 private:
181 friend class NodeMarkerBase;
182
183 inline NodeId NextNodeId();
184
185 Zone* const zone_;
186 Node* start_;
187 Node* end_;
188 Mark mark_max_;
189 NodeId next_node_id_;
190 ZoneVector<GraphDecorator*> decorators_;
191
192 DISALLOW_COPY_AND_ASSIGN(Graph);
193 };
194
195
196 // A graph decorator can be used to add behavior to the creation of nodes
197 // in a graph.
198 class GraphDecorator : public ZoneObject {
199 public:
~GraphDecorator()200 virtual ~GraphDecorator() {}
201 virtual void Decorate(Node* node) = 0;
202 };
203
204 } // namespace compiler
205 } // namespace internal
206 } // namespace v8
207
208 #endif // V8_COMPILER_GRAPH_H_
209