src/compiler/node.cc - v8/v8 - Git at Google

 // Copyright 2013 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.

 #include "src/compiler/node.h"

 namespace v8 {
 namespace internal {
 namespace compiler {

 Node::OutOfLineInputs* Node::OutOfLineInputs::New(Zone* zone, int capacity) {
   size_t size =
       sizeof(OutOfLineInputs) + capacity * (sizeof(Node*) + sizeof(Use));
   intptr_t raw_buffer = reinterpret_cast<intptr_t>(zone->New(size));
   Node::OutOfLineInputs* outline =
       reinterpret_cast<OutOfLineInputs*>(raw_buffer + capacity * sizeof(Use));
   outline->capacity_ = capacity;
   outline->count_ = 0;
   return outline;
 }


 void Node::OutOfLineInputs::ExtractFrom(Use* old_use_ptr, Node** old_input_ptr,
                                         int count) {
   // Extract the inputs from the old use and input pointers and copy them
   // to this out-of-line-storage.
   Use* new_use_ptr = reinterpret_cast<Use*>(this) - 1;
   Node** new_input_ptr = inputs();
   for (int current = 0; current < count; current++) {
     new_use_ptr->bit_field_ =
         Use::InputIndexField::encode(current) | Use::InlineField::encode(false);
     DCHECK_EQ(old_input_ptr, old_use_ptr->input_ptr());
     DCHECK_EQ(new_input_ptr, new_use_ptr->input_ptr());
     Node* old_to = *old_input_ptr;
     if (old_to) {
       *old_input_ptr = nullptr;
       old_to->RemoveUse(old_use_ptr);
       *new_input_ptr = old_to;
       old_to->AppendUse(new_use_ptr);
     } else {
       *new_input_ptr = nullptr;
     }
     old_input_ptr++;
     new_input_ptr++;
     old_use_ptr--;
     new_use_ptr--;
   }
   this->count_ = count;
 }


 Node* Node::New(Zone* zone, NodeId id, const Operator* op, int input_count,
                 Node* const* inputs, bool has_extensible_inputs) {
   Node** input_ptr;
   Use* use_ptr;
   Node* node;
   bool is_inline;

 #if DEBUG
   // Verify that none of the inputs are {nullptr}.
   for (int i = 0; i < input_count; i++) {
     if (inputs[i] == nullptr) {
       FATAL("Node::New() Error: #%d:%s[%d] is nullptr", static_cast<int>(id),
             op->mnemonic(), i);
     }
   }
 #endif

   if (input_count > kMaxInlineCapacity) {
     // Allocate out-of-line inputs.
     int capacity =
         has_extensible_inputs ? input_count + kMaxInlineCapacity : input_count;
     OutOfLineInputs* outline = OutOfLineInputs::New(zone, capacity);

     // Allocate node, with space for OutOfLineInputs pointer.
     void* node_buffer = zone->New(sizeof(Node) + sizeof(OutOfLineInputs*));
     node = new (node_buffer) Node(id, op, kOutlineMarker, 0);
     node->set_outline_inputs(outline);

     outline->node_ = node;
     outline->count_ = input_count;

     input_ptr = outline->inputs();
     use_ptr = reinterpret_cast<Use*>(outline);
     is_inline = false;
   } else {
     // Allocate node with inline inputs. Capacity must be at least 1 so that
     // an OutOfLineInputs pointer can be stored when inputs are added later.
     int capacity = std::max(1, input_count);
     if (has_extensible_inputs) {
       const int max = kMaxInlineCapacity;
       capacity = std::min(input_count + 3, max);
     }

     size_t size = sizeof(Node) + capacity * (sizeof(Node*) + sizeof(Use));
     intptr_t raw_buffer = reinterpret_cast<intptr_t>(zone->New(size));
     void* node_buffer =
         reinterpret_cast<void*>(raw_buffer + capacity * sizeof(Use));

     node = new (node_buffer) Node(id, op, input_count, capacity);
     input_ptr = node->inline_inputs();
     use_ptr = reinterpret_cast<Use*>(node);
     is_inline = true;
   }

   // Initialize the input pointers and the uses.
   for (int current = 0; current < input_count; ++current) {
     Node* to = *inputs++;
     input_ptr[current] = to;
     Use* use = use_ptr - 1 - current;
     use->bit_field_ = Use::InputIndexField::encode(current) |
                       Use::InlineField::encode(is_inline);
     to->AppendUse(use);
   }
   node->Verify();
   return node;
 }


 Node* Node::Clone(Zone* zone, NodeId id, const Node* node) {
   int const input_count = node->InputCount();
   Node* const* const inputs = node->has_inline_inputs()
                                   ? node->inline_inputs()
                                   : node->outline_inputs()->inputs();
   Node* const clone = New(zone, id, node->op(), input_count, inputs, false);
   clone->set_type(node->type());
   return clone;
 }


 void Node::Kill() {
   DCHECK_NOT_NULL(op());
   NullAllInputs();
   DCHECK(uses().empty());
 }


 void Node::AppendInput(Zone* zone, Node* new_to) {
   DCHECK_NOT_NULL(zone);
   DCHECK_NOT_NULL(new_to);

   int inline_count = InlineCountField::decode(bit_field_);
   int inline_capacity = InlineCapacityField::decode(bit_field_);
   if (inline_count < inline_capacity) {
     // Append inline input.
     bit_field_ = InlineCountField::update(bit_field_, inline_count + 1);
     *GetInputPtr(inline_count) = new_to;
     Use* use = GetUsePtr(inline_count);
     use->bit_field_ = Use::InputIndexField::encode(inline_count) |
                       Use::InlineField::encode(true);
     new_to->AppendUse(use);
   } else {
     // Append out-of-line input.
     int input_count = InputCount();
     OutOfLineInputs* outline = nullptr;
     if (inline_count != kOutlineMarker) {
       // switch to out of line inputs.
       outline = OutOfLineInputs::New(zone, input_count * 2 + 3);
       outline->node_ = this;
       outline->ExtractFrom(GetUsePtr(0), GetInputPtr(0), input_count);
       bit_field_ = InlineCountField::update(bit_field_, kOutlineMarker);
       set_outline_inputs(outline);
     } else {
       // use current out of line inputs.
       outline = outline_inputs();
       if (input_count >= outline->capacity_) {
         // out of space in out-of-line inputs.
         outline = OutOfLineInputs::New(zone, input_count * 2 + 3);
         outline->node_ = this;
         outline->ExtractFrom(GetUsePtr(0), GetInputPtr(0), input_count);
         set_outline_inputs(outline);
       }
     }
     outline->count_++;
     *GetInputPtr(input_count) = new_to;
     Use* use = GetUsePtr(input_count);
     use->bit_field_ = Use::InputIndexField::encode(input_count) |
                       Use::InlineField::encode(false);
     new_to->AppendUse(use);
   }
   Verify();
 }


 void Node::InsertInput(Zone* zone, int index, Node* new_to) {
   DCHECK_NOT_NULL(zone);
   DCHECK_LE(0, index);
   DCHECK_LT(index, InputCount());
   AppendInput(zone, InputAt(InputCount() - 1));
   for (int i = InputCount() - 1; i > index; --i) {
     ReplaceInput(i, InputAt(i - 1));
   }
   ReplaceInput(index, new_to);
   Verify();
 }

 void Node::InsertInputs(Zone* zone, int index, int count) {
   DCHECK_NOT_NULL(zone);
   DCHECK_LE(0, index);
   DCHECK_LT(0, count);
   DCHECK_LT(index, InputCount());
   for (int i = 0; i < count; i++) {
     AppendInput(zone, InputAt(Max(InputCount() - count, 0)));
   }
   for (int i = InputCount() - count - 1; i >= Max(index, count); --i) {
     ReplaceInput(i, InputAt(i - count));
   }
   for (int i = 0; i < count; i++) {
     ReplaceInput(index + i, nullptr);
   }
   Verify();
 }

 void Node::RemoveInput(int index) {
   DCHECK_LE(0, index);
   DCHECK_LT(index, InputCount());
   for (; index < InputCount() - 1; ++index) {
     ReplaceInput(index, InputAt(index + 1));
   }
   TrimInputCount(InputCount() - 1);
   Verify();
 }


 void Node::ClearInputs(int start, int count) {
   Node** input_ptr = GetInputPtr(start);
   Use* use_ptr = GetUsePtr(start);
   while (count-- > 0) {
     DCHECK_EQ(input_ptr, use_ptr->input_ptr());
     Node* input = *input_ptr;
     *input_ptr = nullptr;
     if (input) input->RemoveUse(use_ptr);
     input_ptr++;
     use_ptr--;
   }
   Verify();
 }


 void Node::NullAllInputs() { ClearInputs(0, InputCount()); }


 void Node::TrimInputCount(int new_input_count) {
   int current_count = InputCount();
   DCHECK_LE(new_input_count, current_count);
   if (new_input_count == current_count) return;  // Nothing to do.
   ClearInputs(new_input_count, current_count - new_input_count);
   if (has_inline_inputs()) {
     bit_field_ = InlineCountField::update(bit_field_, new_input_count);
   } else {
     outline_inputs()->count_ = new_input_count;
   }
 }


 int Node::UseCount() const {
   int use_count = 0;
   for (const Use* use = first_use_; use; use = use->next) {
     ++use_count;
   }
   return use_count;
 }


 void Node::ReplaceUses(Node* that) {
   DCHECK(this->first_use_ == nullptr || this->first_use_->prev == nullptr);
   DCHECK(that->first_use_ == nullptr || that->first_use_->prev == nullptr);

   // Update the pointers to {this} to point to {that}.
   Use* last_use = nullptr;
   for (Use* use = this->first_use_; use; use = use->next) {
     *use->input_ptr() = that;
     last_use = use;
   }
   if (last_use) {
     // Concat the use list of {this} and {that}.
     last_use->next = that->first_use_;
     if (that->first_use_) that->first_use_->prev = last_use;
     that->first_use_ = this->first_use_;
   }
   first_use_ = nullptr;
 }


 bool Node::OwnedBy(Node const* owner1, Node const* owner2) const {
   unsigned mask = 0;
   for (Use* use = first_use_; use; use = use->next) {
     Node* from = use->from();
     if (from == owner1) {
       mask |= 1;
     } else if (from == owner2) {
       mask |= 2;
     } else {
       return false;
     }
   }
   return mask == 3;
 }

 void Node::Print() const {
   StdoutStream os;
   Print(os);
 }

 void Node::Print(std::ostream& os) const {
   os << *this << std::endl;
   for (Node* input : this->inputs()) {
     os << "  " << *input << std::endl;
   }
 }

 std::ostream& operator<<(std::ostream& os, const Node& n) {
   os << n.id() << ": " << *n.op();
   if (n.InputCount() > 0) {
     os << "(";
     for (int i = 0; i < n.InputCount(); ++i) {
       if (i != 0) os << ", ";
       if (n.InputAt(i)) {
         os << n.InputAt(i)->id();
       } else {
         os << "null";
       }
     }
     os << ")";
   }
   return os;
 }

 Node::Node(NodeId id, const Operator* op, int inline_count, int inline_capacity)
     : op_(op),
       mark_(0),
       bit_field_(IdField::encode(id) | InlineCountField::encode(inline_count) |
                  InlineCapacityField::encode(inline_capacity)),
       first_use_(nullptr) {
   // Inputs must either be out of line or within the inline capacity.
   DCHECK_GE(kMaxInlineCapacity, inline_capacity);
   DCHECK(inline_count == kOutlineMarker || inline_count <= inline_capacity);
 }


 void Node::AppendUse(Use* use) {
   DCHECK(first_use_ == nullptr || first_use_->prev == nullptr);
   DCHECK_EQ(this, *use->input_ptr());
   use->next = first_use_;
   use->prev = nullptr;
   if (first_use_) first_use_->prev = use;
   first_use_ = use;
 }


 void Node::RemoveUse(Use* use) {
   DCHECK(first_use_ == nullptr || first_use_->prev == nullptr);
   if (use->prev) {
     DCHECK_NE(first_use_, use);
     use->prev->next = use->next;
   } else {
     DCHECK_EQ(first_use_, use);
     first_use_ = use->next;
   }
   if (use->next) {
     use->next->prev = use->prev;
   }
 }


 #if DEBUG
 void Node::Verify() {
   // Check basic sanity of input data structures.
   fflush(stdout);
   int count = this->InputCount();
   // Avoid quadratic explosion for mega nodes; only verify if the input
   // count is less than 200 or is a round number of 100s.
   if (count > 200 && count % 100) return;

   for (int i = 0; i < count; i++) {
     DCHECK_EQ(i, this->GetUsePtr(i)->input_index());
     DCHECK_EQ(this->GetInputPtr(i), this->GetUsePtr(i)->input_ptr());
     DCHECK_EQ(count, this->InputCount());
   }
   {  // Direct input iteration.
     int index = 0;
     for (Node* input : this->inputs()) {
       DCHECK_EQ(this->InputAt(index), input);
       index++;
     }
     DCHECK_EQ(count, index);
     DCHECK_EQ(this->InputCount(), index);
   }
   {  // Input edge iteration.
     int index = 0;
     for (Edge edge : this->input_edges()) {
       DCHECK_EQ(edge.from(), this);
       DCHECK_EQ(index, edge.index());
       DCHECK_EQ(this->InputAt(index), edge.to());
       index++;
     }
     DCHECK_EQ(count, index);
     DCHECK_EQ(this->InputCount(), index);
   }
 }
 #endif

 Node::InputEdges::iterator Node::InputEdges::iterator::operator++(int n) {
   iterator result(*this);
   ++(*this);
   return result;
 }


 Node::Inputs::const_iterator Node::Inputs::const_iterator::operator++(int n) {
   const_iterator result(*this);
   ++(*this);
   return result;
 }


 Node::UseEdges::iterator Node::UseEdges::iterator::operator++(int n) {
   iterator result(*this);
   ++(*this);
   return result;
 }


 bool Node::UseEdges::empty() const { return begin() == end(); }


 Node::Uses::const_iterator Node::Uses::const_iterator::operator++(int n) {
   const_iterator result(*this);
   ++(*this);
   return result;
 }


 bool Node::Uses::empty() const { return begin() == end(); }

 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8
	// Copyright 2013 the V8 project authors. All rights reserved.
	// Use of this source code is governed by a BSD-style license that can be
	// found in the LICENSE file.

	#include "src/compiler/node.h"

	namespace v8 {
	namespace internal {
	namespace compiler {

	Node::OutOfLineInputs* Node::OutOfLineInputs::New(Zone* zone, int capacity) {
	size_t size =
	sizeof(OutOfLineInputs) + capacity * (sizeof(Node*) + sizeof(Use));
	intptr_t raw_buffer = reinterpret_cast<intptr_t>(zone->New(size));
	Node::OutOfLineInputs* outline =
	reinterpret_cast<OutOfLineInputs>(raw_buffer + capacity sizeof(Use));
	outline->capacity_ = capacity;
	outline->count_ = 0;
	return outline;
	}


	void Node::OutOfLineInputs::ExtractFrom(Use* old_use_ptr, Node** old_input_ptr,
	int count) {
	// Extract the inputs from the old use and input pointers and copy them
	// to this out-of-line-storage.
	Use* new_use_ptr = reinterpret_cast<Use*>(this) - 1;
	Node** new_input_ptr = inputs();
	for (int current = 0; current < count; current++) {
	new_use_ptr->bit_field_ =
	Use::InputIndexField::encode(current) \| Use::InlineField::encode(false);
	DCHECK_EQ(old_input_ptr, old_use_ptr->input_ptr());
	DCHECK_EQ(new_input_ptr, new_use_ptr->input_ptr());
	Node* old_to = *old_input_ptr;
	if (old_to) {
	*old_input_ptr = nullptr;
	old_to->RemoveUse(old_use_ptr);
	*new_input_ptr = old_to;
	old_to->AppendUse(new_use_ptr);
	} else {
	*new_input_ptr = nullptr;
	}
	old_input_ptr++;
	new_input_ptr++;
	old_use_ptr--;
	new_use_ptr--;
	}
	this->count_ = count;
	}


	Node* Node::New(Zone* zone, NodeId id, const Operator* op, int input_count,
	Node* const* inputs, bool has_extensible_inputs) {
	Node** input_ptr;
	Use* use_ptr;
	Node* node;
	bool is_inline;

	#if DEBUG
	// Verify that none of the inputs are {nullptr}.
	for (int i = 0; i < input_count; i++) {
	if (inputs[i] == nullptr) {
	FATAL("Node::New() Error: #%d:%s[%d] is nullptr", static_cast<int>(id),
	op->mnemonic(), i);
	}
	}
	#endif

	if (input_count > kMaxInlineCapacity) {
	// Allocate out-of-line inputs.
	int capacity =
	has_extensible_inputs ? input_count + kMaxInlineCapacity : input_count;
	OutOfLineInputs* outline = OutOfLineInputs::New(zone, capacity);

	// Allocate node, with space for OutOfLineInputs pointer.
	void* node_buffer = zone->New(sizeof(Node) + sizeof(OutOfLineInputs*));
	node = new (node_buffer) Node(id, op, kOutlineMarker, 0);
	node->set_outline_inputs(outline);

	outline->node_ = node;
	outline->count_ = input_count;

	input_ptr = outline->inputs();
	use_ptr = reinterpret_cast<Use*>(outline);
	is_inline = false;
	} else {
	// Allocate node with inline inputs. Capacity must be at least 1 so that
	// an OutOfLineInputs pointer can be stored when inputs are added later.
	int capacity = std::max(1, input_count);
	if (has_extensible_inputs) {
	const int max = kMaxInlineCapacity;
	capacity = std::min(input_count + 3, max);
	}

	size_t size = sizeof(Node) + capacity * (sizeof(Node*) + sizeof(Use));
	intptr_t raw_buffer = reinterpret_cast<intptr_t>(zone->New(size));
	void* node_buffer =
	reinterpret_cast<void>(raw_buffer + capacity sizeof(Use));

	node = new (node_buffer) Node(id, op, input_count, capacity);
	input_ptr = node->inline_inputs();
	use_ptr = reinterpret_cast<Use*>(node);
	is_inline = true;
	}

	// Initialize the input pointers and the uses.
	for (int current = 0; current < input_count; ++current) {
	Node* to = *inputs++;
	input_ptr[current] = to;
	Use* use = use_ptr - 1 - current;
	use->bit_field_ = Use::InputIndexField::encode(current) \|
	Use::InlineField::encode(is_inline);
	to->AppendUse(use);
	}
	node->Verify();
	return node;
	}


	Node* Node::Clone(Zone* zone, NodeId id, const Node* node) {
	int const input_count = node->InputCount();
	Node* const* const inputs = node->has_inline_inputs()
	? node->inline_inputs()
	: node->outline_inputs()->inputs();
	Node* const clone = New(zone, id, node->op(), input_count, inputs, false);
	clone->set_type(node->type());
	return clone;
	}


	void Node::Kill() {
	DCHECK_NOT_NULL(op());
	NullAllInputs();
	DCHECK(uses().empty());
	}


	void Node::AppendInput(Zone* zone, Node* new_to) {
	DCHECK_NOT_NULL(zone);
	DCHECK_NOT_NULL(new_to);

	int inline_count = InlineCountField::decode(bit_field_);
	int inline_capacity = InlineCapacityField::decode(bit_field_);
	if (inline_count < inline_capacity) {
	// Append inline input.
	bit_field_ = InlineCountField::update(bit_field_, inline_count + 1);
	*GetInputPtr(inline_count) = new_to;
	Use* use = GetUsePtr(inline_count);
	use->bit_field_ = Use::InputIndexField::encode(inline_count) \|
	Use::InlineField::encode(true);
	new_to->AppendUse(use);
	} else {
	// Append out-of-line input.
	int input_count = InputCount();
	OutOfLineInputs* outline = nullptr;
	if (inline_count != kOutlineMarker) {
	// switch to out of line inputs.
	outline = OutOfLineInputs::New(zone, input_count * 2 + 3);
	outline->node_ = this;
	outline->ExtractFrom(GetUsePtr(0), GetInputPtr(0), input_count);
	bit_field_ = InlineCountField::update(bit_field_, kOutlineMarker);
	set_outline_inputs(outline);
	} else {
	// use current out of line inputs.
	outline = outline_inputs();
	if (input_count >= outline->capacity_) {
	// out of space in out-of-line inputs.
	outline = OutOfLineInputs::New(zone, input_count * 2 + 3);
	outline->node_ = this;
	outline->ExtractFrom(GetUsePtr(0), GetInputPtr(0), input_count);
	set_outline_inputs(outline);
	}
	}
	outline->count_++;
	*GetInputPtr(input_count) = new_to;
	Use* use = GetUsePtr(input_count);
	use->bit_field_ = Use::InputIndexField::encode(input_count) \|
	Use::InlineField::encode(false);
	new_to->AppendUse(use);
	}
	Verify();
	}


	void Node::InsertInput(Zone* zone, int index, Node* new_to) {
	DCHECK_NOT_NULL(zone);
	DCHECK_LE(0, index);
	DCHECK_LT(index, InputCount());
	AppendInput(zone, InputAt(InputCount() - 1));
	for (int i = InputCount() - 1; i > index; --i) {
	ReplaceInput(i, InputAt(i - 1));
	}
	ReplaceInput(index, new_to);
	Verify();
	}

	void Node::InsertInputs(Zone* zone, int index, int count) {
	DCHECK_NOT_NULL(zone);
	DCHECK_LE(0, index);
	DCHECK_LT(0, count);
	DCHECK_LT(index, InputCount());
	for (int i = 0; i < count; i++) {
	AppendInput(zone, InputAt(Max(InputCount() - count, 0)));
	}
	for (int i = InputCount() - count - 1; i >= Max(index, count); --i) {
	ReplaceInput(i, InputAt(i - count));
	}
	for (int i = 0; i < count; i++) {
	ReplaceInput(index + i, nullptr);
	}
	Verify();
	}

	void Node::RemoveInput(int index) {
	DCHECK_LE(0, index);
	DCHECK_LT(index, InputCount());
	for (; index < InputCount() - 1; ++index) {
	ReplaceInput(index, InputAt(index + 1));
	}
	TrimInputCount(InputCount() - 1);
	Verify();
	}


	void Node::ClearInputs(int start, int count) {
	Node** input_ptr = GetInputPtr(start);
	Use* use_ptr = GetUsePtr(start);
	while (count-- > 0) {
	DCHECK_EQ(input_ptr, use_ptr->input_ptr());
	Node* input = *input_ptr;
	*input_ptr = nullptr;
	if (input) input->RemoveUse(use_ptr);
	input_ptr++;
	use_ptr--;
	}
	Verify();
	}


	void Node::NullAllInputs() { ClearInputs(0, InputCount()); }


	void Node::TrimInputCount(int new_input_count) {
	int current_count = InputCount();
	DCHECK_LE(new_input_count, current_count);
	if (new_input_count == current_count) return; // Nothing to do.
	ClearInputs(new_input_count, current_count - new_input_count);
	if (has_inline_inputs()) {
	bit_field_ = InlineCountField::update(bit_field_, new_input_count);
	} else {
	outline_inputs()->count_ = new_input_count;
	}
	}


	int Node::UseCount() const {
	int use_count = 0;
	for (const Use* use = first_use_; use; use = use->next) {
	++use_count;
	}
	return use_count;
	}


	void Node::ReplaceUses(Node* that) {
	DCHECK(this->first_use_ == nullptr \|\| this->first_use_->prev == nullptr);
	DCHECK(that->first_use_ == nullptr \|\| that->first_use_->prev == nullptr);

	// Update the pointers to {this} to point to {that}.
	Use* last_use = nullptr;
	for (Use* use = this->first_use_; use; use = use->next) {
	*use->input_ptr() = that;
	last_use = use;
	}
	if (last_use) {
	// Concat the use list of {this} and {that}.
	last_use->next = that->first_use_;
	if (that->first_use_) that->first_use_->prev = last_use;
	that->first_use_ = this->first_use_;
	}
	first_use_ = nullptr;
	}


	bool Node::OwnedBy(Node const* owner1, Node const* owner2) const {
	unsigned mask = 0;
	for (Use* use = first_use_; use; use = use->next) {
	Node* from = use->from();
	if (from == owner1) {
	mask \|= 1;
	} else if (from == owner2) {
	mask \|= 2;
	} else {
	return false;
	}
	}
	return mask == 3;
	}

	void Node::Print() const {
	StdoutStream os;
	Print(os);
	}

	void Node::Print(std::ostream& os) const {
	os << *this << std::endl;
	for (Node* input : this->inputs()) {
	os << " " << *input << std::endl;
	}
	}

	std::ostream& operator<<(std::ostream& os, const Node& n) {
	os << n.id() << ": " << *n.op();
	if (n.InputCount() > 0) {
	os << "(";
	for (int i = 0; i < n.InputCount(); ++i) {
	if (i != 0) os << ", ";
	if (n.InputAt(i)) {
	os << n.InputAt(i)->id();
	} else {
	os << "null";
	}
	}
	os << ")";
	}
	return os;
	}

	Node::Node(NodeId id, const Operator* op, int inline_count, int inline_capacity)
	: op_(op),
	mark_(0),
	bit_field_(IdField::encode(id) \| InlineCountField::encode(inline_count) \|
	InlineCapacityField::encode(inline_capacity)),
	first_use_(nullptr) {
	// Inputs must either be out of line or within the inline capacity.
	DCHECK_GE(kMaxInlineCapacity, inline_capacity);
	DCHECK(inline_count == kOutlineMarker \|\| inline_count <= inline_capacity);
	}


	void Node::AppendUse(Use* use) {
	DCHECK(first_use_ == nullptr \|\| first_use_->prev == nullptr);
	DCHECK_EQ(this, *use->input_ptr());
	use->next = first_use_;
	use->prev = nullptr;
	if (first_use_) first_use_->prev = use;
	first_use_ = use;
	}


	void Node::RemoveUse(Use* use) {
	DCHECK(first_use_ == nullptr \|\| first_use_->prev == nullptr);
	if (use->prev) {
	DCHECK_NE(first_use_, use);
	use->prev->next = use->next;
	} else {
	DCHECK_EQ(first_use_, use);
	first_use_ = use->next;
	}
	if (use->next) {
	use->next->prev = use->prev;
	}
	}


	#if DEBUG
	void Node::Verify() {
	// Check basic sanity of input data structures.
	fflush(stdout);
	int count = this->InputCount();
	// Avoid quadratic explosion for mega nodes; only verify if the input
	// count is less than 200 or is a round number of 100s.
	if (count > 200 && count % 100) return;

	for (int i = 0; i < count; i++) {
	DCHECK_EQ(i, this->GetUsePtr(i)->input_index());
	DCHECK_EQ(this->GetInputPtr(i), this->GetUsePtr(i)->input_ptr());
	DCHECK_EQ(count, this->InputCount());
	}
	{ // Direct input iteration.
	int index = 0;
	for (Node* input : this->inputs()) {
	DCHECK_EQ(this->InputAt(index), input);
	index++;
	}
	DCHECK_EQ(count, index);
	DCHECK_EQ(this->InputCount(), index);
	}
	{ // Input edge iteration.
	int index = 0;
	for (Edge edge : this->input_edges()) {
	DCHECK_EQ(edge.from(), this);
	DCHECK_EQ(index, edge.index());
	DCHECK_EQ(this->InputAt(index), edge.to());
	index++;
	}
	DCHECK_EQ(count, index);
	DCHECK_EQ(this->InputCount(), index);
	}
	}
	#endif

	Node::InputEdges::iterator Node::InputEdges::iterator::operator++(int n) {
	iterator result(*this);
	++(*this);
	return result;
	}


	Node::Inputs::const_iterator Node::Inputs::const_iterator::operator++(int n) {
	const_iterator result(*this);
	++(*this);
	return result;
	}


	Node::UseEdges::iterator Node::UseEdges::iterator::operator++(int n) {
	iterator result(*this);
	++(*this);
	return result;
	}


	bool Node::UseEdges::empty() const { return begin() == end(); }


	Node::Uses::const_iterator Node::Uses::const_iterator::operator++(int n) {
	const_iterator result(*this);
	++(*this);
	return result;
	}


	bool Node::Uses::empty() const { return begin() == end(); }

	} // namespace compiler
	} // namespace internal
	} // namespace v8