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_NODE_H_ 6#define V8_COMPILER_NODE_H_ 7 8#include "src/compiler/opcodes.h" 9#include "src/compiler/operator.h" 10#include "src/compiler/types.h" 11#include "src/globals.h" 12#include "src/zone/zone-containers.h" 13 14namespace v8 { 15namespace internal { 16namespace compiler { 17 18// Forward declarations. 19class Edge; 20class Graph; 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. 26typedef 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. 31typedef uint32_t NodeId; 32 33 34// A Node is the basic primitive of graphs. Nodes are chained together by 35// input/use chains but by default otherwise contain only an identifying number 36// which specific applications of graphs and nodes can use to index auxiliary 37// out-of-line data, especially transient data. 38// 39// In addition Nodes only contain a mutable Operator that may change during 40// compilation, e.g. during lowering passes. Other information that needs to be 41// associated with Nodes during compilation must be stored out-of-line indexed 42// by the Node's id. 43class V8_EXPORT_PRIVATE Node final { 44 public: 45 static Node* New(Zone* zone, NodeId id, const Operator* op, int input_count, 46 Node* const* inputs, bool has_extensible_inputs); 47 static Node* Clone(Zone* zone, NodeId id, const Node* node); 48 49 inline bool IsDead() const; 50 void Kill(); 51 52 const Operator* op() const { return op_; } 53 54 IrOpcode::Value opcode() const { 55 DCHECK(op_->opcode() <= IrOpcode::kLast); 56 return static_cast<IrOpcode::Value>(op_->opcode()); 57 } 58 59 NodeId id() const { return IdField::decode(bit_field_); } 60 61 int InputCount() const { 62 return has_inline_inputs() ? InlineCountField::decode(bit_field_) 63 : inputs_.outline_->count_; 64 } 65 66#if DEBUG 67 void Verify(); 68#define BOUNDS_CHECK(index) \ 69 do { \ 70 if (index < 0 || index >= InputCount()) { \ 71 V8_Fatal(__FILE__, __LINE__, "Node #%d:%s->InputAt(%d) out of bounds", \ 72 id(), op()->mnemonic(), index); \ 73 } \ 74 } while (false) 75#else 76 // No bounds checks or verification in release mode. 77 inline void Verify() {} 78#define BOUNDS_CHECK(index) \ 79 do { \ 80 } while (false) 81#endif 82 83 Node* InputAt(int index) const { 84 BOUNDS_CHECK(index); 85 return *GetInputPtrConst(index); 86 } 87 88 void ReplaceInput(int index, Node* new_to) { 89 BOUNDS_CHECK(index); 90 Node** input_ptr = GetInputPtr(index); 91 Node* old_to = *input_ptr; 92 if (old_to != new_to) { 93 Use* use = GetUsePtr(index); 94 if (old_to) old_to->RemoveUse(use); 95 *input_ptr = new_to; 96 if (new_to) new_to->AppendUse(use); 97 } 98 } 99 100#undef BOUNDS_CHECK 101 102 void AppendInput(Zone* zone, Node* new_to); 103 void InsertInput(Zone* zone, int index, Node* new_to); 104 void InsertInputs(Zone* zone, int index, int count); 105 void RemoveInput(int index); 106 void NullAllInputs(); 107 void TrimInputCount(int new_input_count); 108 109 int UseCount() const; 110 void ReplaceUses(Node* replace_to); 111 112 class InputEdges; 113 inline InputEdges input_edges(); 114 115 class Inputs; 116 inline Inputs inputs() const; 117 118 class UseEdges final { 119 public: 120 typedef Edge value_type; 121 122 class iterator; 123 inline iterator begin() const; 124 inline iterator end() const; 125 126 bool empty() const; 127 128 explicit UseEdges(Node* node) : node_(node) {} 129 130 private: 131 Node* node_; 132 }; 133 134 UseEdges use_edges() { return UseEdges(this); } 135 136 class V8_EXPORT_PRIVATE Uses final { 137 public: 138 typedef Node* value_type; 139 140 class const_iterator; 141 inline const_iterator begin() const; 142 inline const_iterator end() const; 143 144 bool empty() const; 145 146 explicit Uses(Node* node) : node_(node) {} 147 148 private: 149 Node* node_; 150 }; 151 152 Uses uses() { return Uses(this); } 153 154 // Returns true if {owner} is the user of {this} node. 155 bool OwnedBy(Node* owner) const { 156 return first_use_ && first_use_->from() == owner && !first_use_->next; 157 } 158 159 // Returns true if {owner1} and {owner2} are the only users of {this} node. 160 bool OwnedBy(Node const* owner1, Node const* owner2) const; 161 162 // Returns true if addressing related operands (such as load, store, lea) 163 // are the only users of {this} node. 164 bool OwnedByAddressingOperand() const; 165 void Print() const; 166 167 private: 168 struct Use; 169 // Out of line storage for inputs when the number of inputs overflowed the 170 // capacity of the inline-allocated space. 171 struct OutOfLineInputs { 172 Node* node_; 173 int count_; 174 int capacity_; 175 Node* inputs_[1]; 176 177 static OutOfLineInputs* New(Zone* zone, int capacity); 178 void ExtractFrom(Use* use_ptr, Node** input_ptr, int count); 179 }; 180 181 // A link in the use chain for a node. Every input {i} to a node {n} has an 182 // associated {Use} which is linked into the use chain of the {i} node. 183 struct Use { 184 Use* next; 185 Use* prev; 186 uint32_t bit_field_; 187 188 int input_index() const { return InputIndexField::decode(bit_field_); } 189 bool is_inline_use() const { return InlineField::decode(bit_field_); } 190 Node** input_ptr() { 191 int index = input_index(); 192 Use* start = this + 1 + index; 193 Node** inputs = is_inline_use() 194 ? reinterpret_cast<Node*>(start)->inputs_.inline_ 195 : reinterpret_cast<OutOfLineInputs*>(start)->inputs_; 196 return &inputs[index]; 197 } 198 199 Node* from() { 200 Use* start = this + 1 + input_index(); 201 return is_inline_use() ? reinterpret_cast<Node*>(start) 202 : reinterpret_cast<OutOfLineInputs*>(start)->node_; 203 } 204 205 typedef BitField<bool, 0, 1> InlineField; 206 typedef BitField<unsigned, 1, 17> InputIndexField; 207 // Leaving some space in the bitset in case we ever decide to record 208 // the output index. 209 }; 210 211 //============================================================================ 212 //== Memory layout =========================================================== 213 //============================================================================ 214 // Saving space for big graphs is important. We use a memory layout trick to 215 // be able to map {Node} objects to {Use} objects and vice-versa in a 216 // space-efficient manner. 217 // 218 // {Use} links are laid out in memory directly before a {Node}, followed by 219 // direct pointers to input {Nodes}. 220 // 221 // inline case: 222 // |Use #N |Use #N-1|...|Use #1 |Use #0 |Node xxxx |I#0|I#1|...|I#N-1|I#N| 223 // ^ ^ ^ 224 // + Use + Node + Input 225 // 226 // Since every {Use} instance records its {input_index}, pointer arithmetic 227 // can compute the {Node}. 228 // 229 // out-of-line case: 230 // |Node xxxx | 231 // ^ + outline ------------------+ 232 // +----------------------------------------+ 233 // | | 234 // v | node 235 // |Use #N |Use #N-1|...|Use #1 |Use #0 |OOL xxxxx |I#0|I#1|...|I#N-1|I#N| 236 // ^ ^ 237 // + Use + Input 238 // 239 // Out-of-line storage of input lists is needed if appending an input to 240 // a node exceeds the maximum inline capacity. 241 242 Node(NodeId id, const Operator* op, int inline_count, int inline_capacity); 243 244 Node* const* GetInputPtrConst(int input_index) const { 245 return has_inline_inputs() ? &(inputs_.inline_[input_index]) 246 : &inputs_.outline_->inputs_[input_index]; 247 } 248 Node** GetInputPtr(int input_index) { 249 return has_inline_inputs() ? &(inputs_.inline_[input_index]) 250 : &inputs_.outline_->inputs_[input_index]; 251 } 252 Use* GetUsePtr(int input_index) { 253 Use* ptr = has_inline_inputs() ? reinterpret_cast<Use*>(this) 254 : reinterpret_cast<Use*>(inputs_.outline_); 255 return &ptr[-1 - input_index]; 256 } 257 258 void AppendUse(Use* use); 259 void RemoveUse(Use* use); 260 261 void* operator new(size_t, void* location) { return location; } 262 263 // Only NodeProperties should manipulate the op. 264 void set_op(const Operator* op) { op_ = op; } 265 266 // Only NodeProperties should manipulate the type. 267 Type* type() const { return type_; } 268 void set_type(Type* type) { type_ = type; } 269 270 // Only NodeMarkers should manipulate the marks on nodes. 271 Mark mark() const { return mark_; } 272 void set_mark(Mark mark) { mark_ = mark; } 273 274 inline bool has_inline_inputs() const { 275 return InlineCountField::decode(bit_field_) != kOutlineMarker; 276 } 277 278 void ClearInputs(int start, int count); 279 280 typedef BitField<NodeId, 0, 24> IdField; 281 typedef BitField<unsigned, 24, 4> InlineCountField; 282 typedef BitField<unsigned, 28, 4> InlineCapacityField; 283 static const int kOutlineMarker = InlineCountField::kMax; 284 static const int kMaxInlineCount = InlineCountField::kMax - 1; 285 static const int kMaxInlineCapacity = InlineCapacityField::kMax - 1; 286 287 const Operator* op_; 288 Type* type_; 289 Mark mark_; 290 uint32_t bit_field_; 291 Use* first_use_; 292 union { 293 // Inline storage for inputs or out-of-line storage. 294 Node* inline_[1]; 295 OutOfLineInputs* outline_; 296 } inputs_; 297 298 friend class Edge; 299 friend class NodeMarkerBase; 300 friend class NodeProperties; 301 302 DISALLOW_COPY_AND_ASSIGN(Node); 303}; 304 305 306std::ostream& operator<<(std::ostream& os, const Node& n); 307 308 309// Typedefs to shorten commonly used Node containers. 310typedef ZoneDeque<Node*> NodeDeque; 311typedef ZoneSet<Node*> NodeSet; 312typedef ZoneVector<Node*> NodeVector; 313typedef ZoneVector<NodeVector> NodeVectorVector; 314 315 316// Helper to extract parameters from Operator1<*> nodes. 317template <typename T> 318static inline const T& OpParameter(const Node* node) { 319 return OpParameter<T>(node->op()); 320} 321 322class Node::InputEdges final { 323 public: 324 typedef Edge value_type; 325 326 class iterator; 327 inline iterator begin() const; 328 inline iterator end() const; 329 330 bool empty() const { return count_ == 0; } 331 int count() const { return count_; } 332 333 inline value_type operator[](int index) const; 334 335 InputEdges(Node** input_root, Use* use_root, int count) 336 : input_root_(input_root), use_root_(use_root), count_(count) {} 337 338 private: 339 Node** input_root_; 340 Use* use_root_; 341 int count_; 342}; 343 344class V8_EXPORT_PRIVATE Node::Inputs final { 345 public: 346 typedef Node* value_type; 347 348 class const_iterator; 349 inline const_iterator begin() const; 350 inline const_iterator end() const; 351 352 bool empty() const { return count_ == 0; } 353 int count() const { return count_; } 354 355 inline value_type operator[](int index) const; 356 357 explicit Inputs(Node* const* input_root, int count) 358 : input_root_(input_root), count_(count) {} 359 360 private: 361 Node* const* input_root_; 362 int count_; 363}; 364 365// An encapsulation for information associated with a single use of node as a 366// input from another node, allowing access to both the defining node and 367// the node having the input. 368class Edge final { 369 public: 370 Node* from() const { return use_->from(); } 371 Node* to() const { return *input_ptr_; } 372 int index() const { 373 int const index = use_->input_index(); 374 DCHECK_LT(index, use_->from()->InputCount()); 375 return index; 376 } 377 378 bool operator==(const Edge& other) { return input_ptr_ == other.input_ptr_; } 379 bool operator!=(const Edge& other) { return !(*this == other); } 380 381 void UpdateTo(Node* new_to) { 382 Node* old_to = *input_ptr_; 383 if (old_to != new_to) { 384 if (old_to) old_to->RemoveUse(use_); 385 *input_ptr_ = new_to; 386 if (new_to) new_to->AppendUse(use_); 387 } 388 } 389 390 private: 391 friend class Node::UseEdges::iterator; 392 friend class Node::InputEdges; 393 friend class Node::InputEdges::iterator; 394 395 Edge(Node::Use* use, Node** input_ptr) : use_(use), input_ptr_(input_ptr) { 396 DCHECK_NOT_NULL(use); 397 DCHECK_NOT_NULL(input_ptr); 398 DCHECK_EQ(input_ptr, use->input_ptr()); 399 } 400 401 Node::Use* use_; 402 Node** input_ptr_; 403}; 404 405bool Node::IsDead() const { 406 Node::Inputs inputs = this->inputs(); 407 return inputs.count() > 0 && inputs[0] == nullptr; 408} 409 410Node::InputEdges Node::input_edges() { 411 int inline_count = InlineCountField::decode(bit_field_); 412 if (inline_count != kOutlineMarker) { 413 return InputEdges(inputs_.inline_, reinterpret_cast<Use*>(this) - 1, 414 inline_count); 415 } else { 416 return InputEdges(inputs_.outline_->inputs_, 417 reinterpret_cast<Use*>(inputs_.outline_) - 1, 418 inputs_.outline_->count_); 419 } 420} 421 422Node::Inputs Node::inputs() const { 423 int inline_count = InlineCountField::decode(bit_field_); 424 if (inline_count != kOutlineMarker) { 425 return Inputs(inputs_.inline_, inline_count); 426 } else { 427 return Inputs(inputs_.outline_->inputs_, inputs_.outline_->count_); 428 } 429} 430 431// A forward iterator to visit the edges for the input dependencies of a node. 432class Node::InputEdges::iterator final { 433 public: 434 typedef std::forward_iterator_tag iterator_category; 435 typedef std::ptrdiff_t difference_type; 436 typedef Edge value_type; 437 typedef Edge* pointer; 438 typedef Edge& reference; 439 440 iterator() : use_(nullptr), input_ptr_(nullptr) {} 441 iterator(const iterator& other) 442 : use_(other.use_), input_ptr_(other.input_ptr_) {} 443 444 Edge operator*() const { return Edge(use_, input_ptr_); } 445 bool operator==(const iterator& other) const { 446 return input_ptr_ == other.input_ptr_; 447 } 448 bool operator!=(const iterator& other) const { return !(*this == other); } 449 iterator& operator++() { 450 input_ptr_++; 451 use_--; 452 return *this; 453 } 454 iterator operator++(int); 455 iterator& operator+=(difference_type offset) { 456 input_ptr_ += offset; 457 use_ -= offset; 458 return *this; 459 } 460 iterator operator+(difference_type offset) const { 461 return iterator(use_ - offset, input_ptr_ + offset); 462 } 463 difference_type operator-(const iterator& other) const { 464 return input_ptr_ - other.input_ptr_; 465 } 466 467 private: 468 friend class Node; 469 470 explicit iterator(Use* use, Node** input_ptr) 471 : use_(use), input_ptr_(input_ptr) {} 472 473 Use* use_; 474 Node** input_ptr_; 475}; 476 477 478Node::InputEdges::iterator Node::InputEdges::begin() const { 479 return Node::InputEdges::iterator(use_root_, input_root_); 480} 481 482 483Node::InputEdges::iterator Node::InputEdges::end() const { 484 return Node::InputEdges::iterator(use_root_ - count_, input_root_ + count_); 485} 486 487Edge Node::InputEdges::operator[](int index) const { 488 return Edge(use_root_ + index, input_root_ + index); 489} 490 491// A forward iterator to visit the inputs of a node. 492class Node::Inputs::const_iterator final { 493 public: 494 typedef std::forward_iterator_tag iterator_category; 495 typedef std::ptrdiff_t difference_type; 496 typedef Node* value_type; 497 typedef const value_type* pointer; 498 typedef value_type& reference; 499 500 const_iterator(const const_iterator& other) : input_ptr_(other.input_ptr_) {} 501 502 Node* operator*() const { return *input_ptr_; } 503 bool operator==(const const_iterator& other) const { 504 return input_ptr_ == other.input_ptr_; 505 } 506 bool operator!=(const const_iterator& other) const { 507 return !(*this == other); 508 } 509 const_iterator& operator++() { 510 ++input_ptr_; 511 return *this; 512 } 513 const_iterator operator++(int); 514 const_iterator& operator+=(difference_type offset) { 515 input_ptr_ += offset; 516 return *this; 517 } 518 const_iterator operator+(difference_type offset) const { 519 return const_iterator(input_ptr_ + offset); 520 } 521 difference_type operator-(const const_iterator& other) const { 522 return input_ptr_ - other.input_ptr_; 523 } 524 525 private: 526 friend class Node::Inputs; 527 528 explicit const_iterator(Node* const* input_ptr) : input_ptr_(input_ptr) {} 529 530 Node* const* input_ptr_; 531}; 532 533 534Node::Inputs::const_iterator Node::Inputs::begin() const { 535 return const_iterator(input_root_); 536} 537 538 539Node::Inputs::const_iterator Node::Inputs::end() const { 540 return const_iterator(input_root_ + count_); 541} 542 543Node* Node::Inputs::operator[](int index) const { return input_root_[index]; } 544 545// A forward iterator to visit the uses edges of a node. 546class Node::UseEdges::iterator final { 547 public: 548 iterator(const iterator& other) 549 : current_(other.current_), next_(other.next_) {} 550 551 Edge operator*() const { return Edge(current_, current_->input_ptr()); } 552 bool operator==(const iterator& other) const { 553 return current_ == other.current_; 554 } 555 bool operator!=(const iterator& other) const { return !(*this == other); } 556 iterator& operator++() { 557 DCHECK_NOT_NULL(current_); 558 current_ = next_; 559 next_ = current_ ? current_->next : nullptr; 560 return *this; 561 } 562 iterator operator++(int); 563 564 private: 565 friend class Node::UseEdges; 566 567 iterator() : current_(nullptr), next_(nullptr) {} 568 explicit iterator(Node* node) 569 : current_(node->first_use_), 570 next_(current_ ? current_->next : nullptr) {} 571 572 Node::Use* current_; 573 Node::Use* next_; 574}; 575 576 577Node::UseEdges::iterator Node::UseEdges::begin() const { 578 return Node::UseEdges::iterator(this->node_); 579} 580 581 582Node::UseEdges::iterator Node::UseEdges::end() const { 583 return Node::UseEdges::iterator(); 584} 585 586 587// A forward iterator to visit the uses of a node. 588class Node::Uses::const_iterator final { 589 public: 590 typedef std::forward_iterator_tag iterator_category; 591 typedef int difference_type; 592 typedef Node* value_type; 593 typedef Node** pointer; 594 typedef Node*& reference; 595 596 const_iterator(const const_iterator& other) : current_(other.current_) {} 597 598 Node* operator*() const { return current_->from(); } 599 bool operator==(const const_iterator& other) const { 600 return other.current_ == current_; 601 } 602 bool operator!=(const const_iterator& other) const { 603 return other.current_ != current_; 604 } 605 const_iterator& operator++() { 606 DCHECK_NOT_NULL(current_); 607 current_ = current_->next; 608 return *this; 609 } 610 const_iterator operator++(int); 611 612 private: 613 friend class Node::Uses; 614 615 const_iterator() : current_(nullptr) {} 616 explicit const_iterator(Node* node) : current_(node->first_use_) {} 617 618 Node::Use* current_; 619}; 620 621 622Node::Uses::const_iterator Node::Uses::begin() const { 623 return const_iterator(this->node_); 624} 625 626 627Node::Uses::const_iterator Node::Uses::end() const { return const_iterator(); } 628 629} // namespace compiler 630} // namespace internal 631} // namespace v8 632 633#endif // V8_COMPILER_NODE_H_ 634