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> |
11 | 11 |
12 #include "src/v8.h" | 12 #include "src/v8.h" |
13 | 13 |
14 #include "src/compiler/generic-algorithm.h" | 14 #include "src/compiler/generic-algorithm.h" |
15 #include "src/compiler/opcodes.h" | 15 #include "src/compiler/opcodes.h" |
16 #include "src/compiler/operator.h" | 16 #include "src/compiler/operator.h" |
17 #include "src/types.h" | 17 #include "src/types.h" |
18 #include "src/zone.h" | 18 #include "src/zone.h" |
19 #include "src/zone-allocator.h" | 19 #include "src/zone-allocator.h" |
20 #include "src/zone-containers.h" | 20 #include "src/zone-containers.h" |
21 | 21 |
22 namespace v8 { | 22 namespace v8 { |
23 namespace internal { | 23 namespace internal { |
24 namespace compiler { | 24 namespace compiler { |
25 | 25 |
| 26 class Edge; |
26 class Graph; | 27 class Graph; |
27 | 28 |
28 // Marks are used during traversal of the graph to distinguish states of nodes. | 29 // 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 | 30 // 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. | 31 // {NodeMarker} has a range of values that indicate states of a node. |
31 typedef uint32_t Mark; | 32 typedef uint32_t Mark; |
32 | 33 |
33 // NodeIds are identifying numbers for nodes that can be used to index auxiliary | 34 // NodeIds are identifying numbers for nodes that can be used to index auxiliary |
34 // out-of-line data associated with each node. | 35 // out-of-line data associated with each node. |
35 typedef int NodeId; | 36 typedef int NodeId; |
(...skipping 46 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
82 } | 83 } |
83 return current->from; | 84 return current->from; |
84 } | 85 } |
85 inline void ReplaceUses(Node* replace_to); | 86 inline void ReplaceUses(Node* replace_to); |
86 template <class UnaryPredicate> | 87 template <class UnaryPredicate> |
87 inline void ReplaceUsesIf(UnaryPredicate pred, Node* replace_to); | 88 inline void ReplaceUsesIf(UnaryPredicate pred, Node* replace_to); |
88 inline void RemoveAllInputs(); | 89 inline void RemoveAllInputs(); |
89 | 90 |
90 inline void TrimInputCount(int input_count); | 91 inline void TrimInputCount(int input_count); |
91 | 92 |
| 93 class InputEdges { |
| 94 public: |
| 95 class iterator; |
| 96 iterator begin() const; |
| 97 iterator end() const; |
| 98 bool empty() const; |
| 99 |
| 100 explicit InputEdges(Node* node) : node_(node) {} |
| 101 |
| 102 private: |
| 103 Node* node_; |
| 104 }; |
| 105 |
92 class Inputs { | 106 class Inputs { |
93 public: | 107 public: |
94 class iterator; | 108 class iterator; |
95 iterator begin(); | 109 iterator begin() const; |
96 iterator end(); | 110 iterator end() const; |
| 111 bool empty() const; |
97 | 112 |
98 explicit Inputs(Node* node) : node_(node) {} | 113 explicit Inputs(Node* node) : node_(node) {} |
99 | 114 |
100 private: | 115 private: |
101 Node* node_; | 116 Node* node_; |
102 }; | 117 }; |
103 | 118 |
104 Inputs inputs() { return Inputs(this); } | 119 Inputs inputs() { return Inputs(this); } |
| 120 InputEdges input_edges() { return InputEdges(this); } |
| 121 |
| 122 class UseEdges { |
| 123 public: |
| 124 class iterator; |
| 125 iterator begin() const; |
| 126 iterator end() const; |
| 127 bool empty() const; |
| 128 |
| 129 explicit UseEdges(Node* node) : node_(node) {} |
| 130 |
| 131 private: |
| 132 Node* node_; |
| 133 }; |
105 | 134 |
106 class Uses { | 135 class Uses { |
107 public: | 136 public: |
108 class iterator; | 137 class iterator; |
109 iterator begin(); | 138 iterator begin() const; |
110 iterator end(); | 139 iterator end() const; |
111 bool empty(); | 140 bool empty() const; |
112 | 141 |
113 explicit Uses(Node* node) : node_(node) {} | 142 explicit Uses(Node* node) : node_(node) {} |
114 | 143 |
115 private: | 144 private: |
116 Node* node_; | 145 Node* node_; |
117 }; | 146 }; |
118 | 147 |
119 Uses uses() { return Uses(this); } | 148 Uses uses() { return Uses(this); } |
120 | 149 UseEdges use_edges() { return UseEdges(this); } |
121 class Edge; | |
122 | 150 |
123 bool OwnedBy(Node* owner) const; | 151 bool OwnedBy(Node* owner) const; |
124 | 152 |
125 static Node* New(Graph* graph, int input_count, Node** inputs, | 153 static Node* New(Graph* graph, int input_count, Node** inputs, |
126 bool has_extensible_inputs); | 154 bool has_extensible_inputs); |
127 | 155 |
128 protected: | 156 protected: |
129 friend class Graph; | 157 friend class Graph; |
| 158 friend class Edge; |
130 | 159 |
131 class Use : public ZoneObject { | 160 class Use : public ZoneObject { |
132 public: | 161 public: |
133 Node* from; | 162 Node* from; |
134 Use* next; | 163 Use* next; |
135 Use* prev; | 164 Use* prev; |
136 int input_index; | 165 int input_index; |
137 }; | 166 }; |
138 | 167 |
139 class Input { | 168 class Input { |
(...skipping 58 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
198 int use_count_; | 227 int use_count_; |
199 Use* first_use_; | 228 Use* first_use_; |
200 Use* last_use_; | 229 Use* last_use_; |
201 | 230 |
202 DISALLOW_COPY_AND_ASSIGN(Node); | 231 DISALLOW_COPY_AND_ASSIGN(Node); |
203 }; | 232 }; |
204 | 233 |
205 | 234 |
206 // An encapsulation for information associated with a single use of node as a | 235 // An encapsulation for information associated with a single use of node as a |
207 // input from another node, allowing access to both the defining node and | 236 // input from another node, allowing access to both the defining node and |
208 // the ndoe having the input. | 237 // the node having the input. |
209 class Node::Edge { | 238 class Edge { |
210 public: | 239 public: |
211 Node* from() const { return input_->use->from; } | 240 Node* from() const { return input_->use->from; } |
212 Node* to() const { return input_->to; } | 241 Node* to() const { return input_->to; } |
213 int index() const { | 242 int index() const { |
214 int index = input_->use->input_index; | 243 int index = input_->use->input_index; |
215 DCHECK(index < input_->use->from->input_count_); | 244 DCHECK(index < input_->use->from->input_count_); |
216 return index; | 245 return index; |
217 } | 246 } |
218 | 247 |
| 248 bool operator==(const Edge& other) { return input_ == other.input_; } |
| 249 bool operator!=(const Edge& other) { return !(*this == other); } |
| 250 |
| 251 void UpdateTo(Node* new_to) { input_->Update(new_to); } |
| 252 |
219 private: | 253 private: |
220 friend class Node::Uses::iterator; | 254 friend class Node::Uses::iterator; |
221 friend class Node::Inputs::iterator; | 255 friend class Node::Inputs::iterator; |
| 256 friend class Node::UseEdges::iterator; |
| 257 friend class Node::InputEdges::iterator; |
222 | 258 |
223 explicit Edge(Node::Input* input) : input_(input) {} | 259 explicit Edge(Node::Input* input) : input_(input) {} |
224 | 260 |
225 Node::Input* input_; | 261 Node::Input* input_; |
226 }; | 262 }; |
227 | 263 |
228 | 264 |
229 // A forward iterator to visit the nodes which are depended upon by a node | 265 // A forward iterator to visit the edges for the input dependencies of a node.. |
230 // in the order of input. | 266 class Node::InputEdges::iterator { |
231 class Node::Inputs::iterator { | |
232 public: | 267 public: |
233 iterator(const Node::Inputs::iterator& other) // NOLINT | 268 typedef std::forward_iterator_tag iterator_category; |
234 : node_(other.node_), | 269 typedef int difference_type; |
235 index_(other.index_) {} | 270 typedef Edge value_type; |
| 271 typedef Edge* pointer; |
| 272 typedef Edge& reference; |
| 273 iterator(const Node::InputEdges::iterator& other) // NOLINT |
| 274 : input_(other.input_) {} |
| 275 iterator() : input_(NULL) {} |
236 | 276 |
237 Node* operator*() { return GetInput()->to; } | 277 Edge operator*() const { return Edge(input_); } |
238 Node::Edge edge() { return Node::Edge(GetInput()); } | 278 bool operator==(const iterator& other) const { return Equals(other); } |
239 bool operator==(const iterator& other) const { | 279 bool operator!=(const iterator& other) const { return !Equals(other); } |
240 return other.index_ == index_ && other.node_ == node_; | |
241 } | |
242 bool operator!=(const iterator& other) const { return !(other == *this); } | |
243 iterator& operator++() { | 280 iterator& operator++() { |
244 DCHECK(node_ != NULL); | 281 DCHECK(input_ != NULL); |
245 DCHECK(index_ < node_->input_count_); | 282 Edge edge(input_); |
246 ++index_; | 283 Node* from = edge.from(); |
| 284 SetInput(from, input_->use->input_index + 1); |
247 return *this; | 285 return *this; |
248 } | 286 } |
249 iterator& UpdateToAndIncrement(Node* new_to) { | 287 iterator operator++(int) { |
250 Node::Input* input = GetInput(); | 288 iterator result(*this); |
251 input->Update(new_to); | 289 ++(*this); |
252 index_++; | 290 return result; |
253 return *this; | |
254 } | 291 } |
255 int index() { return index_; } | |
256 | 292 |
257 private: | 293 private: |
258 friend class Node; | 294 friend class Node; |
259 | 295 |
260 explicit iterator(Node* node, int index) : node_(node), index_(index) {} | 296 explicit iterator(Node* from, int index = 0) : input_(NULL) { |
| 297 SetInput(from, index); |
| 298 } |
261 | 299 |
262 Input* GetInput() const { return node_->GetInputRecordPtr(index_); } | 300 bool Equals(const iterator& other) const { return other.input_ == input_; } |
| 301 void SetInput(Node* from, int index) { |
| 302 DCHECK(index >= 0 && index <= from->InputCount()); |
| 303 if (index < from->InputCount()) { |
| 304 input_ = from->GetInputRecordPtr(index); |
| 305 } else { |
| 306 input_ = NULL; |
| 307 } |
| 308 } |
263 | 309 |
264 Node* node_; | 310 Input* input_; |
265 int index_; | |
266 }; | 311 }; |
267 | 312 |
268 | 313 |
| 314 // A forward iterator to visit the inputs of a node. |
| 315 class Node::Inputs::iterator { |
| 316 public: |
| 317 typedef std::forward_iterator_tag iterator_category; |
| 318 typedef int difference_type; |
| 319 typedef Node* value_type; |
| 320 typedef Node** pointer; |
| 321 typedef Node*& reference; |
| 322 |
| 323 iterator(const Node::Inputs::iterator& other) // NOLINT |
| 324 : iter_(other.iter_) {} |
| 325 |
| 326 Node* operator*() const { return (*iter_).to(); } |
| 327 bool operator==(const iterator& other) const { return Equals(other); } |
| 328 bool operator!=(const iterator& other) const { return !Equals(other); } |
| 329 iterator& operator++() { |
| 330 ++iter_; |
| 331 return *this; |
| 332 } |
| 333 iterator operator++(int) { |
| 334 iterator result(*this); |
| 335 ++(*this); |
| 336 return result; |
| 337 } |
| 338 |
| 339 |
| 340 private: |
| 341 friend class Node::Inputs; |
| 342 |
| 343 explicit iterator(Node* node, int index) : iter_(node, index) {} |
| 344 |
| 345 bool Equals(const iterator& other) const { return other.iter_ == iter_; } |
| 346 |
| 347 Node::InputEdges::iterator iter_; |
| 348 }; |
| 349 |
| 350 // A forward iterator to visit the uses edges of a node. The edges are returned |
| 351 // in |
| 352 // the order in which they were added as inputs. |
| 353 class Node::UseEdges::iterator { |
| 354 public: |
| 355 iterator(const Node::UseEdges::iterator& other) // NOLINT |
| 356 : current_(other.current_), |
| 357 next_(other.next_) {} |
| 358 |
| 359 Edge operator*() const { return Edge(CurrentInput()); } |
| 360 |
| 361 bool operator==(const iterator& other) { return Equals(other); } |
| 362 bool operator!=(const iterator& other) { return !Equals(other); } |
| 363 iterator& operator++() { |
| 364 DCHECK(current_ != NULL); |
| 365 current_ = next_; |
| 366 next_ = (current_ == NULL) ? NULL : current_->next; |
| 367 return *this; |
| 368 } |
| 369 iterator operator++(int) { |
| 370 iterator result(*this); |
| 371 ++(*this); |
| 372 return result; |
| 373 } |
| 374 |
| 375 private: |
| 376 friend class Node::UseEdges; |
| 377 |
| 378 iterator() : current_(NULL), next_(NULL) {} |
| 379 explicit iterator(Node* node) |
| 380 : current_(node->first_use_), |
| 381 next_(current_ == NULL ? NULL : current_->next) {} |
| 382 |
| 383 bool Equals(const iterator& other) const { |
| 384 return other.current_ == current_; |
| 385 } |
| 386 |
| 387 Input* CurrentInput() const { |
| 388 return current_->from->GetInputRecordPtr(current_->input_index); |
| 389 } |
| 390 |
| 391 Node::Use* current_; |
| 392 Node::Use* next_; |
| 393 }; |
| 394 |
| 395 |
269 // A forward iterator to visit the uses of a node. The uses are returned in | 396 // 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. | 397 // the order in which they were added as inputs. |
271 class Node::Uses::iterator { | 398 class Node::Uses::iterator { |
272 public: | 399 public: |
273 iterator(const Node::Uses::iterator& other) // NOLINT | 400 iterator(const Node::Uses::iterator& other) // NOLINT |
274 : current_(other.current_), | 401 : current_(other.current_) {} |
275 index_(other.index_) {} | |
276 | 402 |
277 Node* operator*() { return current_->from; } | 403 Node* operator*() { return current_->from; } |
278 Node::Edge edge() { return Node::Edge(CurrentInput()); } | |
279 | 404 |
280 bool operator==(const iterator& other) { return other.current_ == current_; } | 405 bool operator==(const iterator& other) { return other.current_ == current_; } |
281 bool operator!=(const iterator& other) { return other.current_ != current_; } | 406 bool operator!=(const iterator& other) { return other.current_ != current_; } |
282 iterator& operator++() { | 407 iterator& operator++() { |
283 DCHECK(current_ != NULL); | 408 DCHECK(current_ != NULL); |
284 index_++; | |
285 current_ = current_->next; | 409 current_ = current_->next; |
286 return *this; | 410 return *this; |
287 } | 411 } |
288 iterator& UpdateToAndIncrement(Node* new_to) { | |
289 DCHECK(current_ != NULL); | |
290 index_++; | |
291 Node::Input* input = CurrentInput(); | |
292 current_ = current_->next; | |
293 input->Update(new_to); | |
294 return *this; | |
295 } | |
296 int index() const { return index_; } | |
297 | 412 |
298 private: | 413 private: |
299 friend class Node::Uses; | 414 friend class Node::Uses; |
300 | 415 |
301 iterator() : current_(NULL), index_(0) {} | 416 iterator() : current_(NULL) {} |
302 explicit iterator(Node* node) : current_(node->first_use_), index_(0) {} | 417 explicit iterator(Node* node) : current_(node->first_use_) {} |
303 | 418 |
304 Input* CurrentInput() const { | 419 Input* CurrentInput() const { |
305 return current_->from->GetInputRecordPtr(current_->input_index); | 420 return current_->from->GetInputRecordPtr(current_->input_index); |
306 } | 421 } |
307 | 422 |
308 Node::Use* current_; | 423 Node::Use* current_; |
309 int index_; | |
310 }; | 424 }; |
311 | 425 |
312 | 426 |
313 std::ostream& operator<<(std::ostream& os, const Node& n); | 427 std::ostream& operator<<(std::ostream& os, const Node& n); |
314 | 428 |
315 typedef GenericGraphVisit::NullNodeVisitor NullNodeVisitor; | 429 typedef GenericGraphVisit::NullNodeVisitor NullNodeVisitor; |
316 | 430 |
317 typedef std::set<Node*, std::less<Node*>, zone_allocator<Node*> > NodeSet; | 431 typedef std::set<Node*, std::less<Node*>, zone_allocator<Node*> > NodeSet; |
318 typedef NodeSet::iterator NodeSetIter; | 432 typedef NodeSet::iterator NodeSetIter; |
319 typedef NodeSet::reverse_iterator NodeSetRIter; | 433 typedef NodeSet::reverse_iterator NodeSetRIter; |
(...skipping 11 matching lines...) Expand all Loading... |
331 | 445 |
332 typedef Node::Uses::iterator UseIter; | 446 typedef Node::Uses::iterator UseIter; |
333 typedef Node::Inputs::iterator InputIter; | 447 typedef Node::Inputs::iterator InputIter; |
334 | 448 |
335 // Helper to extract parameters from Operator1<*> nodes. | 449 // Helper to extract parameters from Operator1<*> nodes. |
336 template <typename T> | 450 template <typename T> |
337 static inline const T& OpParameter(const Node* node) { | 451 static inline const T& OpParameter(const Node* node) { |
338 return OpParameter<T>(node->op()); | 452 return OpParameter<T>(node->op()); |
339 } | 453 } |
340 | 454 |
341 inline Node::Inputs::iterator Node::Inputs::begin() { | 455 inline Node::InputEdges::iterator Node::InputEdges::begin() const { |
| 456 return Node::InputEdges::iterator(this->node_, 0); |
| 457 } |
| 458 |
| 459 inline Node::InputEdges::iterator Node::InputEdges::end() const { |
| 460 return Node::InputEdges::iterator(this->node_, this->node_->InputCount()); |
| 461 } |
| 462 |
| 463 inline Node::Inputs::iterator Node::Inputs::begin() const { |
342 return Node::Inputs::iterator(this->node_, 0); | 464 return Node::Inputs::iterator(this->node_, 0); |
343 } | 465 } |
344 | 466 |
345 inline Node::Inputs::iterator Node::Inputs::end() { | 467 inline Node::Inputs::iterator Node::Inputs::end() const { |
346 return Node::Inputs::iterator(this->node_, this->node_->InputCount()); | 468 return Node::Inputs::iterator(this->node_, this->node_->InputCount()); |
347 } | 469 } |
348 | 470 |
349 inline Node::Uses::iterator Node::Uses::begin() { | 471 inline Node::UseEdges::iterator Node::UseEdges::begin() const { |
| 472 return Node::UseEdges::iterator(this->node_); |
| 473 } |
| 474 |
| 475 inline Node::UseEdges::iterator Node::UseEdges::end() const { |
| 476 return Node::UseEdges::iterator(); |
| 477 } |
| 478 |
| 479 inline Node::Uses::iterator Node::Uses::begin() const { |
350 return Node::Uses::iterator(this->node_); | 480 return Node::Uses::iterator(this->node_); |
351 } | 481 } |
352 | 482 |
353 inline Node::Uses::iterator Node::Uses::end() { return Node::Uses::iterator(); } | 483 inline Node::Uses::iterator Node::Uses::end() const { |
| 484 return Node::Uses::iterator(); |
| 485 } |
354 | 486 |
355 inline bool Node::Uses::empty() { return begin() == end(); } | 487 inline bool Node::InputEdges::empty() const { return begin() == end(); } |
| 488 inline bool Node::Uses::empty() const { return begin() == end(); } |
| 489 inline bool Node::UseEdges::empty() const { return begin() == end(); } |
| 490 inline bool Node::Inputs::empty() const { return begin() == end(); } |
356 | 491 |
357 inline void Node::ReplaceUses(Node* replace_to) { | 492 inline void Node::ReplaceUses(Node* replace_to) { |
358 for (Use* use = first_use_; use != NULL; use = use->next) { | 493 for (Use* use = first_use_; use != NULL; use = use->next) { |
359 use->from->GetInputRecordPtr(use->input_index)->to = replace_to; | 494 use->from->GetInputRecordPtr(use->input_index)->to = replace_to; |
360 } | 495 } |
361 if (replace_to->last_use_ == NULL) { | 496 if (replace_to->last_use_ == NULL) { |
362 DCHECK_EQ(NULL, replace_to->first_use_); | 497 DCHECK_EQ(NULL, replace_to->first_use_); |
363 replace_to->first_use_ = first_use_; | 498 replace_to->first_use_ = first_use_; |
364 replace_to->last_use_ = last_use_; | 499 replace_to->last_use_ = last_use_; |
365 } else if (first_use_ != NULL) { | 500 } else if (first_use_ != NULL) { |
(...skipping 15 matching lines...) Expand all Loading... |
381 if (pred(use->from)) { | 516 if (pred(use->from)) { |
382 RemoveUse(use); | 517 RemoveUse(use); |
383 replace_to->AppendUse(use); | 518 replace_to->AppendUse(use); |
384 use->from->GetInputRecordPtr(use->input_index)->to = replace_to; | 519 use->from->GetInputRecordPtr(use->input_index)->to = replace_to; |
385 } | 520 } |
386 use = next; | 521 use = next; |
387 } | 522 } |
388 } | 523 } |
389 | 524 |
390 inline void Node::RemoveAllInputs() { | 525 inline void Node::RemoveAllInputs() { |
391 for (Inputs::iterator iter(inputs().begin()); iter != inputs().end(); | 526 for (Edge edge : input_edges()) { |
392 ++iter) { | 527 edge.UpdateTo(NULL); |
393 iter.GetInput()->Update(NULL); | |
394 } | 528 } |
395 } | 529 } |
396 | 530 |
397 inline void Node::TrimInputCount(int new_input_count) { | 531 inline void Node::TrimInputCount(int new_input_count) { |
398 if (new_input_count == input_count_) return; // Nothing to do. | 532 if (new_input_count == input_count_) return; // Nothing to do. |
399 | 533 |
400 DCHECK(new_input_count < input_count_); | 534 DCHECK(new_input_count < input_count_); |
401 | 535 |
402 // Update inline inputs. | 536 // Update inline inputs. |
403 for (int i = new_input_count; i < input_count_; i++) { | 537 for (int i = new_input_count; i < input_count_; i++) { |
(...skipping 105 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
509 inline bool Node::OwnedBy(Node* owner) const { | 643 inline bool Node::OwnedBy(Node* owner) const { |
510 return first_use_ != NULL && first_use_->from == owner && | 644 return first_use_ != NULL && first_use_->from == owner && |
511 first_use_->next == NULL; | 645 first_use_->next == NULL; |
512 } | 646 } |
513 | 647 |
514 } // namespace compiler | 648 } // namespace compiler |
515 } // namespace internal | 649 } // namespace internal |
516 } // namespace v8 | 650 } // namespace v8 |
517 | 651 |
518 #endif // V8_COMPILER_NODE_H_ | 652 #endif // V8_COMPILER_NODE_H_ |
OLD | NEW |