| OLD | NEW |
| 1 // Copyright 2013 the V8 project authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 | 4 |
| 5 #ifndef V8_COMPILER_NODE_H_ | 5 #ifndef V8_COMPILER_NODE_H_ |
| 6 #define V8_COMPILER_NODE_H_ | 6 #define V8_COMPILER_NODE_H_ |
| 7 | 7 |
| 8 #include <deque> | 8 #include <deque> |
| 9 #include <set> | 9 #include <set> |
| 10 #include <vector> | 10 #include <vector> |
| (...skipping 12 matching lines...) Expand all Loading... |
| 23 namespace internal { | 23 namespace internal { |
| 24 namespace compiler { | 24 namespace compiler { |
| 25 | 25 |
| 26 class Graph; | 26 class Graph; |
| 27 | 27 |
| 28 // Marks are used during traversal of the graph to distinguish states of nodes. | 28 // Marks are used during traversal of the graph to distinguish states of nodes. |
| 29 // Each node has a mark which is a monotonically increasing integer, and a | 29 // Each node has a mark which is a monotonically increasing integer, and a |
| 30 // {NodeMarker} has a range of values that indicate states of a node. | 30 // {NodeMarker} has a range of values that indicate states of a node. |
| 31 typedef uint32_t Mark; | 31 typedef uint32_t Mark; |
| 32 | 32 |
| 33 class NodeData { | 33 // NodeIds are identifying numbers for nodes that can be used to index auxiliary |
| 34 public: | 34 // out-of-line data associated with each node. |
| 35 const Operator* op() const { return op_; } | |
| 36 void set_op(const Operator* op) { op_ = op; } | |
| 37 | |
| 38 IrOpcode::Value opcode() const { | |
| 39 DCHECK(op_->opcode() <= IrOpcode::kLast); | |
| 40 return static_cast<IrOpcode::Value>(op_->opcode()); | |
| 41 } | |
| 42 | |
| 43 protected: | |
| 44 const Operator* op_; | |
| 45 Bounds bounds_; | |
| 46 Mark mark_; | |
| 47 explicit NodeData(Zone* zone) {} | |
| 48 | |
| 49 friend class NodeProperties; | |
| 50 template <typename State> | |
| 51 friend class NodeMarker; | |
| 52 | |
| 53 Bounds bounds() { return bounds_; } | |
| 54 void set_bounds(Bounds b) { bounds_ = b; } | |
| 55 | |
| 56 // Only NodeMarkers should manipulate the marks on nodes. | |
| 57 Mark mark() { return mark_; } | |
| 58 void set_mark(Mark mark) { mark_ = mark; } | |
| 59 }; | |
| 60 | |
| 61 typedef int NodeId; | 35 typedef int NodeId; |
| 62 | 36 |
| 63 // A Node is the basic primitive of graphs. Nodes are chained together by | 37 // A Node is the basic primitive of graphs. Nodes are chained together by |
| 64 // input/use chains but by default otherwise contain only an identifying number | 38 // input/use chains but by default otherwise contain only an identifying number |
| 65 // which specific applications of graphs and nodes can use to index auxiliary | 39 // which specific applications of graphs and nodes can use to index auxiliary |
| 66 // out-of-line data, especially transient data. | 40 // out-of-line data, especially transient data. |
| 67 // | 41 // |
| 68 // In addition Nodes only contain a mutable Operator that may change during | 42 // In addition Nodes only contain a mutable Operator that may change during |
| 69 // compilation, e.g. during lowering passes. Other information that needs to be | 43 // compilation, e.g. during lowering passes. Other information that needs to be |
| 70 // associated with Nodes during compilation must be stored out-of-line indexed | 44 // associated with Nodes during compilation must be stored out-of-line indexed |
| 71 // by the Node's id. | 45 // by the Node's id. |
| 72 class Node FINAL : public NodeData { | 46 class Node FINAL { |
| 73 public: | 47 public: |
| 74 void Initialize(const Operator* op) { | 48 void Initialize(const Operator* op) { |
| 75 set_op(op); | 49 set_op(op); |
| 76 set_mark(0); | 50 set_mark(0); |
| 77 } | 51 } |
| 78 | 52 |
| 79 bool IsDead() const { return InputCount() > 0 && InputAt(0) == NULL; } | 53 bool IsDead() const { return InputCount() > 0 && InputAt(0) == NULL; } |
| 80 void Kill(); | 54 void Kill(); |
| 81 | 55 |
| 82 void CollectProjections(ZoneVector<Node*>* projections); | 56 void CollectProjections(ZoneVector<Node*>* projections); |
| 83 Node* FindProjection(size_t projection_index); | 57 Node* FindProjection(size_t projection_index); |
| 84 | 58 |
| 85 inline NodeId id() const { return id_; } | 59 const Operator* op() const { return op_; } |
| 60 void set_op(const Operator* op) { op_ = op; } |
| 61 |
| 62 IrOpcode::Value opcode() const { |
| 63 DCHECK(op_->opcode() <= IrOpcode::kLast); |
| 64 return static_cast<IrOpcode::Value>(op_->opcode()); |
| 65 } |
| 66 |
| 67 NodeId id() const { return id_; } |
| 86 | 68 |
| 87 int InputCount() const { return input_count_; } | 69 int InputCount() const { return input_count_; } |
| 88 Node* InputAt(int index) const { return GetInputRecordPtr(index)->to; } | 70 Node* InputAt(int index) const { return GetInputRecordPtr(index)->to; } |
| 89 inline void ReplaceInput(int index, Node* new_input); | 71 inline void ReplaceInput(int index, Node* new_input); |
| 90 inline void AppendInput(Zone* zone, Node* new_input); | 72 inline void AppendInput(Zone* zone, Node* new_input); |
| 91 inline void InsertInput(Zone* zone, int index, Node* new_input); | 73 inline void InsertInput(Zone* zone, int index, Node* new_input); |
| 92 inline void RemoveInput(int index); | 74 inline void RemoveInput(int index); |
| 93 | 75 |
| 94 int UseCount() { return use_count_; } | 76 int UseCount() { return use_count_; } |
| 95 Node* UseAt(int index) { | 77 Node* UseAt(int index) { |
| (...skipping 79 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 175 inline void AppendUse(Use* use); | 157 inline void AppendUse(Use* use); |
| 176 inline void RemoveUse(Use* use); | 158 inline void RemoveUse(Use* use); |
| 177 | 159 |
| 178 void* operator new(size_t, void* location) { return location; } | 160 void* operator new(size_t, void* location) { return location; } |
| 179 | 161 |
| 180 private: | 162 private: |
| 181 Node(Graph* graph, int input_count, int reserve_input_count); | 163 Node(Graph* graph, int input_count, int reserve_input_count); |
| 182 | 164 |
| 183 typedef ZoneDeque<Input> InputDeque; | 165 typedef ZoneDeque<Input> InputDeque; |
| 184 | 166 |
| 167 friend class NodeProperties; |
| 168 template <typename State> |
| 169 friend class NodeMarker; |
| 170 |
| 171 // Only NodeProperties should manipulate the bounds. |
| 172 Bounds bounds() { return bounds_; } |
| 173 void set_bounds(Bounds b) { bounds_ = b; } |
| 174 |
| 175 // Only NodeMarkers should manipulate the marks on nodes. |
| 176 Mark mark() { return mark_; } |
| 177 void set_mark(Mark mark) { mark_ = mark; } |
| 178 |
| 185 static const int kReservedInputCountBits = 2; | 179 static const int kReservedInputCountBits = 2; |
| 186 static const int kMaxReservedInputs = (1 << kReservedInputCountBits) - 1; | 180 static const int kMaxReservedInputs = (1 << kReservedInputCountBits) - 1; |
| 187 static const int kDefaultReservedInputs = kMaxReservedInputs; | 181 static const int kDefaultReservedInputs = kMaxReservedInputs; |
| 188 | 182 |
| 183 const Operator* op_; |
| 184 Bounds bounds_; |
| 185 Mark mark_; |
| 189 NodeId id_; | 186 NodeId id_; |
| 190 int input_count_ : 29; | 187 int input_count_ : 29; |
| 191 unsigned int reserve_input_count_ : kReservedInputCountBits; | 188 unsigned int reserve_input_count_ : kReservedInputCountBits; |
| 192 bool has_appendable_inputs_ : 1; | 189 bool has_appendable_inputs_ : 1; |
| 193 union { | 190 union { |
| 194 // When a node is initially allocated, it uses a static buffer to hold its | 191 // When a node is initially allocated, it uses a static buffer to hold its |
| 195 // inputs under the assumption that the number of outputs will not increase. | 192 // inputs under the assumption that the number of outputs will not increase. |
| 196 // When the first input is appended, the static buffer is converted into a | 193 // When the first input is appended, the static buffer is converted into a |
| 197 // deque to allow for space-efficient growing. | 194 // deque to allow for space-efficient growing. |
| 198 Input* static_; | 195 Input* static_; |
| 199 InputDeque* appendable_; | 196 InputDeque* appendable_; |
| 200 } inputs_; | 197 } inputs_; |
| 201 int use_count_; | 198 int use_count_; |
| 202 Use* first_use_; | 199 Use* first_use_; |
| 203 Use* last_use_; | 200 Use* last_use_; |
| 204 | 201 |
| 205 DISALLOW_COPY_AND_ASSIGN(Node); | 202 DISALLOW_COPY_AND_ASSIGN(Node); |
| 206 }; | 203 }; |
| 207 | 204 |
| 205 |
| 208 // An encapsulation for information associated with a single use of node as a | 206 // An encapsulation for information associated with a single use of node as a |
| 209 // input from another node, allowing access to both the defining node and | 207 // input from another node, allowing access to both the defining node and |
| 210 // the ndoe having the input. | 208 // the ndoe having the input. |
| 211 class Node::Edge { | 209 class Node::Edge { |
| 212 public: | 210 public: |
| 213 Node* from() const { return input_->use->from; } | 211 Node* from() const { return input_->use->from; } |
| 214 Node* to() const { return input_->to; } | 212 Node* to() const { return input_->to; } |
| 215 int index() const { | 213 int index() const { |
| 216 int index = input_->use->input_index; | 214 int index = input_->use->input_index; |
| 217 DCHECK(index < input_->use->from->input_count_); | 215 DCHECK(index < input_->use->from->input_count_); |
| 218 return index; | 216 return index; |
| 219 } | 217 } |
| 220 | 218 |
| 221 private: | 219 private: |
| 222 friend class Node::Uses::iterator; | 220 friend class Node::Uses::iterator; |
| 223 friend class Node::Inputs::iterator; | 221 friend class Node::Inputs::iterator; |
| 224 | 222 |
| 225 explicit Edge(Node::Input* input) : input_(input) {} | 223 explicit Edge(Node::Input* input) : input_(input) {} |
| 226 | 224 |
| 227 Node::Input* input_; | 225 Node::Input* input_; |
| 228 }; | 226 }; |
| 229 | 227 |
| 228 |
| 230 // A forward iterator to visit the nodes which are depended upon by a node | 229 // A forward iterator to visit the nodes which are depended upon by a node |
| 231 // in the order of input. | 230 // in the order of input. |
| 232 class Node::Inputs::iterator { | 231 class Node::Inputs::iterator { |
| 233 public: | 232 public: |
| 234 iterator(const Node::Inputs::iterator& other) // NOLINT | 233 iterator(const Node::Inputs::iterator& other) // NOLINT |
| 235 : node_(other.node_), | 234 : node_(other.node_), |
| 236 index_(other.index_) {} | 235 index_(other.index_) {} |
| 237 | 236 |
| 238 Node* operator*() { return GetInput()->to; } | 237 Node* operator*() { return GetInput()->to; } |
| 239 Node::Edge edge() { return Node::Edge(GetInput()); } | 238 Node::Edge edge() { return Node::Edge(GetInput()); } |
| (...skipping 19 matching lines...) Expand all Loading... |
| 259 friend class Node; | 258 friend class Node; |
| 260 | 259 |
| 261 explicit iterator(Node* node, int index) : node_(node), index_(index) {} | 260 explicit iterator(Node* node, int index) : node_(node), index_(index) {} |
| 262 | 261 |
| 263 Input* GetInput() const { return node_->GetInputRecordPtr(index_); } | 262 Input* GetInput() const { return node_->GetInputRecordPtr(index_); } |
| 264 | 263 |
| 265 Node* node_; | 264 Node* node_; |
| 266 int index_; | 265 int index_; |
| 267 }; | 266 }; |
| 268 | 267 |
| 268 |
| 269 // A forward iterator to visit the uses of a node. The uses are returned in | 269 // A forward iterator to visit the uses of a node. The uses are returned in |
| 270 // the order in which they were added as inputs. | 270 // the order in which they were added as inputs. |
| 271 class Node::Uses::iterator { | 271 class Node::Uses::iterator { |
| 272 public: | 272 public: |
| 273 iterator(const Node::Uses::iterator& other) // NOLINT | 273 iterator(const Node::Uses::iterator& other) // NOLINT |
| 274 : current_(other.current_), | 274 : current_(other.current_), |
| 275 index_(other.index_) {} | 275 index_(other.index_) {} |
| 276 | 276 |
| 277 Node* operator*() { return current_->from; } | 277 Node* operator*() { return current_->from; } |
| 278 Node::Edge edge() { return Node::Edge(CurrentInput()); } | 278 Node::Edge edge() { return Node::Edge(CurrentInput()); } |
| (...skipping 23 matching lines...) Expand all Loading... |
| 302 explicit iterator(Node* node) : current_(node->first_use_), index_(0) {} | 302 explicit iterator(Node* node) : current_(node->first_use_), index_(0) {} |
| 303 | 303 |
| 304 Input* CurrentInput() const { | 304 Input* CurrentInput() const { |
| 305 return current_->from->GetInputRecordPtr(current_->input_index); | 305 return current_->from->GetInputRecordPtr(current_->input_index); |
| 306 } | 306 } |
| 307 | 307 |
| 308 Node::Use* current_; | 308 Node::Use* current_; |
| 309 int index_; | 309 int index_; |
| 310 }; | 310 }; |
| 311 | 311 |
| 312 |
| 312 std::ostream& operator<<(std::ostream& os, const Node& n); | 313 std::ostream& operator<<(std::ostream& os, const Node& n); |
| 313 | 314 |
| 314 typedef GenericGraphVisit::NullNodeVisitor NullNodeVisitor; | 315 typedef GenericGraphVisit::NullNodeVisitor NullNodeVisitor; |
| 315 | 316 |
| 316 typedef std::set<Node*, std::less<Node*>, zone_allocator<Node*> > NodeSet; | 317 typedef std::set<Node*, std::less<Node*>, zone_allocator<Node*> > NodeSet; |
| 317 typedef NodeSet::iterator NodeSetIter; | 318 typedef NodeSet::iterator NodeSetIter; |
| 318 typedef NodeSet::reverse_iterator NodeSetRIter; | 319 typedef NodeSet::reverse_iterator NodeSetRIter; |
| 319 | 320 |
| 320 typedef ZoneDeque<Node*> NodeDeque; | 321 typedef ZoneDeque<Node*> NodeDeque; |
| 321 | 322 |
| (...skipping 186 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 508 inline bool Node::OwnedBy(Node* owner) const { | 509 inline bool Node::OwnedBy(Node* owner) const { |
| 509 return first_use_ != NULL && first_use_->from == owner && | 510 return first_use_ != NULL && first_use_->from == owner && |
| 510 first_use_->next == NULL; | 511 first_use_->next == NULL; |
| 511 } | 512 } |
| 512 | 513 |
| 513 } // namespace compiler | 514 } // namespace compiler |
| 514 } // namespace internal | 515 } // namespace internal |
| 515 } // namespace v8 | 516 } // namespace v8 |
| 516 | 517 |
| 517 #endif // V8_COMPILER_NODE_H_ | 518 #endif // V8_COMPILER_NODE_H_ |
| OLD | NEW |