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 14 namespace v8 { 15 namespace internal { 16 namespace compiler { 17 18 // Forward declarations. 19 class Edge; 20 class 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. 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 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. 43 class 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 bool IsDead() const { return InputCount() > 0 && !InputAt(0); } 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 final { 113 public: 114 typedef Edge value_type; 115 116 class iterator; 117 inline iterator begin() const; 118 inline iterator end() const; 119 120 bool empty() const; 121 122 explicit InputEdges(Node* node) : node_(node) {} 123 124 private: 125 Node* node_; 126 }; 127 128 InputEdges input_edges() { return InputEdges(this); } 129 130 class V8_EXPORT_PRIVATE Inputs final { 131 public: 132 typedef Node* value_type; 133 134 class const_iterator; 135 inline const_iterator begin() const; 136 inline const_iterator end() const; 137 138 bool empty() const; 139 140 explicit Inputs(Node* node) : node_(node) {} 141 142 private: 143 Node* node_; 144 }; 145 146 Inputs inputs() { return Inputs(this); } 147 148 class UseEdges final { 149 public: 150 typedef Edge value_type; 151 152 class iterator; 153 inline iterator begin() const; 154 inline iterator end() const; 155 156 bool empty() const; 157 158 explicit UseEdges(Node* node) : node_(node) {} 159 160 private: 161 Node* node_; 162 }; 163 164 UseEdges use_edges() { return UseEdges(this); } 165 166 class V8_EXPORT_PRIVATE Uses final { 167 public: 168 typedef Node* value_type; 169 170 class const_iterator; 171 inline const_iterator begin() const; 172 inline const_iterator end() const; 173 174 bool empty() const; 175 176 explicit Uses(Node* node) : node_(node) {} 177 178 private: 179 Node* node_; 180 }; 181 182 Uses uses() { return Uses(this); } 183 184 // Returns true if {owner} is the user of {this} node. 185 bool OwnedBy(Node* owner) const { 186 return first_use_ && first_use_->from() == owner && !first_use_->next; 187 } 188 189 // Returns true if {owner1} and {owner2} are the only users of {this} node. 190 bool OwnedBy(Node const* owner1, Node const* owner2) const; 191 void Print() const; 192 193 private: 194 struct Use; 195 // Out of line storage for inputs when the number of inputs overflowed the 196 // capacity of the inline-allocated space. 197 struct OutOfLineInputs { 198 Node* node_; 199 int count_; 200 int capacity_; 201 Node* inputs_[1]; 202 203 static OutOfLineInputs* New(Zone* zone, int capacity); 204 void ExtractFrom(Use* use_ptr, Node** input_ptr, int count); 205 }; 206 207 // A link in the use chain for a node. Every input {i} to a node {n} has an 208 // associated {Use} which is linked into the use chain of the {i} node. 209 struct Use { 210 Use* next; 211 Use* prev; 212 uint32_t bit_field_; 213 214 int input_index() const { return InputIndexField::decode(bit_field_); } 215 bool is_inline_use() const { return InlineField::decode(bit_field_); } 216 Node** input_ptr() { 217 int index = input_index(); 218 Use* start = this + 1 + index; 219 Node** inputs = is_inline_use() 220 ? reinterpret_cast<Node*>(start)->inputs_.inline_ 221 : reinterpret_cast<OutOfLineInputs*>(start)->inputs_; 222 return &inputs[index]; 223 } 224 225 Node* from() { 226 Use* start = this + 1 + input_index(); 227 return is_inline_use() ? reinterpret_cast<Node*>(start) 228 : reinterpret_cast<OutOfLineInputs*>(start)->node_; 229 } 230 231 typedef BitField<bool, 0, 1> InlineField; 232 typedef BitField<unsigned, 1, 17> InputIndexField; 233 // Leaving some space in the bitset in case we ever decide to record 234 // the output index. 235 }; 236 237 //============================================================================ 238 //== Memory layout =========================================================== 239 //============================================================================ 240 // Saving space for big graphs is important. We use a memory layout trick to 241 // be able to map {Node} objects to {Use} objects and vice-versa in a 242 // space-efficient manner. 243 // 244 // {Use} links are laid out in memory directly before a {Node}, followed by 245 // direct pointers to input {Nodes}. 246 // 247 // inline case: 248 // |Use #N |Use #N-1|...|Use #1 |Use #0 |Node xxxx |I#0|I#1|...|I#N-1|I#N| 249 // ^ ^ ^ 250 // + Use + Node + Input 251 // 252 // Since every {Use} instance records its {input_index}, pointer arithmetic 253 // can compute the {Node}. 254 // 255 // out-of-line case: 256 // |Node xxxx | 257 // ^ + outline ------------------+ 258 // +----------------------------------------+ 259 // | | 260 // v | node 261 // |Use #N |Use #N-1|...|Use #1 |Use #0 |OOL xxxxx |I#0|I#1|...|I#N-1|I#N| 262 // ^ ^ 263 // + Use + Input 264 // 265 // Out-of-line storage of input lists is needed if appending an input to 266 // a node exceeds the maximum inline capacity. 267 268 Node(NodeId id, const Operator* op, int inline_count, int inline_capacity); 269 270 Node* const* GetInputPtrConst(int input_index) const { 271 return has_inline_inputs() ? &(inputs_.inline_[input_index]) 272 : &inputs_.outline_->inputs_[input_index]; 273 } 274 Node** GetInputPtr(int input_index) { 275 return has_inline_inputs() ? &(inputs_.inline_[input_index]) 276 : &inputs_.outline_->inputs_[input_index]; 277 } 278 Use* GetUsePtr(int input_index) { 279 Use* ptr = has_inline_inputs() ? reinterpret_cast<Use*>(this) 280 : reinterpret_cast<Use*>(inputs_.outline_); 281 return &ptr[-1 - input_index]; 282 } 283 284 void AppendUse(Use* use); 285 void RemoveUse(Use* use); 286 287 void* operator new(size_t, void* location) { return location; } 288 289 // Only NodeProperties should manipulate the op. 290 void set_op(const Operator* op) { op_ = op; } 291 292 // Only NodeProperties should manipulate the type. 293 Type* type() const { return type_; } 294 void set_type(Type* type) { type_ = type; } 295 296 // Only NodeMarkers should manipulate the marks on nodes. 297 Mark mark() { return mark_; } 298 void set_mark(Mark mark) { mark_ = mark; } 299 300 inline bool has_inline_inputs() const { 301 return InlineCountField::decode(bit_field_) != kOutlineMarker; 302 } 303 304 void ClearInputs(int start, int count); 305 306 typedef BitField<NodeId, 0, 24> IdField; 307 typedef BitField<unsigned, 24, 4> InlineCountField; 308 typedef BitField<unsigned, 28, 4> InlineCapacityField; 309 static const int kOutlineMarker = InlineCountField::kMax; 310 static const int kMaxInlineCount = InlineCountField::kMax - 1; 311 static const int kMaxInlineCapacity = InlineCapacityField::kMax - 1; 312 313 const Operator* op_; 314 Type* type_; 315 Mark mark_; 316 uint32_t bit_field_; 317 Use* first_use_; 318 union { 319 // Inline storage for inputs or out-of-line storage. 320 Node* inline_[1]; 321 OutOfLineInputs* outline_; 322 } inputs_; 323 324 friend class Edge; 325 friend class NodeMarkerBase; 326 friend class NodeProperties; 327 328 DISALLOW_COPY_AND_ASSIGN(Node); 329 }; 330 331 332 std::ostream& operator<<(std::ostream& os, const Node& n); 333 334 335 // Typedefs to shorten commonly used Node containers. 336 typedef ZoneDeque<Node*> NodeDeque; 337 typedef ZoneSet<Node*> NodeSet; 338 typedef ZoneVector<Node*> NodeVector; 339 typedef ZoneVector<NodeVector> NodeVectorVector; 340 341 342 // Helper to extract parameters from Operator1<*> nodes. 343 template <typename T> 344 static inline const T& OpParameter(const Node* node) { 345 return OpParameter<T>(node->op()); 346 } 347 348 349 // An encapsulation for information associated with a single use of node as a 350 // input from another node, allowing access to both the defining node and 351 // the node having the input. 352 class Edge final { 353 public: 354 Node* from() const { return use_->from(); } 355 Node* to() const { return *input_ptr_; } 356 int index() const { 357 int const index = use_->input_index(); 358 DCHECK_LT(index, use_->from()->InputCount()); 359 return index; 360 } 361 362 bool operator==(const Edge& other) { return input_ptr_ == other.input_ptr_; } 363 bool operator!=(const Edge& other) { return !(*this == other); } 364 365 void UpdateTo(Node* new_to) { 366 Node* old_to = *input_ptr_; 367 if (old_to != new_to) { 368 if (old_to) old_to->RemoveUse(use_); 369 *input_ptr_ = new_to; 370 if (new_to) new_to->AppendUse(use_); 371 } 372 } 373 374 private: 375 friend class Node::UseEdges::iterator; 376 friend class Node::InputEdges::iterator; 377 378 Edge(Node::Use* use, Node** input_ptr) : use_(use), input_ptr_(input_ptr) { 379 DCHECK_NOT_NULL(use); 380 DCHECK_NOT_NULL(input_ptr); 381 DCHECK_EQ(input_ptr, use->input_ptr()); 382 } 383 384 Node::Use* use_; 385 Node** input_ptr_; 386 }; 387 388 389 // A forward iterator to visit the edges for the input dependencies of a node. 390 class Node::InputEdges::iterator final { 391 public: 392 typedef std::forward_iterator_tag iterator_category; 393 typedef int difference_type; 394 typedef Edge value_type; 395 typedef Edge* pointer; 396 typedef Edge& reference; 397 398 iterator() : use_(nullptr), input_ptr_(nullptr) {} 399 iterator(const iterator& other) 400 : use_(other.use_), input_ptr_(other.input_ptr_) {} 401 402 Edge operator*() const { return Edge(use_, input_ptr_); } 403 bool operator==(const iterator& other) const { 404 return input_ptr_ == other.input_ptr_; 405 } 406 bool operator!=(const iterator& other) const { return !(*this == other); } 407 iterator& operator++() { 408 input_ptr_++; 409 use_--; 410 return *this; 411 } 412 iterator operator++(int); 413 414 private: 415 friend class Node; 416 417 explicit iterator(Node* from, int index = 0) 418 : use_(from->GetUsePtr(index)), input_ptr_(from->GetInputPtr(index)) {} 419 420 Use* use_; 421 Node** input_ptr_; 422 }; 423 424 425 Node::InputEdges::iterator Node::InputEdges::begin() const { 426 return Node::InputEdges::iterator(this->node_, 0); 427 } 428 429 430 Node::InputEdges::iterator Node::InputEdges::end() const { 431 return Node::InputEdges::iterator(this->node_, this->node_->InputCount()); 432 } 433 434 435 // A forward iterator to visit the inputs of a node. 436 class Node::Inputs::const_iterator final { 437 public: 438 typedef std::forward_iterator_tag iterator_category; 439 typedef int difference_type; 440 typedef Node* value_type; 441 typedef Node** pointer; 442 typedef Node*& reference; 443 444 const_iterator(const const_iterator& other) : iter_(other.iter_) {} 445 446 Node* operator*() const { return (*iter_).to(); } 447 bool operator==(const const_iterator& other) const { 448 return iter_ == other.iter_; 449 } 450 bool operator!=(const const_iterator& other) const { 451 return !(*this == other); 452 } 453 const_iterator& operator++() { 454 ++iter_; 455 return *this; 456 } 457 const_iterator operator++(int); 458 459 private: 460 friend class Node::Inputs; 461 462 const_iterator(Node* node, int index) : iter_(node, index) {} 463 464 Node::InputEdges::iterator iter_; 465 }; 466 467 468 Node::Inputs::const_iterator Node::Inputs::begin() const { 469 return const_iterator(this->node_, 0); 470 } 471 472 473 Node::Inputs::const_iterator Node::Inputs::end() const { 474 return const_iterator(this->node_, this->node_->InputCount()); 475 } 476 477 478 // A forward iterator to visit the uses edges of a node. 479 class Node::UseEdges::iterator final { 480 public: 481 iterator(const iterator& other) 482 : current_(other.current_), next_(other.next_) {} 483 484 Edge operator*() const { return Edge(current_, current_->input_ptr()); } 485 bool operator==(const iterator& other) const { 486 return current_ == other.current_; 487 } 488 bool operator!=(const iterator& other) const { return !(*this == other); } 489 iterator& operator++() { 490 DCHECK_NOT_NULL(current_); 491 current_ = next_; 492 next_ = current_ ? current_->next : nullptr; 493 return *this; 494 } 495 iterator operator++(int); 496 497 private: 498 friend class Node::UseEdges; 499 500 iterator() : current_(nullptr), next_(nullptr) {} 501 explicit iterator(Node* node) 502 : current_(node->first_use_), 503 next_(current_ ? current_->next : nullptr) {} 504 505 Node::Use* current_; 506 Node::Use* next_; 507 }; 508 509 510 Node::UseEdges::iterator Node::UseEdges::begin() const { 511 return Node::UseEdges::iterator(this->node_); 512 } 513 514 515 Node::UseEdges::iterator Node::UseEdges::end() const { 516 return Node::UseEdges::iterator(); 517 } 518 519 520 // A forward iterator to visit the uses of a node. 521 class Node::Uses::const_iterator final { 522 public: 523 typedef std::forward_iterator_tag iterator_category; 524 typedef int difference_type; 525 typedef Node* value_type; 526 typedef Node** pointer; 527 typedef Node*& reference; 528 529 const_iterator(const const_iterator& other) : current_(other.current_) {} 530 531 Node* operator*() const { return current_->from(); } 532 bool operator==(const const_iterator& other) const { 533 return other.current_ == current_; 534 } 535 bool operator!=(const const_iterator& other) const { 536 return other.current_ != current_; 537 } 538 const_iterator& operator++() { 539 DCHECK_NOT_NULL(current_); 540 current_ = current_->next; 541 return *this; 542 } 543 const_iterator operator++(int); 544 545 private: 546 friend class Node::Uses; 547 548 const_iterator() : current_(nullptr) {} 549 explicit const_iterator(Node* node) : current_(node->first_use_) {} 550 551 Node::Use* current_; 552 }; 553 554 555 Node::Uses::const_iterator Node::Uses::begin() const { 556 return const_iterator(this->node_); 557 } 558 559 560 Node::Uses::const_iterator Node::Uses::end() const { return const_iterator(); } 561 562 } // namespace compiler 563 } // namespace internal 564 } // namespace v8 565 566 #endif // V8_COMPILER_NODE_H_ 567