• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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