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
op()52 const Operator* op() const { return op_; }
53
opcode()54 IrOpcode::Value opcode() const {
55 DCHECK_GE(IrOpcode::kLast, op_->opcode());
56 return static_cast<IrOpcode::Value>(op_->opcode());
57 }
58
id()59 NodeId id() const { return IdField::decode(bit_field_); }
60
InputCount()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.
Verify()77 inline void Verify() {}
78 #define BOUNDS_CHECK(index) \
79 do { \
80 } while (false)
81 #endif
82
InputAt(int index)83 Node* InputAt(int index) const {
84 BOUNDS_CHECK(index);
85 return *GetInputPtrConst(index);
86 }
87
ReplaceInput(int index,Node * new_to)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
UseEdges(Node * node)128 explicit UseEdges(Node* node) : node_(node) {}
129
130 private:
131 Node* node_;
132 };
133
use_edges()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
Uses(Node * node)146 explicit Uses(Node* node) : node_(node) {}
147
148 private:
149 Node* node_;
150 };
151
uses()152 Uses uses() { return Uses(this); }
153
154 // Returns true if {owner} is the user of {this} node.
OwnedBy(Node * owner)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
input_indexUse185 int input_index() const { return InputIndexField::decode(bit_field_); }
is_inline_useUse186 bool is_inline_use() const { return InlineField::decode(bit_field_); }
input_ptrUse187 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
fromUse196 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
GetInputPtrConst(int input_index)241 Node* const* GetInputPtrConst(int input_index) const {
242 return has_inline_inputs() ? &(inputs_.inline_[input_index])
243 : &inputs_.outline_->inputs_[input_index];
244 }
GetInputPtr(int input_index)245 Node** GetInputPtr(int input_index) {
246 return has_inline_inputs() ? &(inputs_.inline_[input_index])
247 : &inputs_.outline_->inputs_[input_index];
248 }
GetUsePtr(int input_index)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
new(size_t,void * location)258 void* operator new(size_t, void* location) { return location; }
259
260 // Only NodeProperties should manipulate the op.
set_op(const Operator * op)261 void set_op(const Operator* op) { op_ = op; }
262
263 // Only NodeProperties should manipulate the type.
type()264 Type type() const { return type_; }
set_type(Type type)265 void set_type(Type type) { type_ = type; }
266
267 // Only NodeMarkers should manipulate the marks on nodes.
mark()268 Mark mark() const { return mark_; }
set_mark(Mark mark)269 void set_mark(Mark mark) { mark_ = mark; }
270
has_inline_inputs()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
empty()321 bool empty() const { return count_ == 0; }
count()322 int count() const { return count_; }
323
324 inline value_type operator[](int index) const;
325
InputEdges(Node ** input_root,Use * use_root,int count)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
empty()343 bool empty() const { return count_ == 0; }
count()344 int count() const { return count_; }
345
346 inline value_type operator[](int index) const;
347
Inputs(Node * const * input_root,int count)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:
from()361 Node* from() const { return use_->from(); }
to()362 Node* to() const { return *input_ptr_; }
index()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
UpdateTo(Node * new_to)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
Edge(Node::Use * use,Node ** input_ptr)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
IsDead()396 bool Node::IsDead() const {
397 Node::Inputs inputs = this->inputs();
398 return inputs.count() > 0 && inputs[0] == nullptr;
399 }
400
input_edges()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
inputs()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
iterator()431 iterator() : use_(nullptr), input_ptr_(nullptr) {}
iterator(const iterator & other)432 iterator(const iterator& other)
433 : use_(other.use_), input_ptr_(other.input_ptr_) {}
434
435 Edge operator*() const { return Edge(use_, input_ptr_); }
436 bool operator==(const iterator& other) const {
437 return input_ptr_ == other.input_ptr_;
438 }
439 bool operator!=(const iterator& other) const { return !(*this == other); }
440 iterator& operator++() {
441 input_ptr_++;
442 use_--;
443 return *this;
444 }
445 iterator operator++(int);
446 iterator& operator+=(difference_type offset) {
447 input_ptr_ += offset;
448 use_ -= offset;
449 return *this;
450 }
451 iterator operator+(difference_type offset) const {
452 return iterator(use_ - offset, input_ptr_ + offset);
453 }
454 difference_type operator-(const iterator& other) const {
455 return input_ptr_ - other.input_ptr_;
456 }
457
458 private:
459 friend class Node;
460
iterator(Use * use,Node ** input_ptr)461 explicit iterator(Use* use, Node** input_ptr)
462 : use_(use), input_ptr_(input_ptr) {}
463
464 Use* use_;
465 Node** input_ptr_;
466 };
467
468
begin()469 Node::InputEdges::iterator Node::InputEdges::begin() const {
470 return Node::InputEdges::iterator(use_root_, input_root_);
471 }
472
473
end()474 Node::InputEdges::iterator Node::InputEdges::end() const {
475 return Node::InputEdges::iterator(use_root_ - count_, input_root_ + count_);
476 }
477
478 Edge Node::InputEdges::operator[](int index) const {
479 return Edge(use_root_ + index, input_root_ + index);
480 }
481
482 // A forward iterator to visit the inputs of a node.
483 class Node::Inputs::const_iterator final {
484 public:
485 typedef std::forward_iterator_tag iterator_category;
486 typedef std::ptrdiff_t difference_type;
487 typedef Node* value_type;
488 typedef const value_type* pointer;
489 typedef value_type& reference;
490
const_iterator(const const_iterator & other)491 const_iterator(const const_iterator& other) : input_ptr_(other.input_ptr_) {}
492
493 Node* operator*() const { return *input_ptr_; }
494 bool operator==(const const_iterator& other) const {
495 return input_ptr_ == other.input_ptr_;
496 }
497 bool operator!=(const const_iterator& other) const {
498 return !(*this == other);
499 }
500 const_iterator& operator++() {
501 ++input_ptr_;
502 return *this;
503 }
504 const_iterator operator++(int);
505 const_iterator& operator+=(difference_type offset) {
506 input_ptr_ += offset;
507 return *this;
508 }
509 const_iterator operator+(difference_type offset) const {
510 return const_iterator(input_ptr_ + offset);
511 }
512 difference_type operator-(const const_iterator& other) const {
513 return input_ptr_ - other.input_ptr_;
514 }
515
516 private:
517 friend class Node::Inputs;
518
const_iterator(Node * const * input_ptr)519 explicit const_iterator(Node* const* input_ptr) : input_ptr_(input_ptr) {}
520
521 Node* const* input_ptr_;
522 };
523
524
begin()525 Node::Inputs::const_iterator Node::Inputs::begin() const {
526 return const_iterator(input_root_);
527 }
528
529
end()530 Node::Inputs::const_iterator Node::Inputs::end() const {
531 return const_iterator(input_root_ + count_);
532 }
533
534 Node* Node::Inputs::operator[](int index) const { return input_root_[index]; }
535
536 // A forward iterator to visit the uses edges of a node.
537 class Node::UseEdges::iterator final {
538 public:
iterator(const iterator & other)539 iterator(const iterator& other)
540 : current_(other.current_), next_(other.next_) {}
541
542 Edge operator*() const { return Edge(current_, current_->input_ptr()); }
543 bool operator==(const iterator& other) const {
544 return current_ == other.current_;
545 }
546 bool operator!=(const iterator& other) const { return !(*this == other); }
547 iterator& operator++() {
548 DCHECK_NOT_NULL(current_);
549 current_ = next_;
550 next_ = current_ ? current_->next : nullptr;
551 return *this;
552 }
553 iterator operator++(int);
554
555 private:
556 friend class Node::UseEdges;
557
iterator()558 iterator() : current_(nullptr), next_(nullptr) {}
iterator(Node * node)559 explicit iterator(Node* node)
560 : current_(node->first_use_),
561 next_(current_ ? current_->next : nullptr) {}
562
563 Node::Use* current_;
564 Node::Use* next_;
565 };
566
567
begin()568 Node::UseEdges::iterator Node::UseEdges::begin() const {
569 return Node::UseEdges::iterator(this->node_);
570 }
571
572
end()573 Node::UseEdges::iterator Node::UseEdges::end() const {
574 return Node::UseEdges::iterator();
575 }
576
577
578 // A forward iterator to visit the uses of a node.
579 class Node::Uses::const_iterator final {
580 public:
581 typedef std::forward_iterator_tag iterator_category;
582 typedef int difference_type;
583 typedef Node* value_type;
584 typedef Node** pointer;
585 typedef Node*& reference;
586
const_iterator(const const_iterator & other)587 const_iterator(const const_iterator& other)
588 : current_(other.current_)
589 #ifdef DEBUG
590 ,
591 next_(other.next_)
592 #endif
593 {
594 }
595
596 Node* operator*() const { return current_->from(); }
597 bool operator==(const const_iterator& other) const {
598 return other.current_ == current_;
599 }
600 bool operator!=(const const_iterator& other) const {
601 return other.current_ != current_;
602 }
603 const_iterator& operator++() {
604 DCHECK_NOT_NULL(current_);
605 // Checking no use gets mutated while iterating through them, a potential
606 // very tricky cause of bug.
607 current_ = current_->next;
608 #ifdef DEBUG
609 DCHECK_EQ(current_, next_);
610 next_ = current_ ? current_->next : nullptr;
611 #endif
612 return *this;
613 }
614 const_iterator operator++(int);
615
616 private:
617 friend class Node::Uses;
618
const_iterator()619 const_iterator() : current_(nullptr) {}
const_iterator(Node * node)620 explicit const_iterator(Node* node)
621 : current_(node->first_use_)
622 #ifdef DEBUG
623 ,
624 next_(current_ ? current_->next : nullptr)
625 #endif
626 {
627 }
628
629 Node::Use* current_;
630 #ifdef DEBUG
631 Node::Use* next_;
632 #endif
633 };
634
635
begin()636 Node::Uses::const_iterator Node::Uses::begin() const {
637 return const_iterator(this->node_);
638 }
639
640
end()641 Node::Uses::const_iterator Node::Uses::end() const { return const_iterator(); }
642
643 } // namespace compiler
644 } // namespace internal
645 } // namespace v8
646
647 #endif // V8_COMPILER_NODE_H_
648