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