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 5674655106 : return static_cast<IrOpcode::Value>(op_->opcode());
57 : }
58 :
59 : NodeId id() const { return IdField::decode(bit_field_); }
60 :
61 981507842 : int InputCount() const {
62 : return has_inline_inputs() ? InlineCountField::decode(bit_field_)
63 1050222012 : : 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 1841329053 : return *GetInputPtrConst(index);
86 : }
87 :
88 128942688 : void ReplaceInput(int index, Node* new_to) {
89 : BOUNDS_CHECK(index);
90 : Node** input_ptr = GetInputPtr(index);
91 128942688 : Node* old_to = *input_ptr;
92 128942688 : if (old_to != new_to) {
93 : Use* use = GetUsePtr(index);
94 83510154 : if (old_to) old_to->RemoveUse(use);
95 83510165 : *input_ptr = new_to;
96 83510165 : if (new_to) new_to->AppendUse(use);
97 : }
98 128942764 : }
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 10375158 : bool OwnedBy(Node* owner) const {
156 20750266 : 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 : Node* inputs_[1];
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 3712698912 : int input_index() const { return InputIndexField::decode(bit_field_); }
187 : bool is_inline_use() const { return InlineField::decode(bit_field_); }
188 1373109406 : Node** input_ptr() {
189 : int index = input_index();
190 1373109406 : Use* start = this + 1 + index;
191 : Node** inputs = is_inline_use()
192 : ? reinterpret_cast<Node*>(start)->inputs_.inline_
193 1351257179 : : reinterpret_cast<OutOfLineInputs*>(start)->inputs_;
194 1351257179 : return &inputs[index];
195 : }
196 :
197 1767124825 : Node* from() {
198 2077639561 : Use* start = this + 1 + input_index();
199 : return is_inline_use() ? reinterpret_cast<Node*>(start)
200 3203069400 : : reinterpret_cast<OutOfLineInputs*>(start)->node_;
201 : }
202 :
203 : typedef BitField<bool, 0, 1> InlineField;
204 : typedef BitField<unsigned, 1, 17> InputIndexField;
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 1349852423 : Node* const* GetInputPtrConst(int input_index) const {
243 : return has_inline_inputs() ? &(inputs_.inline_[input_index])
244 1841329053 : : &inputs_.outline_->inputs_[input_index];
245 : }
246 179854829 : Node** GetInputPtr(int input_index) {
247 : return has_inline_inputs() ? &(inputs_.inline_[input_index])
248 180972836 : : &inputs_.outline_->inputs_[input_index];
249 : }
250 24361201 : Use* GetUsePtr(int input_index) {
251 : Use* ptr = has_inline_inputs() ? reinterpret_cast<Use*>(this)
252 135540302 : : reinterpret_cast<Use*>(inputs_.outline_);
253 123818928 : return &ptr[-1 - input_index];
254 : }
255 :
256 : void AppendUse(Use* use);
257 : void RemoveUse(Use* use);
258 :
259 : void* operator new(size_t, void* location) { return location; }
260 :
261 : // Only NodeProperties should manipulate the op.
262 40025495 : void set_op(const Operator* op) { op_ = op; }
263 :
264 : // Only NodeProperties should manipulate the type.
265 : Type type() const { return type_; }
266 45863625 : void set_type(Type type) { type_ = type; }
267 :
268 : // Only NodeMarkers should manipulate the marks on nodes.
269 3855982974 : Mark mark() const { return mark_; }
270 1347324998 : void set_mark(Mark mark) { mark_ = mark; }
271 :
272 : inline bool has_inline_inputs() const {
273 : return InlineCountField::decode(bit_field_) != kOutlineMarker;
274 : }
275 :
276 : void ClearInputs(int start, int count);
277 :
278 : typedef BitField<NodeId, 0, 24> IdField;
279 : typedef BitField<unsigned, 24, 4> InlineCountField;
280 : typedef BitField<unsigned, 28, 4> InlineCapacityField;
281 : static const int kOutlineMarker = InlineCountField::kMax;
282 : static const int kMaxInlineCount = InlineCountField::kMax - 1;
283 : static const int kMaxInlineCapacity = InlineCapacityField::kMax - 1;
284 :
285 : const Operator* op_;
286 : Type type_;
287 : Mark mark_;
288 : uint32_t bit_field_;
289 : Use* first_use_;
290 : union {
291 : // Inline storage for inputs or out-of-line storage.
292 : Node* inline_[1];
293 : OutOfLineInputs* outline_;
294 : } inputs_;
295 :
296 : friend class Edge;
297 : friend class NodeMarkerBase;
298 : friend class NodeProperties;
299 :
300 : DISALLOW_COPY_AND_ASSIGN(Node);
301 : };
302 :
303 :
304 : std::ostream& operator<<(std::ostream& os, const Node& n);
305 :
306 :
307 : // Typedefs to shorten commonly used Node containers.
308 : typedef ZoneDeque<Node*> NodeDeque;
309 : typedef ZoneSet<Node*> NodeSet;
310 : typedef ZoneVector<Node*> NodeVector;
311 : typedef ZoneVector<NodeVector> NodeVectorVector;
312 :
313 :
314 : class Node::InputEdges final {
315 : public:
316 : typedef Edge value_type;
317 :
318 : class iterator;
319 : inline iterator begin() const;
320 : inline iterator end() const;
321 :
322 : bool empty() const { return count_ == 0; }
323 : int count() const { return count_; }
324 :
325 : inline value_type operator[](int index) const;
326 :
327 : InputEdges(Node** input_root, Use* use_root, int count)
328 : : input_root_(input_root), use_root_(use_root), count_(count) {}
329 :
330 : private:
331 : Node** input_root_;
332 : Use* use_root_;
333 : int count_;
334 : };
335 :
336 : class V8_EXPORT_PRIVATE Node::Inputs final {
337 : public:
338 : typedef Node* value_type;
339 :
340 : class const_iterator;
341 : inline const_iterator begin() const;
342 : inline const_iterator end() const;
343 :
344 4 : bool empty() const { return count_ == 0; }
345 : int count() const { return count_; }
346 :
347 : inline value_type operator[](int index) const;
348 :
349 : explicit Inputs(Node* const* input_root, int count)
350 : : input_root_(input_root), count_(count) {}
351 :
352 : private:
353 : Node* const* input_root_;
354 : int count_;
355 : };
356 :
357 : // An encapsulation for information associated with a single use of node as a
358 : // input from another node, allowing access to both the defining node and
359 : // the node having the input.
360 : class Edge final {
361 : public:
362 : Node* from() const { return use_->from(); }
363 649211284 : Node* to() const { return *input_ptr_; }
364 : int index() const {
365 572464681 : int const index = use_->input_index();
366 : DCHECK_LT(index, use_->from()->InputCount());
367 : return index;
368 : }
369 :
370 : bool operator==(const Edge& other) { return input_ptr_ == other.input_ptr_; }
371 : bool operator!=(const Edge& other) { return !(*this == other); }
372 :
373 94295128 : void UpdateTo(Node* new_to) {
374 94295128 : Node* old_to = *input_ptr_;
375 94295128 : if (old_to != new_to) {
376 90651481 : if (old_to) old_to->RemoveUse(use_);
377 90651684 : *input_ptr_ = new_to;
378 90651684 : if (new_to) new_to->AppendUse(use_);
379 : }
380 94295476 : }
381 :
382 : private:
383 : friend class Node::UseEdges::iterator;
384 : friend class Node::InputEdges;
385 : friend class Node::InputEdges::iterator;
386 :
387 : Edge(Node::Use* use, Node** input_ptr) : use_(use), input_ptr_(input_ptr) {
388 : DCHECK_NOT_NULL(use);
389 : DCHECK_NOT_NULL(input_ptr);
390 : DCHECK_EQ(input_ptr, use->input_ptr());
391 : }
392 :
393 : Node::Use* use_;
394 : Node** input_ptr_;
395 : };
396 :
397 : bool Node::IsDead() const {
398 : Node::Inputs inputs = this->inputs();
399 2416961576 : return inputs.count() > 0 && inputs[0] == nullptr;
400 : }
401 :
402 : Node::InputEdges Node::input_edges() {
403 877526263 : int inline_count = InlineCountField::decode(bit_field_);
404 483279513 : if (inline_count != kOutlineMarker) {
405 : return InputEdges(inputs_.inline_, reinterpret_cast<Use*>(this) - 1,
406 370053885 : inline_count);
407 : } else {
408 : return InputEdges(inputs_.outline_->inputs_,
409 : reinterpret_cast<Use*>(inputs_.outline_) - 1,
410 113225628 : inputs_.outline_->count_);
411 : }
412 : }
413 :
414 : Node::Inputs Node::inputs() const {
415 4312515942 : int inline_count = InlineCountField::decode(bit_field_);
416 2927313346 : if (inline_count != kOutlineMarker) {
417 2639406534 : return Inputs(inputs_.inline_, inline_count);
418 : } else {
419 287906801 : return Inputs(inputs_.outline_->inputs_, inputs_.outline_->count_);
420 : }
421 : }
422 :
423 : // A forward iterator to visit the edges for the input dependencies of a node.
424 : class Node::InputEdges::iterator final {
425 : public:
426 : typedef std::forward_iterator_tag iterator_category;
427 : typedef std::ptrdiff_t difference_type;
428 : typedef Edge value_type;
429 : typedef Edge* pointer;
430 : typedef Edge& reference;
431 :
432 : iterator() : use_(nullptr), input_ptr_(nullptr) {}
433 : iterator(const iterator& other) = default;
434 :
435 426221235 : Edge operator*() const { return Edge(use_, input_ptr_); }
436 : bool operator==(const iterator& other) const {
437 : return input_ptr_ == other.input_ptr_;
438 : }
439 1056108 : bool operator!=(const iterator& other) const { return !(*this == other); }
440 : iterator& operator++() {
441 516227997 : input_ptr_++;
442 516227997 : 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 :
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 :
469 : Node::InputEdges::iterator Node::InputEdges::begin() const {
470 : return Node::InputEdges::iterator(use_root_, input_root_);
471 : }
472 :
473 :
474 : Node::InputEdges::iterator Node::InputEdges::end() const {
475 390805477 : 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 :
491 : const_iterator(const const_iterator& other) = default;
492 :
493 1918667802 : Node* operator*() const { return *input_ptr_; }
494 : bool operator==(const const_iterator& other) const {
495 1 : 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 1911249863 : ++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 :
519 : explicit const_iterator(Node* const* input_ptr) : input_ptr_(input_ptr) {}
520 :
521 : Node* const* input_ptr_;
522 : };
523 :
524 :
525 : Node::Inputs::const_iterator Node::Inputs::begin() const {
526 : return const_iterator(input_root_);
527 : }
528 :
529 :
530 : Node::Inputs::const_iterator Node::Inputs::end() const {
531 745635382 : return const_iterator(input_root_ + count_);
532 : }
533 :
534 3049873965 : 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:
539 : iterator(const iterator& other) = default;
540 :
541 : Edge operator*() const { return Edge(current_, current_->input_ptr()); }
542 : bool operator==(const iterator& other) const {
543 18788 : return current_ == other.current_;
544 : }
545 1604122 : bool operator!=(const iterator& other) const { return !(*this == other); }
546 : iterator& operator++() {
547 : DCHECK_NOT_NULL(current_);
548 968420 : current_ = next_;
549 1353238170 : next_ = current_ ? current_->next : nullptr;
550 : return *this;
551 : }
552 : iterator operator++(int);
553 :
554 : private:
555 : friend class Node::UseEdges;
556 :
557 : iterator() : current_(nullptr), next_(nullptr) {}
558 : explicit iterator(Node* node)
559 : : current_(node->first_use_),
560 541431732 : next_(current_ ? current_->next : nullptr) {}
561 :
562 : Node::Use* current_;
563 : Node::Use* next_;
564 : };
565 :
566 :
567 : Node::UseEdges::iterator Node::UseEdges::begin() const {
568 18788 : return Node::UseEdges::iterator(this->node_);
569 : }
570 :
571 :
572 : Node::UseEdges::iterator Node::UseEdges::end() const {
573 : return Node::UseEdges::iterator();
574 : }
575 :
576 :
577 : // A forward iterator to visit the uses of a node.
578 : class Node::Uses::const_iterator final {
579 : public:
580 : typedef std::forward_iterator_tag iterator_category;
581 : typedef int difference_type;
582 : typedef Node* value_type;
583 : typedef Node** pointer;
584 : typedef Node*& reference;
585 :
586 177400 : Node* operator*() const { return current_->from(); }
587 : bool operator==(const const_iterator& other) const {
588 1457929 : return other.current_ == current_;
589 : }
590 : bool operator!=(const const_iterator& other) const {
591 12184 : return other.current_ != current_;
592 : }
593 : const_iterator& operator++() {
594 : DCHECK_NOT_NULL(current_);
595 : // Checking no use gets mutated while iterating through them, a potential
596 : // very tricky cause of bug.
597 525916347 : current_ = current_->next;
598 : #ifdef DEBUG
599 : DCHECK_EQ(current_, next_);
600 : next_ = current_ ? current_->next : nullptr;
601 : #endif
602 : return *this;
603 : }
604 : const_iterator operator++(int);
605 :
606 : private:
607 : friend class Node::Uses;
608 :
609 : const_iterator() : current_(nullptr) {}
610 : explicit const_iterator(Node* node)
611 203911753 : : current_(node->first_use_)
612 : #ifdef DEBUG
613 : ,
614 : next_(current_ ? current_->next : nullptr)
615 : #endif
616 : {
617 : }
618 :
619 : Node::Use* current_;
620 : #ifdef DEBUG
621 : Node::Use* next_;
622 : #endif
623 : };
624 :
625 :
626 : Node::Uses::const_iterator Node::Uses::begin() const {
627 1458192 : return const_iterator(this->node_);
628 : }
629 :
630 :
631 : Node::Uses::const_iterator Node::Uses::end() const { return const_iterator(); }
632 :
633 : } // namespace compiler
634 : } // namespace internal
635 : } // namespace v8
636 :
637 : #endif // V8_COMPILER_NODE_H_
|
