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 <array>
9 
10 #include "src/base/compiler-specific.h"
11 #include "src/common/globals.h"
12 #include "src/zone/zone-containers.h"
13 #include "src/zone/zone.h"
14 
15 namespace v8 {
16 namespace internal {
17 namespace compiler {
18 
19 // Forward declarations.
20 class GraphDecorator;
21 class Node;
22 class Operator;
23 
24 
25 // Marks are used during traversal of the graph to distinguish states of nodes.
26 // Each node has a mark which is a monotonically increasing integer, and a
27 // {NodeMarker} has a range of values that indicate states of a node.
28 using Mark = uint32_t;
29 
30 // NodeIds are identifying numbers for nodes that can be used to index auxiliary
31 // out-of-line data associated with each node.
32 using NodeId = uint32_t;
33 
34 class V8_EXPORT_PRIVATE Graph final : public NON_EXPORTED_BASE(ZoneObject) {
35  public:
36   explicit Graph(Zone* zone);
37   Graph(const Graph&) = delete;
38   Graph& operator=(const Graph&) = delete;
39 
40   // Scope used when creating a subgraph for inlining. Automatically preserves
41   // the original start and end nodes of the graph, and resets them when you
42   // leave the scope.
43   class V8_NODISCARD SubgraphScope final {
44    public:
SubgraphScope(Graph* graph)45     explicit SubgraphScope(Graph* graph)
46         : graph_(graph), start_(graph->start()), end_(graph->end()) {}
~SubgraphScope()47     ~SubgraphScope() {
48       graph_->SetStart(start_);
49       graph_->SetEnd(end_);
50     }
51     SubgraphScope(const SubgraphScope&) = delete;
52     SubgraphScope& operator=(const SubgraphScope&) = delete;
53 
54    private:
55     Graph* const graph_;
56     Node* const start_;
57     Node* const end_;
58   };
59 
60   // Base implementation used by all factory methods.
61   Node* NewNodeUnchecked(const Operator* op, int input_count,
62                          Node* const* inputs, bool incomplete = false);
63 
64   // Factory that checks the input count.
65   Node* NewNode(const Operator* op, int input_count, Node* const* inputs,
66                 bool incomplete = false);
67 
68   // Factory template for nodes with static input counts.
69   // Note: Template magic below is used to ensure this method is only considered
70   // for argument types convertible to Node* during overload resolution.
71   template <typename... Nodes,
72             typename = typename std::enable_if_t<
73                 std::conjunction_v<std::is_convertible<Nodes, Node*>...>>>
NewNode(const Operator* op, Nodes... nodes)74   Node* NewNode(const Operator* op, Nodes... nodes) {
75     std::array<Node*, sizeof...(nodes)> nodes_arr{
76         {static_cast<Node*>(nodes)...}};
77     return NewNode(op, nodes_arr.size(), nodes_arr.data());
78   }
79 
80   // Clone the {node}, and assign a new node id to the copy.
81   Node* CloneNode(const Node* node);
82 
zone() const83   Zone* zone() const { return zone_; }
start() const84   Node* start() const { return start_; }
end() const85   Node* end() const { return end_; }
86 
SetStart(Node* start)87   void SetStart(Node* start) { start_ = start; }
SetEnd(Node* end)88   void SetEnd(Node* end) { end_ = end; }
89 
NodeCount() const90   size_t NodeCount() const { return next_node_id_; }
91 
92   void Decorate(Node* node);
93   void AddDecorator(GraphDecorator* decorator);
94   void RemoveDecorator(GraphDecorator* decorator);
95 
96   // Very simple print API usable in a debugger.
97   void Print() const;
98 
99  private:
100   friend class NodeMarkerBase;
101 
102   inline NodeId NextNodeId();
103 
104   Zone* const zone_;
105   Node* start_;
106   Node* end_;
107   Mark mark_max_;
108   NodeId next_node_id_;
109   ZoneVector<GraphDecorator*> decorators_;
110 };
111 
112 
113 // A graph decorator can be used to add behavior to the creation of nodes
114 // in a graph.
115 class GraphDecorator : public ZoneObject {
116  public:
117   virtual ~GraphDecorator() = default;
118   virtual void Decorate(Node* node) = 0;
119 };
120 
121 }  // namespace compiler
122 }  // namespace internal
123 }  // namespace v8
124 
125 #endif  // V8_COMPILER_GRAPH_H_
126