5 #ifndef V8_COMPILER_NODE_H_ 6 #define V8_COMPILER_NODE_H_ 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" 43 class V8_EXPORT_PRIVATE
Node final {
46 Node*
const* inputs,
bool has_extensible_inputs);
49 inline bool IsDead()
const;
52 const Operator* op()
const {
return op_; }
54 IrOpcode::Value opcode()
const {
55 DCHECK_GE(IrOpcode::kLast, op_->opcode());
56 return static_cast<IrOpcode::Value
>(op_->opcode());
59 NodeId id()
const {
return IdField::decode(bit_field_); }
61 int InputCount()
const {
62 return has_inline_inputs() ? InlineCountField::decode(bit_field_)
63 : inputs_.outline_->count_;
68 #define BOUNDS_CHECK(index) \ 70 if (index < 0 || index >= InputCount()) { \ 71 FATAL("Node #%d:%s->InputAt(%d) out of bounds", id(), op()->mnemonic(), \ 77 inline void Verify() {}
78 #define BOUNDS_CHECK(index) \ 83 Node* InputAt(
int index)
const {
85 return *GetInputPtrConst(index);
88 void ReplaceInput(
int index,
Node* new_to) {
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);
96 if (new_to) new_to->AppendUse(use);
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);
109 int UseCount()
const;
110 void ReplaceUses(
Node* replace_to);
116 inline Inputs inputs()
const;
136 class V8_EXPORT_PRIVATE
Uses final {
146 explicit Uses(
Node* node) : node_(node) {}
155 bool OwnedBy(
Node* owner)
const {
156 return first_use_ && first_use_->from() == owner && !first_use_->next;
160 bool OwnedBy(
Node const* owner1,
Node const* owner2)
const;
168 struct OutOfLineInputs {
174 static OutOfLineInputs* New(
Zone* zone,
int capacity);
175 void ExtractFrom(Use* use_ptr,
Node** input_ptr,
int count);
185 int input_index()
const {
return InputIndexField::decode(bit_field_); }
186 bool is_inline_use()
const {
return InlineField::decode(bit_field_); }
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];
197 Use* start =
this + 1 + input_index();
198 return is_inline_use() ?
reinterpret_cast<Node*
>(start)
199 : reinterpret_cast<OutOfLineInputs*>(start)->node_;
202 typedef BitField<bool, 0, 1> InlineField;
203 typedef BitField<unsigned, 1, 17> InputIndexField;
239 Node(NodeId
id,
const Operator* op,
int inline_count,
int inline_capacity);
241 Node*
const* GetInputPtrConst(
int input_index)
const {
242 return has_inline_inputs() ? &(inputs_.inline_[input_index])
243 : &inputs_.outline_->inputs_[input_index];
245 Node** GetInputPtr(
int input_index) {
246 return has_inline_inputs() ? &(inputs_.inline_[input_index])
247 : &inputs_.outline_->inputs_[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];
255 void AppendUse(Use* use);
256 void RemoveUse(Use* use);
258 void*
operator new(
size_t,
void* location) {
return location; }
261 void set_op(
const Operator* op) { op_ = op; }
264 Type type()
const {
return type_; }
265 void set_type(
Type type) { type_ = type; }
268 Mark mark()
const {
return mark_; }
269 void set_mark(Mark mark) { mark_ = mark; }
271 inline bool has_inline_inputs()
const {
272 return InlineCountField::decode(bit_field_) != kOutlineMarker;
275 void ClearInputs(
int start,
int count);
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;
292 OutOfLineInputs* outline_;
296 friend class NodeMarkerBase;
297 friend class NodeProperties;
299 DISALLOW_COPY_AND_ASSIGN(Node);
303 std::ostream& operator<<(std::ostream& os,
const Node& n);
307 typedef ZoneDeque<Node*> NodeDeque;
308 typedef ZoneSet<Node*> NodeSet;
309 typedef ZoneVector<Node*> NodeVector;
310 typedef ZoneVector<NodeVector> NodeVectorVector;
321 bool empty()
const {
return count_ == 0; }
322 int count()
const {
return count_; }
324 inline value_type operator[](
int index)
const;
327 : input_root_(input_root), use_root_(use_root), count_(count) {}
335 class V8_EXPORT_PRIVATE
Node::Inputs final {
339 class const_iterator;
340 inline const_iterator begin()
const;
341 inline const_iterator end()
const;
343 bool empty()
const {
return count_ == 0; }
344 int count()
const {
return count_; }
346 inline value_type operator[](
int index)
const;
348 explicit Inputs(
Node*
const* input_root,
int count)
349 : input_root_(input_root), count_(count) {}
352 Node*
const* input_root_;
361 Node* from()
const {
return use_->from(); }
362 Node* to()
const {
return *input_ptr_; }
364 int const index = use_->input_index();
365 DCHECK_LT(index, use_->from()->InputCount());
369 bool operator==(
const Edge& other) {
return input_ptr_ == other.input_ptr_; }
370 bool operator!=(
const Edge& other) {
return !(*
this == other); }
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_);
382 friend class Node::UseEdges::iterator;
384 friend class Node::InputEdges::iterator;
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());
396 bool Node::IsDead()
const {
397 Node::Inputs inputs = this->inputs();
398 return inputs.count() > 0 && inputs[0] ==
nullptr;
402 int inline_count = InlineCountField::decode(bit_field_);
403 if (inline_count != kOutlineMarker) {
404 return InputEdges(inputs_.inline_, reinterpret_cast<Use*>(
this) - 1,
407 return InputEdges(inputs_.outline_->inputs_,
408 reinterpret_cast<Use*>(inputs_.outline_) - 1,
409 inputs_.outline_->count_);
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);
418 return Inputs(inputs_.outline_->inputs_, inputs_.outline_->count_);
423 class Node::InputEdges::iterator final {
425 typedef std::forward_iterator_tag iterator_category;
426 typedef std::ptrdiff_t difference_type;
431 iterator() : use_(
nullptr), input_ptr_(
nullptr) {}
434 Edge operator*()
const {
return Edge(use_, input_ptr_); }
435 bool operator==(
const iterator& other)
const {
436 return input_ptr_ == other.input_ptr_;
438 bool operator!=(
const iterator& other)
const {
return !(*
this == other); }
445 iterator& operator+=(difference_type offset) {
446 input_ptr_ += offset;
450 iterator operator+(difference_type offset)
const {
451 return iterator(use_ - offset, input_ptr_ + offset);
453 difference_type operator-(
const iterator& other)
const {
454 return input_ptr_ - other.input_ptr_;
461 : use_(use), input_ptr_(input_ptr) {}
468 Node::InputEdges::iterator Node::InputEdges::begin()
const {
469 return Node::InputEdges::iterator(use_root_, input_root_);
473 Node::InputEdges::iterator Node::InputEdges::end()
const {
474 return Node::InputEdges::iterator(use_root_ - count_, input_root_ + count_);
477 Edge Node::InputEdges::operator[](
int index)
const {
478 return Edge(use_root_ + index, input_root_ + index);
482 class Node::Inputs::const_iterator final {
484 typedef std::forward_iterator_tag iterator_category;
485 typedef std::ptrdiff_t difference_type;
492 Node* operator*()
const {
return *input_ptr_; }
494 return input_ptr_ == other.input_ptr_;
497 return !(*
this == other);
505 input_ptr_ += offset;
512 return input_ptr_ - other.input_ptr_;
516 friend class Node::Inputs;
520 Node*
const* input_ptr_;
524 Node::Inputs::const_iterator Node::Inputs::begin()
const {
529 Node::Inputs::const_iterator Node::Inputs::end()
const {
530 return const_iterator(input_root_ + count_);
533 Node* Node::Inputs::operator[](
int index)
const {
return input_root_[index]; }
536 class Node::UseEdges::iterator final {
540 Edge operator*()
const {
return Edge(current_, current_->input_ptr()); }
541 bool operator==(
const iterator& other)
const {
542 return current_ == other.current_;
544 bool operator!=(
const iterator& other)
const {
return !(*
this == other); }
546 DCHECK_NOT_NULL(current_);
548 next_ = current_ ? current_->next :
nullptr;
556 iterator() : current_(
nullptr), next_(
nullptr) {}
558 : current_(node->first_use_),
559 next_(current_ ? current_->next :
nullptr) {}
566 Node::UseEdges::iterator Node::UseEdges::begin()
const {
567 return Node::UseEdges::iterator(this->node_);
571 Node::UseEdges::iterator Node::UseEdges::end()
const {
572 return Node::UseEdges::iterator();
577 class Node::Uses::const_iterator final {
579 typedef std::forward_iterator_tag iterator_category;
585 Node* operator*()
const {
return current_->from(); }
587 return other.current_ == current_;
590 return other.current_ != current_;
593 DCHECK_NOT_NULL(current_);
596 current_ = current_->next;
598 DCHECK_EQ(current_, next_);
599 next_ = current_ ? current_->next :
nullptr;
610 : current_(node->first_use_)
613 next_(current_ ? current_->next :
nullptr)
625 Node::Uses::const_iterator Node::Uses::begin()
const {
630 Node::Uses::const_iterator Node::Uses::end()
const {
return const_iterator(); }
636 #endif // V8_COMPILER_NODE_H_