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
108 // Clone the {node}, and assign a new node id to the copy.
109 Node* CloneNode(const Node* node);
110
111 Zone* zone() const { return zone_; }
112 Node* start() const { return start_; }
113 Node* end() const { return end_; }
114
115 void SetStart(Node* start) { start_ = start; }
116 void SetEnd(Node* end) { end_ = end; }
117
118 size_t NodeCount() const { return next_node_id_; }
119
120 void Decorate(Node* node);
121 void AddDecorator(GraphDecorator* decorator);
122 void RemoveDecorator(GraphDecorator* decorator);
123
124 // Very simple print API usable in a debugger.
125 void Print() const;
126
127 private:
128 friend class NodeMarkerBase;
129
130 inline NodeId NextNodeId();
131
132 Zone* const zone_;
133 Node* start_;
134 Node* end_;
135 Mark mark_max_;
136 NodeId next_node_id_;
137 ZoneVector<GraphDecorator*> decorators_;
138
139 DISALLOW_COPY_AND_ASSIGN(Graph);
140 };
141
142
143 // A graph decorator can be used to add behavior to the creation of nodes
144 // in a graph.
145 class GraphDecorator : public ZoneObject {
146 public:
~GraphDecorator()147 virtual ~GraphDecorator() {}
148 virtual void Decorate(Node* node) = 0;
149 };
150
151 } // namespace compiler
152 } // namespace internal
153 } // namespace v8
154
155 #endif // V8_COMPILER_GRAPH_H_
156