node.cc

// 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.
    void* node_buffer = zone->New(sizeof(Node));
    node = new (node_buffer) Node(id, op, kOutlineMarker, 0);
    node->inputs_.outline_ = 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.
    int capacity = 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->inputs_.inline_;
    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->inputs_.inline_
                                  : node->inputs_.outline_->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);
      inputs_.outline_ = outline;
    } else {
      // use current out of line inputs.
      outline = inputs_.outline_;
      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);
        inputs_.outline_ = 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 {
    inputs_.outline_->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;
  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