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 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: 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