V8 API Reference, 7.2.502.16 (for Deno 0.2.4)
node.h
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  inline bool IsDead() const;
50  void Kill();
51 
52  const Operator* op() const { return op_; }
53 
54  IrOpcode::Value opcode() const {
55  DCHECK_GE(IrOpcode::kLast, op_->opcode());
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 #ifdef DEBUG
67  void Verify();
68 #define BOUNDS_CHECK(index) \
69  do { \
70  if (index < 0 || index >= InputCount()) { \
71  FATAL("Node #%d:%s->InputAt(%d) out of bounds", id(), op()->mnemonic(), \
72  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  void Print() const;
163 
164  private:
165  struct Use;
166  // Out of line storage for inputs when the number of inputs overflowed the
167  // capacity of the inline-allocated space.
168  struct OutOfLineInputs {
169  Node* node_;
170  int count_;
171  int capacity_;
172  Node* inputs_[1];
173 
174  static OutOfLineInputs* New(Zone* zone, int capacity);
175  void ExtractFrom(Use* use_ptr, Node** input_ptr, int count);
176  };
177 
178  // A link in the use chain for a node. Every input {i} to a node {n} has an
179  // associated {Use} which is linked into the use chain of the {i} node.
180  struct Use {
181  Use* next;
182  Use* prev;
183  uint32_t bit_field_;
184 
185  int input_index() const { return InputIndexField::decode(bit_field_); }
186  bool is_inline_use() const { return InlineField::decode(bit_field_); }
187  Node** input_ptr() {
188  int index = input_index();
189  Use* start = this + 1 + index;
190  Node** inputs = is_inline_use()
191  ? reinterpret_cast<Node*>(start)->inputs_.inline_
192  : reinterpret_cast<OutOfLineInputs*>(start)->inputs_;
193  return &inputs[index];
194  }
195 
196  Node* from() {
197  Use* start = this + 1 + input_index();
198  return is_inline_use() ? reinterpret_cast<Node*>(start)
199  : reinterpret_cast<OutOfLineInputs*>(start)->node_;
200  }
201 
202  typedef BitField<bool, 0, 1> InlineField;
203  typedef BitField<unsigned, 1, 17> InputIndexField;
204  // Leaving some space in the bitset in case we ever decide to record
205  // the output index.
206  };
207 
208  //============================================================================
209  //== Memory layout ===========================================================
210  //============================================================================
211  // Saving space for big graphs is important. We use a memory layout trick to
212  // be able to map {Node} objects to {Use} objects and vice-versa in a
213  // space-efficient manner.
214  //
215  // {Use} links are laid out in memory directly before a {Node}, followed by
216  // direct pointers to input {Nodes}.
217  //
218  // inline case:
219  // |Use #N |Use #N-1|...|Use #1 |Use #0 |Node xxxx |I#0|I#1|...|I#N-1|I#N|
220  // ^ ^ ^
221  // + Use + Node + Input
222  //
223  // Since every {Use} instance records its {input_index}, pointer arithmetic
224  // can compute the {Node}.
225  //
226  // out-of-line case:
227  // |Node xxxx |
228  // ^ + outline ------------------+
229  // +----------------------------------------+
230  // | |
231  // v | node
232  // |Use #N |Use #N-1|...|Use #1 |Use #0 |OOL xxxxx |I#0|I#1|...|I#N-1|I#N|
233  // ^ ^
234  // + Use + Input
235  //
236  // Out-of-line storage of input lists is needed if appending an input to
237  // a node exceeds the maximum inline capacity.
238 
239  Node(NodeId id, const Operator* op, int inline_count, int inline_capacity);
240 
241  Node* const* GetInputPtrConst(int input_index) const {
242  return has_inline_inputs() ? &(inputs_.inline_[input_index])
243  : &inputs_.outline_->inputs_[input_index];
244  }
245  Node** GetInputPtr(int input_index) {
246  return has_inline_inputs() ? &(inputs_.inline_[input_index])
247  : &inputs_.outline_->inputs_[input_index];
248  }
249  Use* GetUsePtr(int input_index) {
250  Use* ptr = has_inline_inputs() ? reinterpret_cast<Use*>(this)
251  : reinterpret_cast<Use*>(inputs_.outline_);
252  return &ptr[-1 - input_index];
253  }
254 
255  void AppendUse(Use* use);
256  void RemoveUse(Use* use);
257 
258  void* operator new(size_t, void* location) { return location; }
259 
260  // Only NodeProperties should manipulate the op.
261  void set_op(const Operator* op) { op_ = op; }
262 
263  // Only NodeProperties should manipulate the type.
264  Type type() const { return type_; }
265  void set_type(Type type) { type_ = type; }
266 
267  // Only NodeMarkers should manipulate the marks on nodes.
268  Mark mark() const { return mark_; }
269  void set_mark(Mark mark) { mark_ = mark; }
270 
271  inline bool has_inline_inputs() const {
272  return InlineCountField::decode(bit_field_) != kOutlineMarker;
273  }
274 
275  void ClearInputs(int start, int count);
276 
277  typedef BitField<NodeId, 0, 24> IdField;
278  typedef BitField<unsigned, 24, 4> InlineCountField;
279  typedef BitField<unsigned, 28, 4> InlineCapacityField;
280  static const int kOutlineMarker = InlineCountField::kMax;
281  static const int kMaxInlineCount = InlineCountField::kMax - 1;
282  static const int kMaxInlineCapacity = InlineCapacityField::kMax - 1;
283 
284  const Operator* op_;
285  Type type_;
286  Mark mark_;
287  uint32_t bit_field_;
288  Use* first_use_;
289  union {
290  // Inline storage for inputs or out-of-line storage.
291  Node* inline_[1];
292  OutOfLineInputs* outline_;
293  } inputs_;
294 
295  friend class Edge;
296  friend class NodeMarkerBase;
297  friend class NodeProperties;
298 
299  DISALLOW_COPY_AND_ASSIGN(Node);
300 };
301 
302 
303 std::ostream& operator<<(std::ostream& os, const Node& n);
304 
305 
306 // Typedefs to shorten commonly used Node containers.
307 typedef ZoneDeque<Node*> NodeDeque;
308 typedef ZoneSet<Node*> NodeSet;
309 typedef ZoneVector<Node*> NodeVector;
310 typedef ZoneVector<NodeVector> NodeVectorVector;
311 
312 
313 class Node::InputEdges final {
314  public:
315  typedef Edge value_type;
316 
317  class iterator;
318  inline iterator begin() const;
319  inline iterator end() const;
320 
321  bool empty() const { return count_ == 0; }
322  int count() const { return count_; }
323 
324  inline value_type operator[](int index) const;
325 
326  InputEdges(Node** input_root, Use* use_root, int count)
327  : input_root_(input_root), use_root_(use_root), count_(count) {}
328 
329  private:
330  Node** input_root_;
331  Use* use_root_;
332  int count_;
333 };
334 
335 class V8_EXPORT_PRIVATE Node::Inputs final {
336  public:
337  typedef Node* value_type;
338 
339  class const_iterator;
340  inline const_iterator begin() const;
341  inline const_iterator end() const;
342 
343  bool empty() const { return count_ == 0; }
344  int count() const { return count_; }
345 
346  inline value_type operator[](int index) const;
347 
348  explicit Inputs(Node* const* input_root, int count)
349  : input_root_(input_root), count_(count) {}
350 
351  private:
352  Node* const* input_root_;
353  int count_;
354 };
355 
356 // An encapsulation for information associated with a single use of node as a
357 // input from another node, allowing access to both the defining node and
358 // the node having the input.
359 class Edge final {
360  public:
361  Node* from() const { return use_->from(); }
362  Node* to() const { return *input_ptr_; }
363  int index() const {
364  int const index = use_->input_index();
365  DCHECK_LT(index, use_->from()->InputCount());
366  return index;
367  }
368 
369  bool operator==(const Edge& other) { return input_ptr_ == other.input_ptr_; }
370  bool operator!=(const Edge& other) { return !(*this == other); }
371 
372  void UpdateTo(Node* new_to) {
373  Node* old_to = *input_ptr_;
374  if (old_to != new_to) {
375  if (old_to) old_to->RemoveUse(use_);
376  *input_ptr_ = new_to;
377  if (new_to) new_to->AppendUse(use_);
378  }
379  }
380 
381  private:
382  friend class Node::UseEdges::iterator;
383  friend class Node::InputEdges;
384  friend class Node::InputEdges::iterator;
385 
386  Edge(Node::Use* use, Node** input_ptr) : use_(use), input_ptr_(input_ptr) {
387  DCHECK_NOT_NULL(use);
388  DCHECK_NOT_NULL(input_ptr);
389  DCHECK_EQ(input_ptr, use->input_ptr());
390  }
391 
392  Node::Use* use_;
393  Node** input_ptr_;
394 };
395 
396 bool Node::IsDead() const {
397  Node::Inputs inputs = this->inputs();
398  return inputs.count() > 0 && inputs[0] == nullptr;
399 }
400 
401 Node::InputEdges Node::input_edges() {
402  int inline_count = InlineCountField::decode(bit_field_);
403  if (inline_count != kOutlineMarker) {
404  return InputEdges(inputs_.inline_, reinterpret_cast<Use*>(this) - 1,
405  inline_count);
406  } else {
407  return InputEdges(inputs_.outline_->inputs_,
408  reinterpret_cast<Use*>(inputs_.outline_) - 1,
409  inputs_.outline_->count_);
410  }
411 }
412 
413 Node::Inputs Node::inputs() const {
414  int inline_count = InlineCountField::decode(bit_field_);
415  if (inline_count != kOutlineMarker) {
416  return Inputs(inputs_.inline_, inline_count);
417  } else {
418  return Inputs(inputs_.outline_->inputs_, inputs_.outline_->count_);
419  }
420 }
421 
422 // A forward iterator to visit the edges for the input dependencies of a node.
423 class Node::InputEdges::iterator final {
424  public:
425  typedef std::forward_iterator_tag iterator_category;
426  typedef std::ptrdiff_t difference_type;
427  typedef Edge value_type;
428  typedef Edge* pointer;
429  typedef Edge& reference;
430 
431  iterator() : use_(nullptr), input_ptr_(nullptr) {}
432  iterator(const iterator& other) = default;
433 
434  Edge operator*() const { return Edge(use_, input_ptr_); }
435  bool operator==(const iterator& other) const {
436  return input_ptr_ == other.input_ptr_;
437  }
438  bool operator!=(const iterator& other) const { return !(*this == other); }
439  iterator& operator++() {
440  input_ptr_++;
441  use_--;
442  return *this;
443  }
444  iterator operator++(int);
445  iterator& operator+=(difference_type offset) {
446  input_ptr_ += offset;
447  use_ -= offset;
448  return *this;
449  }
450  iterator operator+(difference_type offset) const {
451  return iterator(use_ - offset, input_ptr_ + offset);
452  }
453  difference_type operator-(const iterator& other) const {
454  return input_ptr_ - other.input_ptr_;
455  }
456 
457  private:
458  friend class Node;
459 
460  explicit iterator(Use* use, Node** input_ptr)
461  : use_(use), input_ptr_(input_ptr) {}
462 
463  Use* use_;
464  Node** input_ptr_;
465 };
466 
467 
468 Node::InputEdges::iterator Node::InputEdges::begin() const {
469  return Node::InputEdges::iterator(use_root_, input_root_);
470 }
471 
472 
473 Node::InputEdges::iterator Node::InputEdges::end() const {
474  return Node::InputEdges::iterator(use_root_ - count_, input_root_ + count_);
475 }
476 
477 Edge Node::InputEdges::operator[](int index) const {
478  return Edge(use_root_ + index, input_root_ + index);
479 }
480 
481 // A forward iterator to visit the inputs of a node.
482 class Node::Inputs::const_iterator final {
483  public:
484  typedef std::forward_iterator_tag iterator_category;
485  typedef std::ptrdiff_t difference_type;
486  typedef Node* value_type;
487  typedef const value_type* pointer;
488  typedef value_type& reference;
489 
490  const_iterator(const const_iterator& other) = default;
491 
492  Node* operator*() const { return *input_ptr_; }
493  bool operator==(const const_iterator& other) const {
494  return input_ptr_ == other.input_ptr_;
495  }
496  bool operator!=(const const_iterator& other) const {
497  return !(*this == other);
498  }
499  const_iterator& operator++() {
500  ++input_ptr_;
501  return *this;
502  }
503  const_iterator operator++(int);
504  const_iterator& operator+=(difference_type offset) {
505  input_ptr_ += offset;
506  return *this;
507  }
508  const_iterator operator+(difference_type offset) const {
509  return const_iterator(input_ptr_ + offset);
510  }
511  difference_type operator-(const const_iterator& other) const {
512  return input_ptr_ - other.input_ptr_;
513  }
514 
515  private:
516  friend class Node::Inputs;
517 
518  explicit const_iterator(Node* const* input_ptr) : input_ptr_(input_ptr) {}
519 
520  Node* const* input_ptr_;
521 };
522 
523 
524 Node::Inputs::const_iterator Node::Inputs::begin() const {
525  return const_iterator(input_root_);
526 }
527 
528 
529 Node::Inputs::const_iterator Node::Inputs::end() const {
530  return const_iterator(input_root_ + count_);
531 }
532 
533 Node* Node::Inputs::operator[](int index) const { return input_root_[index]; }
534 
535 // A forward iterator to visit the uses edges of a node.
536 class Node::UseEdges::iterator final {
537  public:
538  iterator(const iterator& other) = default;
539 
540  Edge operator*() const { return Edge(current_, current_->input_ptr()); }
541  bool operator==(const iterator& other) const {
542  return current_ == other.current_;
543  }
544  bool operator!=(const iterator& other) const { return !(*this == other); }
545  iterator& operator++() {
546  DCHECK_NOT_NULL(current_);
547  current_ = next_;
548  next_ = current_ ? current_->next : nullptr;
549  return *this;
550  }
551  iterator operator++(int);
552 
553  private:
554  friend class Node::UseEdges;
555 
556  iterator() : current_(nullptr), next_(nullptr) {}
557  explicit iterator(Node* node)
558  : current_(node->first_use_),
559  next_(current_ ? current_->next : nullptr) {}
560 
561  Node::Use* current_;
562  Node::Use* next_;
563 };
564 
565 
566 Node::UseEdges::iterator Node::UseEdges::begin() const {
567  return Node::UseEdges::iterator(this->node_);
568 }
569 
570 
571 Node::UseEdges::iterator Node::UseEdges::end() const {
572  return Node::UseEdges::iterator();
573 }
574 
575 
576 // A forward iterator to visit the uses of a node.
577 class Node::Uses::const_iterator final {
578  public:
579  typedef std::forward_iterator_tag iterator_category;
580  typedef int difference_type;
581  typedef Node* value_type;
582  typedef Node** pointer;
583  typedef Node*& reference;
584 
585  Node* operator*() const { return current_->from(); }
586  bool operator==(const const_iterator& other) const {
587  return other.current_ == current_;
588  }
589  bool operator!=(const const_iterator& other) const {
590  return other.current_ != current_;
591  }
592  const_iterator& operator++() {
593  DCHECK_NOT_NULL(current_);
594  // Checking no use gets mutated while iterating through them, a potential
595  // very tricky cause of bug.
596  current_ = current_->next;
597 #ifdef DEBUG
598  DCHECK_EQ(current_, next_);
599  next_ = current_ ? current_->next : nullptr;
600 #endif
601  return *this;
602  }
603  const_iterator operator++(int);
604 
605  private:
606  friend class Node::Uses;
607 
608  const_iterator() : current_(nullptr) {}
609  explicit const_iterator(Node* node)
610  : current_(node->first_use_)
611 #ifdef DEBUG
612  ,
613  next_(current_ ? current_->next : nullptr)
614 #endif
615  {
616  }
617 
618  Node::Use* current_;
619 #ifdef DEBUG
620  Node::Use* next_;
621 #endif
622 };
623 
624 
625 Node::Uses::const_iterator Node::Uses::begin() const {
626  return const_iterator(this->node_);
627 }
628 
629 
630 Node::Uses::const_iterator Node::Uses::end() const { return const_iterator(); }
631 
632 } // namespace compiler
633 } // namespace internal
634 } // namespace v8
635 
636 #endif // V8_COMPILER_NODE_H_
Definition: libplatform.h:13