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(op_->opcode() <= IrOpcode::kLast);
56 3104774117 : return static_cast<IrOpcode::Value>(op_->opcode());
57 : }
58 :
59 : NodeId id() const { return IdField::decode(bit_field_); }
60 :
61 634897832 : int InputCount() const {
62 : return has_inline_inputs() ? InlineCountField::decode(bit_field_)
63 732146581 : : inputs_.outline_->count_;
64 : }
65 :
66 : #if DEBUG
67 : void Verify();
68 : #define BOUNDS_CHECK(index) \
69 : do { \
70 : if (index < 0 || index >= InputCount()) { \
71 : V8_Fatal(__FILE__, __LINE__, "Node #%d:%s->InputAt(%d) out of bounds", \
72 : id(), op()->mnemonic(), 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 1237779955 : return *GetInputPtrConst(index);
86 : }
87 :
88 120956785 : void ReplaceInput(int index, Node* new_to) {
89 : BOUNDS_CHECK(index);
90 : Node** input_ptr = GetInputPtr(index);
91 120956785 : Node* old_to = *input_ptr;
92 120956785 : if (old_to != new_to) {
93 : Use* use = GetUsePtr(index);
94 82694830 : if (old_to) old_to->RemoveUse(use);
95 82694841 : *input_ptr = new_to;
96 82694841 : if (new_to) new_to->AppendUse(use);
97 : }
98 120956805 : }
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 6380694 : bool OwnedBy(Node* owner) const {
156 12761434 : 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 : // Returns true if addressing related operands (such as load, store, lea)
163 : // are the only users of {this} node.
164 : bool OwnedByAddressingOperand() const;
165 : void Print() const;
166 :
167 : private:
168 : struct Use;
169 : // Out of line storage for inputs when the number of inputs overflowed the
170 : // capacity of the inline-allocated space.
171 : struct OutOfLineInputs {
172 : Node* node_;
173 : int count_;
174 : int capacity_;
175 : Node* inputs_[1];
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 3512621425 : int input_index() const { return InputIndexField::decode(bit_field_); }
189 : bool is_inline_use() const { return InlineField::decode(bit_field_); }
190 1069134620 : Node** input_ptr() {
191 : int index = input_index();
192 1069134620 : Use* start = this + 1 + index;
193 : Node** inputs = is_inline_use()
194 : ? reinterpret_cast<Node*>(start)->inputs_.inline_
195 1030101942 : : reinterpret_cast<OutOfLineInputs*>(start)->inputs_;
196 1030101942 : return &inputs[index];
197 : }
198 :
199 2006876207 : Node* from() {
200 2214871578 : Use* start = this + 1 + input_index();
201 : return is_inline_use() ? reinterpret_cast<Node*>(start)
202 2274619057 : : 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 888055562 : Node* const* GetInputPtrConst(int input_index) const {
245 : return has_inline_inputs() ? &(inputs_.inline_[input_index])
246 1237779955 : : &inputs_.outline_->inputs_[input_index];
247 : }
248 156032466 : Node** GetInputPtr(int input_index) {
249 : return has_inline_inputs() ? &(inputs_.inline_[input_index])
250 158364538 : : &inputs_.outline_->inputs_[input_index];
251 : }
252 17749181 : Use* GetUsePtr(int input_index) {
253 : Use* ptr = has_inline_inputs() ? reinterpret_cast<Use*>(this)
254 120102583 : : reinterpret_cast<Use*>(inputs_.outline_);
255 113856848 : return &ptr[-1 - input_index];
256 : }
257 :
258 : void AppendUse(Use* use);
259 : void RemoveUse(Use* use);
260 :
261 : void* operator new(size_t, void* location) { return location; }
262 :
263 : // Only NodeProperties should manipulate the op.
264 22903540 : void set_op(const Operator* op) { op_ = op; }
265 :
266 : // Only NodeProperties should manipulate the type.
267 : Type* type() const { return type_; }
268 39861828 : void set_type(Type* type) { type_ = type; }
269 :
270 : // Only NodeMarkers should manipulate the marks on nodes.
271 3054448835 : Mark mark() const { return mark_; }
272 1023055963 : void set_mark(Mark mark) { mark_ = mark; }
273 :
274 : inline bool has_inline_inputs() const {
275 : return InlineCountField::decode(bit_field_) != kOutlineMarker;
276 : }
277 :
278 : void ClearInputs(int start, int count);
279 :
280 : typedef BitField<NodeId, 0, 24> IdField;
281 : typedef BitField<unsigned, 24, 4> InlineCountField;
282 : typedef BitField<unsigned, 28, 4> InlineCapacityField;
283 : static const int kOutlineMarker = InlineCountField::kMax;
284 : static const int kMaxInlineCount = InlineCountField::kMax - 1;
285 : static const int kMaxInlineCapacity = InlineCapacityField::kMax - 1;
286 :
287 : const Operator* op_;
288 : Type* type_;
289 : Mark mark_;
290 : uint32_t bit_field_;
291 : Use* first_use_;
292 : union {
293 : // Inline storage for inputs or out-of-line storage.
294 : Node* inline_[1];
295 : OutOfLineInputs* outline_;
296 : } inputs_;
297 :
298 : friend class Edge;
299 : friend class NodeMarkerBase;
300 : friend class NodeProperties;
301 :
302 : DISALLOW_COPY_AND_ASSIGN(Node);
303 : };
304 :
305 :
306 : std::ostream& operator<<(std::ostream& os, const Node& n);
307 :
308 :
309 : // Typedefs to shorten commonly used Node containers.
310 : typedef ZoneDeque<Node*> NodeDeque;
311 : typedef ZoneSet<Node*> NodeSet;
312 : typedef ZoneVector<Node*> NodeVector;
313 : typedef ZoneVector<NodeVector> NodeVectorVector;
314 :
315 :
316 : // Helper to extract parameters from Operator1<*> nodes.
317 : template <typename T>
318 3392916 : static inline const T& OpParameter(const Node* node) {
319 : return OpParameter<T>(node->op());
320 : }
321 :
322 : class Node::InputEdges final {
323 : public:
324 : typedef Edge value_type;
325 :
326 : class iterator;
327 : inline iterator begin() const;
328 : inline iterator end() const;
329 :
330 : bool empty() const { return count_ == 0; }
331 : int count() const { return count_; }
332 :
333 : inline value_type operator[](int index) const;
334 :
335 : InputEdges(Node** input_root, Use* use_root, int count)
336 : : input_root_(input_root), use_root_(use_root), count_(count) {}
337 :
338 : private:
339 : Node** input_root_;
340 : Use* use_root_;
341 : int count_;
342 : };
343 :
344 : class V8_EXPORT_PRIVATE Node::Inputs final {
345 : public:
346 : typedef Node* value_type;
347 :
348 : class const_iterator;
349 : inline const_iterator begin() const;
350 : inline const_iterator end() const;
351 :
352 : bool empty() const { return count_ == 0; }
353 : int count() const { return count_; }
354 :
355 : inline value_type operator[](int index) const;
356 :
357 : explicit Inputs(Node* const* input_root, int count)
358 : : input_root_(input_root), count_(count) {}
359 :
360 : private:
361 : Node* const* input_root_;
362 : int count_;
363 : };
364 :
365 : // An encapsulation for information associated with a single use of node as a
366 : // input from another node, allowing access to both the defining node and
367 : // the node having the input.
368 : class Edge final {
369 : public:
370 : Node* from() const { return use_->from(); }
371 541410536 : Node* to() const { return *input_ptr_; }
372 : int index() const {
373 436610598 : int const index = use_->input_index();
374 : DCHECK_LT(index, use_->from()->InputCount());
375 : return index;
376 : }
377 :
378 : bool operator==(const Edge& other) { return input_ptr_ == other.input_ptr_; }
379 : bool operator!=(const Edge& other) { return !(*this == other); }
380 :
381 82176825 : void UpdateTo(Node* new_to) {
382 82176825 : Node* old_to = *input_ptr_;
383 82176825 : if (old_to != new_to) {
384 78190557 : if (old_to) old_to->RemoveUse(use_);
385 78190686 : *input_ptr_ = new_to;
386 78190686 : if (new_to) new_to->AppendUse(use_);
387 : }
388 82177085 : }
389 :
390 : private:
391 : friend class Node::UseEdges::iterator;
392 : friend class Node::InputEdges;
393 : friend class Node::InputEdges::iterator;
394 :
395 : Edge(Node::Use* use, Node** input_ptr) : use_(use), input_ptr_(input_ptr) {
396 : DCHECK_NOT_NULL(use);
397 : DCHECK_NOT_NULL(input_ptr);
398 : DCHECK_EQ(input_ptr, use->input_ptr());
399 : }
400 :
401 : Node::Use* use_;
402 : Node** input_ptr_;
403 : };
404 :
405 : bool Node::IsDead() const {
406 : Node::Inputs inputs = this->inputs();
407 1440287839 : return inputs.count() > 0 && inputs[0] == nullptr;
408 : }
409 :
410 : Node::InputEdges Node::input_edges() {
411 702047794 : int inline_count = InlineCountField::decode(bit_field_);
412 380693460 : if (inline_count != kOutlineMarker) {
413 : return InputEdges(inputs_.inline_, reinterpret_cast<Use*>(this) - 1,
414 293111750 : inline_count);
415 : } else {
416 : return InputEdges(inputs_.outline_->inputs_,
417 : reinterpret_cast<Use*>(inputs_.outline_) - 1,
418 87581710 : inputs_.outline_->count_);
419 : }
420 : }
421 :
422 : Node::Inputs Node::inputs() const {
423 2538261795 : int inline_count = InlineCountField::decode(bit_field_);
424 1867351338 : if (inline_count != kOutlineMarker) {
425 1653227353 : return Inputs(inputs_.inline_, inline_count);
426 : } else {
427 214123985 : return Inputs(inputs_.outline_->inputs_, inputs_.outline_->count_);
428 : }
429 : }
430 :
431 : // A forward iterator to visit the edges for the input dependencies of a node.
432 : class Node::InputEdges::iterator final {
433 : public:
434 : typedef std::forward_iterator_tag iterator_category;
435 : typedef std::ptrdiff_t difference_type;
436 : typedef Edge value_type;
437 : typedef Edge* pointer;
438 : typedef Edge& reference;
439 :
440 : iterator() : use_(nullptr), input_ptr_(nullptr) {}
441 : iterator(const iterator& other)
442 70184639 : : use_(other.use_), input_ptr_(other.input_ptr_) {}
443 :
444 292192116 : Edge operator*() const { return Edge(use_, input_ptr_); }
445 : bool operator==(const iterator& other) const {
446 : return input_ptr_ == other.input_ptr_;
447 : }
448 24229525 : bool operator!=(const iterator& other) const { return !(*this == other); }
449 : iterator& operator++() {
450 458392770 : input_ptr_++;
451 373500234 : use_--;
452 : return *this;
453 : }
454 : iterator operator++(int);
455 : iterator& operator+=(difference_type offset) {
456 : input_ptr_ += offset;
457 : use_ -= offset;
458 : return *this;
459 : }
460 : iterator operator+(difference_type offset) const {
461 : return iterator(use_ - offset, input_ptr_ + offset);
462 : }
463 : difference_type operator-(const iterator& other) const {
464 : return input_ptr_ - other.input_ptr_;
465 : }
466 :
467 : private:
468 : friend class Node;
469 :
470 : explicit iterator(Use* use, Node** input_ptr)
471 59339126 : : use_(use), input_ptr_(input_ptr) {}
472 :
473 : Use* use_;
474 : Node** input_ptr_;
475 : };
476 :
477 :
478 : Node::InputEdges::iterator Node::InputEdges::begin() const {
479 : return Node::InputEdges::iterator(use_root_, input_root_);
480 : }
481 :
482 :
483 : Node::InputEdges::iterator Node::InputEdges::end() const {
484 315931326 : return Node::InputEdges::iterator(use_root_ - count_, input_root_ + count_);
485 : }
486 :
487 : Edge Node::InputEdges::operator[](int index) const {
488 : return Edge(use_root_ + index, input_root_ + index);
489 : }
490 :
491 : // A forward iterator to visit the inputs of a node.
492 : class Node::Inputs::const_iterator final {
493 : public:
494 : typedef std::forward_iterator_tag iterator_category;
495 : typedef std::ptrdiff_t difference_type;
496 : typedef Node* value_type;
497 : typedef const value_type* pointer;
498 : typedef value_type& reference;
499 :
500 0 : const_iterator(const const_iterator& other) : input_ptr_(other.input_ptr_) {}
501 :
502 836224721 : Node* operator*() const { return *input_ptr_; }
503 : bool operator==(const const_iterator& other) const {
504 : return input_ptr_ == other.input_ptr_;
505 : }
506 : bool operator!=(const const_iterator& other) const {
507 : return !(*this == other);
508 : }
509 : const_iterator& operator++() {
510 827594563 : ++input_ptr_;
511 : return *this;
512 : }
513 : const_iterator operator++(int);
514 : const_iterator& operator+=(difference_type offset) {
515 : input_ptr_ += offset;
516 : return *this;
517 : }
518 : const_iterator operator+(difference_type offset) const {
519 : return const_iterator(input_ptr_ + offset);
520 : }
521 : difference_type operator-(const const_iterator& other) const {
522 : return input_ptr_ - other.input_ptr_;
523 : }
524 :
525 : private:
526 : friend class Node::Inputs;
527 :
528 0 : explicit const_iterator(Node* const* input_ptr) : input_ptr_(input_ptr) {}
529 :
530 : Node* const* input_ptr_;
531 : };
532 :
533 :
534 : Node::Inputs::const_iterator Node::Inputs::begin() const {
535 : return const_iterator(input_root_);
536 : }
537 :
538 :
539 : Node::Inputs::const_iterator Node::Inputs::end() const {
540 355110507 : return const_iterator(input_root_ + count_);
541 : }
542 :
543 2206503585 : Node* Node::Inputs::operator[](int index) const { return input_root_[index]; }
544 :
545 : // A forward iterator to visit the uses edges of a node.
546 : class Node::UseEdges::iterator final {
547 : public:
548 : iterator(const iterator& other)
549 10846017 : : current_(other.current_), next_(other.next_) {}
550 :
551 : Edge operator*() const { return Edge(current_, current_->input_ptr()); }
552 : bool operator==(const iterator& other) const {
553 5914 : return current_ == other.current_;
554 : }
555 26325760 : bool operator!=(const iterator& other) const { return !(*this == other); }
556 : iterator& operator++() {
557 : DCHECK_NOT_NULL(current_);
558 15479772 : current_ = next_;
559 1053350049 : next_ = current_ ? current_->next : nullptr;
560 : return *this;
561 : }
562 : iterator operator++(int);
563 :
564 : private:
565 : friend class Node::UseEdges;
566 :
567 : iterator() : current_(nullptr), next_(nullptr) {}
568 : explicit iterator(Node* node)
569 : : current_(node->first_use_),
570 411030264 : next_(current_ ? current_->next : nullptr) {}
571 :
572 : Node::Use* current_;
573 : Node::Use* next_;
574 : };
575 :
576 :
577 : Node::UseEdges::iterator Node::UseEdges::begin() const {
578 5914 : return Node::UseEdges::iterator(this->node_);
579 : }
580 :
581 :
582 : Node::UseEdges::iterator Node::UseEdges::end() const {
583 : return Node::UseEdges::iterator();
584 : }
585 :
586 :
587 : // A forward iterator to visit the uses of a node.
588 : class Node::Uses::const_iterator final {
589 : public:
590 : typedef std::forward_iterator_tag iterator_category;
591 : typedef int difference_type;
592 : typedef Node* value_type;
593 : typedef Node** pointer;
594 : typedef Node*& reference;
595 :
596 247580 : const_iterator(const const_iterator& other) : current_(other.current_) {}
597 :
598 247580 : Node* operator*() const { return current_->from(); }
599 : bool operator==(const const_iterator& other) const {
600 1750565 : return other.current_ == current_;
601 : }
602 : bool operator!=(const const_iterator& other) const {
603 25164 : return other.current_ != current_;
604 : }
605 : const_iterator& operator++() {
606 : DCHECK_NOT_NULL(current_);
607 450221497 : current_ = current_->next;
608 : return *this;
609 : }
610 : const_iterator operator++(int);
611 :
612 : private:
613 : friend class Node::Uses;
614 :
615 : const_iterator() : current_(nullptr) {}
616 173816612 : explicit const_iterator(Node* node) : current_(node->first_use_) {}
617 :
618 : Node::Use* current_;
619 : };
620 :
621 :
622 : Node::Uses::const_iterator Node::Uses::begin() const {
623 1750565 : return const_iterator(this->node_);
624 : }
625 :
626 :
627 : Node::Uses::const_iterator Node::Uses::end() const { return const_iterator(); }
628 :
629 : } // namespace compiler
630 : } // namespace internal
631 : } // namespace v8
632 :
633 : #endif // V8_COMPILER_NODE_H_
|
