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 : 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 6187922843 : return static_cast<IrOpcode::Value>(op_->opcode());
57 : }
58 :
59 : NodeId id() const { return IdField::decode(bit_field_); }
60 :
61 1086371787 : int InputCount() const {
62 : return has_inline_inputs() ? InlineCountField::decode(bit_field_)
63 1277737596 : : outline_inputs()->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 2081436465 : return *GetInputPtrConst(index);
86 : }
87 :
88 149594747 : void ReplaceInput(int index, Node* new_to) {
89 : BOUNDS_CHECK(index);
90 : Node** input_ptr = GetInputPtr(index);
91 149594747 : Node* old_to = *input_ptr;
92 149594747 : if (old_to != new_to) {
93 : Use* use = GetUsePtr(index);
94 96657021 : if (old_to) old_to->RemoveUse(use);
95 96657041 : *input_ptr = new_to;
96 96657041 : if (new_to) new_to->AppendUse(use);
97 : }
98 149594809 : }
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 10380488 : bool OwnedBy(Node* owner) const {
156 20760904 : 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 : void Print(std::ostream&) const;
164 :
165 : private:
166 : struct Use;
167 : // Out of line storage for inputs when the number of inputs overflowed the
168 : // capacity of the inline-allocated space.
169 : struct OutOfLineInputs {
170 : Node* node_;
171 : int count_;
172 : int capacity_;
173 :
174 : // Inputs are allocated right behind the OutOfLineInputs instance.
175 : inline Node** inputs();
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 4162520082 : int input_index() const { return InputIndexField::decode(bit_field_); }
189 : bool is_inline_use() const { return InlineField::decode(bit_field_); }
190 1535656597 : Node** input_ptr() {
191 : int index = input_index();
192 1535656597 : Use* start = this + 1 + index;
193 : Node** inputs = is_inline_use()
194 : ? reinterpret_cast<Node*>(start)->inline_inputs()
195 1511627511 : : reinterpret_cast<OutOfLineInputs*>(start)->inputs();
196 1511627511 : return &inputs[index];
197 : }
198 :
199 1993187818 : Node* from() {
200 2323766738 : Use* start = this + 1 + input_index();
201 : return is_inline_use() ? reinterpret_cast<Node*>(start)
202 3566048165 : : 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 : inline Address inputs_location() const;
245 :
246 : Node** inline_inputs() const {
247 6304057738 : return reinterpret_cast<Node**>(inputs_location());
248 : }
249 : OutOfLineInputs* outline_inputs() const {
250 1157837274 : return *reinterpret_cast<OutOfLineInputs**>(inputs_location());
251 : }
252 : void set_outline_inputs(OutOfLineInputs* outline) {
253 14089114 : *reinterpret_cast<OutOfLineInputs**>(inputs_location()) = outline;
254 : }
255 :
256 1514381218 : Node* const* GetInputPtrConst(int input_index) const {
257 : return has_inline_inputs() ? &(inline_inputs()[input_index])
258 3977572786 : : &(outline_inputs()->inputs()[input_index]);
259 : }
260 205797014 : Node** GetInputPtr(int input_index) {
261 78325811 : return has_inline_inputs() ? &(inline_inputs()[input_index])
262 400482380 : : &(outline_inputs()->inputs()[input_index]);
263 : }
264 28160208 : Use* GetUsePtr(int input_index) {
265 : Use* ptr = has_inline_inputs() ? reinterpret_cast<Use*>(this)
266 154327929 : : reinterpret_cast<Use*>(outline_inputs());
267 140278999 : return &ptr[-1 - input_index];
268 : }
269 :
270 : void AppendUse(Use* use);
271 : void RemoveUse(Use* use);
272 :
273 : void* operator new(size_t, void* location) { return location; }
274 :
275 : // Only NodeProperties should manipulate the op.
276 37936553 : void set_op(const Operator* op) { op_ = op; }
277 :
278 : // Only NodeProperties should manipulate the type.
279 : Type type() const { return type_; }
280 47731176 : void set_type(Type type) { type_ = type; }
281 :
282 : // Only NodeMarkers should manipulate the marks on nodes.
283 4330376693 : Mark mark() const { return mark_; }
284 1443959393 : void set_mark(Mark mark) { mark_ = mark; }
285 :
286 : inline bool has_inline_inputs() const {
287 : return InlineCountField::decode(bit_field_) != kOutlineMarker;
288 : }
289 :
290 : void ClearInputs(int start, int count);
291 :
292 : typedef BitField<NodeId, 0, 24> IdField;
293 : typedef BitField<unsigned, 24, 4> InlineCountField;
294 : typedef BitField<unsigned, 28, 4> InlineCapacityField;
295 : static const int kOutlineMarker = InlineCountField::kMax;
296 : static const int kMaxInlineCount = InlineCountField::kMax - 1;
297 : static const int kMaxInlineCapacity = InlineCapacityField::kMax - 1;
298 :
299 : const Operator* op_;
300 : Type type_;
301 : Mark mark_;
302 : uint32_t bit_field_;
303 : Use* first_use_;
304 :
305 : friend class Edge;
306 : friend class NodeMarkerBase;
307 : friend class NodeProperties;
308 :
309 : DISALLOW_COPY_AND_ASSIGN(Node);
310 : };
311 :
312 : Address Node::inputs_location() const {
313 7475538242 : return reinterpret_cast<Address>(this) + sizeof(Node);
314 : }
315 :
316 : Node** Node::OutOfLineInputs::inputs() {
317 1333977021 : return reinterpret_cast<Node**>(reinterpret_cast<Address>(this) +
318 1333977021 : sizeof(Node::OutOfLineInputs));
319 : }
320 :
321 : std::ostream& operator<<(std::ostream& os, const Node& n);
322 :
323 :
324 : // Typedefs to shorten commonly used Node containers.
325 : typedef ZoneDeque<Node*> NodeDeque;
326 : typedef ZoneSet<Node*> NodeSet;
327 : typedef ZoneVector<Node*> NodeVector;
328 : typedef ZoneVector<NodeVector> NodeVectorVector;
329 :
330 :
331 : class Node::InputEdges final {
332 : public:
333 : typedef Edge value_type;
334 :
335 : class iterator;
336 : inline iterator begin() const;
337 : inline iterator end() const;
338 :
339 : bool empty() const { return count_ == 0; }
340 : int count() const { return count_; }
341 :
342 : inline value_type operator[](int index) const;
343 :
344 : InputEdges(Node** input_root, Use* use_root, int count)
345 : : input_root_(input_root), use_root_(use_root), count_(count) {}
346 :
347 : private:
348 : Node** input_root_;
349 : Use* use_root_;
350 : int count_;
351 : };
352 :
353 : class V8_EXPORT_PRIVATE Node::Inputs final {
354 : public:
355 : typedef Node* value_type;
356 :
357 : class const_iterator;
358 : inline const_iterator begin() const;
359 : inline const_iterator end() const;
360 :
361 4 : bool empty() const { return count_ == 0; }
362 : int count() const { return count_; }
363 :
364 : inline value_type operator[](int index) const;
365 :
366 : explicit Inputs(Node* const* input_root, int count)
367 : : input_root_(input_root), count_(count) {}
368 :
369 : private:
370 : Node* const* input_root_;
371 : int count_;
372 : };
373 :
374 : // An encapsulation for information associated with a single use of node as a
375 : // input from another node, allowing access to both the defining node and
376 : // the node having the input.
377 : class Edge final {
378 : public:
379 : Node* from() const { return use_->from(); }
380 686489056 : Node* to() const { return *input_ptr_; }
381 : int index() const {
382 633675667 : int const index = use_->input_index();
383 : DCHECK_LT(index, use_->from()->InputCount());
384 : return index;
385 : }
386 :
387 : bool operator==(const Edge& other) { return input_ptr_ == other.input_ptr_; }
388 : bool operator!=(const Edge& other) { return !(*this == other); }
389 :
390 95207754 : void UpdateTo(Node* new_to) {
391 95207754 : Node* old_to = *input_ptr_;
392 95207754 : if (old_to != new_to) {
393 91414497 : if (old_to) old_to->RemoveUse(use_);
394 91414606 : *input_ptr_ = new_to;
395 91414606 : if (new_to) new_to->AppendUse(use_);
396 : }
397 95207945 : }
398 :
399 : private:
400 : friend class Node::UseEdges::iterator;
401 : friend class Node::InputEdges;
402 : friend class Node::InputEdges::iterator;
403 :
404 : Edge(Node::Use* use, Node** input_ptr) : use_(use), input_ptr_(input_ptr) {
405 : DCHECK_NOT_NULL(use);
406 : DCHECK_NOT_NULL(input_ptr);
407 : DCHECK_EQ(input_ptr, use->input_ptr());
408 : }
409 :
410 : Node::Use* use_;
411 : Node** input_ptr_;
412 : };
413 :
414 1429805299 : bool Node::IsDead() const {
415 : Node::Inputs inputs = this->inputs();
416 2659624893 : return inputs.count() > 0 && inputs[0] == nullptr;
417 : }
418 :
419 : Node::InputEdges Node::input_edges() {
420 914693004 : int inline_count = InlineCountField::decode(bit_field_);
421 503236153 : if (inline_count != kOutlineMarker) {
422 : return InputEdges(inline_inputs(), reinterpret_cast<Use*>(this) - 1,
423 158894052 : inline_count);
424 : } else {
425 : return InputEdges(outline_inputs()->inputs(),
426 : reinterpret_cast<Use*>(outline_inputs()) - 1,
427 134297196 : outline_inputs()->count_);
428 : }
429 : }
430 :
431 : Node::Inputs Node::inputs() const {
432 6342834874 : int inline_count = InlineCountField::decode(bit_field_);
433 3175777377 : if (inline_count != kOutlineMarker) {
434 : return Inputs(inline_inputs(), inline_count);
435 : } else {
436 315724684 : return Inputs(outline_inputs()->inputs(), outline_inputs()->count_);
437 : }
438 : }
439 :
440 : // A forward iterator to visit the edges for the input dependencies of a node.
441 : class Node::InputEdges::iterator final {
442 : public:
443 : typedef std::forward_iterator_tag iterator_category;
444 : typedef std::ptrdiff_t difference_type;
445 : typedef Edge value_type;
446 : typedef Edge* pointer;
447 : typedef Edge& reference;
448 :
449 : iterator() : use_(nullptr), input_ptr_(nullptr) {}
450 : iterator(const iterator& other) = default;
451 :
452 442667509 : Edge operator*() const { return Edge(use_, input_ptr_); }
453 : bool operator==(const iterator& other) const {
454 : return input_ptr_ == other.input_ptr_;
455 : }
456 652469 : bool operator!=(const iterator& other) const { return !(*this == other); }
457 : iterator& operator++() {
458 554266425 : input_ptr_++;
459 554266425 : use_--;
460 : return *this;
461 : }
462 : iterator operator++(int);
463 : iterator& operator+=(difference_type offset) {
464 : input_ptr_ += offset;
465 : use_ -= offset;
466 : return *this;
467 : }
468 : iterator operator+(difference_type offset) const {
469 : return iterator(use_ - offset, input_ptr_ + offset);
470 : }
471 : difference_type operator-(const iterator& other) const {
472 : return input_ptr_ - other.input_ptr_;
473 : }
474 :
475 : private:
476 : friend class Node;
477 :
478 : explicit iterator(Use* use, Node** input_ptr)
479 : : use_(use), input_ptr_(input_ptr) {}
480 :
481 : Use* use_;
482 : Node** input_ptr_;
483 : };
484 :
485 :
486 : Node::InputEdges::iterator Node::InputEdges::begin() const {
487 : return Node::InputEdges::iterator(use_root_, input_root_);
488 : }
489 :
490 :
491 : Node::InputEdges::iterator Node::InputEdges::end() const {
492 408902783 : return Node::InputEdges::iterator(use_root_ - count_, input_root_ + count_);
493 : }
494 :
495 : Edge Node::InputEdges::operator[](int index) const {
496 : return Edge(use_root_ + index, input_root_ + index);
497 : }
498 :
499 : // A forward iterator to visit the inputs of a node.
500 : class Node::Inputs::const_iterator final {
501 : public:
502 : typedef std::forward_iterator_tag iterator_category;
503 : typedef std::ptrdiff_t difference_type;
504 : typedef Node* value_type;
505 : typedef const value_type* pointer;
506 : typedef value_type& reference;
507 :
508 : const_iterator(const const_iterator& other) = default;
509 :
510 2161418187 : Node* operator*() const { return *input_ptr_; }
511 : bool operator==(const const_iterator& other) const {
512 1 : return input_ptr_ == other.input_ptr_;
513 : }
514 : bool operator!=(const const_iterator& other) const {
515 : return !(*this == other);
516 : }
517 : const_iterator& operator++() {
518 2153731932 : ++input_ptr_;
519 : return *this;
520 : }
521 : const_iterator operator++(int);
522 : const_iterator& operator+=(difference_type offset) {
523 : input_ptr_ += offset;
524 : return *this;
525 : }
526 : const_iterator operator+(difference_type offset) const {
527 : return const_iterator(input_ptr_ + offset);
528 : }
529 : difference_type operator-(const const_iterator& other) const {
530 : return input_ptr_ - other.input_ptr_;
531 : }
532 :
533 : private:
534 : friend class Node::Inputs;
535 :
536 : explicit const_iterator(Node* const* input_ptr) : input_ptr_(input_ptr) {}
537 :
538 : Node* const* input_ptr_;
539 : };
540 :
541 :
542 : Node::Inputs::const_iterator Node::Inputs::begin() const {
543 : return const_iterator(input_root_);
544 : }
545 :
546 :
547 : Node::Inputs::const_iterator Node::Inputs::end() const {
548 796689078 : return const_iterator(input_root_ + count_);
549 : }
550 :
551 3428751077 : Node* Node::Inputs::operator[](int index) const { return input_root_[index]; }
552 :
553 : // A forward iterator to visit the uses edges of a node.
554 : class Node::UseEdges::iterator final {
555 : public:
556 : iterator(const iterator& other) = default;
557 :
558 : Edge operator*() const { return Edge(current_, current_->input_ptr()); }
559 : bool operator==(const iterator& other) const {
560 18734 : return current_ == other.current_;
561 : }
562 1075877 : bool operator!=(const iterator& other) const { return !(*this == other); }
563 : iterator& operator++() {
564 : DCHECK_NOT_NULL(current_);
565 687961 : current_ = next_;
566 1514235552 : next_ = current_ ? current_->next : nullptr;
567 : return *this;
568 : }
569 : iterator operator++(int);
570 :
571 : private:
572 : friend class Node::UseEdges;
573 :
574 : iterator() : current_(nullptr), next_(nullptr) {}
575 : explicit iterator(Node* node)
576 : : current_(node->first_use_),
577 568743455 : next_(current_ ? current_->next : nullptr) {}
578 :
579 : Node::Use* current_;
580 : Node::Use* next_;
581 : };
582 :
583 :
584 : Node::UseEdges::iterator Node::UseEdges::begin() const {
585 18734 : return Node::UseEdges::iterator(this->node_);
586 : }
587 :
588 :
589 : Node::UseEdges::iterator Node::UseEdges::end() const {
590 : return Node::UseEdges::iterator();
591 : }
592 :
593 :
594 : // A forward iterator to visit the uses of a node.
595 : class Node::Uses::const_iterator final {
596 : public:
597 : typedef std::forward_iterator_tag iterator_category;
598 : typedef int difference_type;
599 : typedef Node* value_type;
600 : typedef Node** pointer;
601 : typedef Node*& reference;
602 :
603 185648 : Node* operator*() const { return current_->from(); }
604 : bool operator==(const const_iterator& other) const {
605 1128551 : return other.current_ == current_;
606 : }
607 : bool operator!=(const const_iterator& other) const {
608 8876 : return other.current_ != current_;
609 : }
610 : const_iterator& operator++() {
611 : DCHECK_NOT_NULL(current_);
612 : // Checking no use gets mutated while iterating through them, a potential
613 : // very tricky cause of bug.
614 620959512 : current_ = current_->next;
615 : #ifdef DEBUG
616 : DCHECK_EQ(current_, next_);
617 : next_ = current_ ? current_->next : nullptr;
618 : #endif
619 : return *this;
620 : }
621 : const_iterator operator++(int);
622 :
623 : private:
624 : friend class Node::Uses;
625 :
626 : const_iterator() : current_(nullptr) {}
627 : explicit const_iterator(Node* node)
628 230005511 : : current_(node->first_use_)
629 : #ifdef DEBUG
630 : ,
631 : next_(current_ ? current_->next : nullptr)
632 : #endif
633 : {
634 : }
635 :
636 : Node::Use* current_;
637 : #ifdef DEBUG
638 : Node::Use* next_;
639 : #endif
640 : };
641 :
642 :
643 : Node::Uses::const_iterator Node::Uses::begin() const {
644 1128682 : return const_iterator(this->node_);
645 : }
646 :
647 :
648 : Node::Uses::const_iterator Node::Uses::end() const { return const_iterator(); }
649 :
650 : } // namespace compiler
651 : } // namespace internal
652 : } // namespace v8
653 :
654 : #endif // V8_COMPILER_NODE_H_
|
