src/compiler/state-values-utils.cc

// Copyright 2015 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/state-values-utils.h"

namespace v8 {
namespace internal {
namespace compiler {

StateValuesCache::StateValuesCache(JSGraph* js_graph)
    : js_graph_(js_graph),
      hash_map_(AreKeysEqual, ZoneHashMap::kDefaultHashMapCapacity,
                ZoneAllocationPolicy(zone())),
      working_space_(zone()),
      empty_state_values_(nullptr) {}


// static
bool StateValuesCache::AreKeysEqual(void* key1, void* key2) {
  NodeKey* node_key1 = reinterpret_cast<NodeKey*>(key1);
  NodeKey* node_key2 = reinterpret_cast<NodeKey*>(key2);

  if (node_key1->node == nullptr) {
    if (node_key2->node == nullptr) {
      return AreValueKeysEqual(reinterpret_cast<StateValuesKey*>(key1),
                               reinterpret_cast<StateValuesKey*>(key2));
    } else {
      return IsKeysEqualToNode(reinterpret_cast<StateValuesKey*>(key1),
                               node_key2->node);
    }
  } else {
    if (node_key2->node == nullptr) {
      // If the nodes are already processed, they must be the same.
      return IsKeysEqualToNode(reinterpret_cast<StateValuesKey*>(key2),
                               node_key1->node);
    } else {
      return node_key1->node == node_key2->node;
    }
  }
  UNREACHABLE();
}


// static
bool StateValuesCache::IsKeysEqualToNode(StateValuesKey* key, Node* node) {
  if (key->count != static_cast<size_t>(node->InputCount())) {
    return false;
  }
  for (size_t i = 0; i < key->count; i++) {
    if (key->values[i] != node->InputAt(static_cast<int>(i))) {
      return false;
    }
  }
  return true;
}


// static
bool StateValuesCache::AreValueKeysEqual(StateValuesKey* key1,
                                         StateValuesKey* key2) {
  if (key1->count != key2->count) {
    return false;
  }
  for (size_t i = 0; i < key1->count; i++) {
    if (key1->values[i] != key2->values[i]) {
      return false;
    }
  }
  return true;
}


Node* StateValuesCache::GetEmptyStateValues() {
  if (empty_state_values_ == nullptr) {
    empty_state_values_ = graph()->NewNode(common()->StateValues(0));
  }
  return empty_state_values_;
}


NodeVector* StateValuesCache::GetWorkingSpace(size_t level) {
  while (working_space_.size() <= level) {
    void* space = zone()->New(sizeof(NodeVector));
    working_space_.push_back(new (space)
                                 NodeVector(kMaxInputCount, nullptr, zone()));
  }
  return working_space_[level];
}

namespace {

int StateValuesHashKey(Node** nodes, size_t count) {
  size_t hash = count;
  for (size_t i = 0; i < count; i++) {
    hash = hash * 23 + nodes[i]->id();
  }
  return static_cast<int>(hash & 0x7fffffff);
}

}  // namespace


Node* StateValuesCache::GetValuesNodeFromCache(Node** nodes, size_t count) {
  StateValuesKey key(count, nodes);
  int hash = StateValuesHashKey(nodes, count);
  ZoneHashMap::Entry* lookup =
      hash_map_.LookupOrInsert(&key, hash, ZoneAllocationPolicy(zone()));
  DCHECK_NOT_NULL(lookup);
  Node* node;
  if (lookup->value == nullptr) {
    int input_count = static_cast<int>(count);
    node = graph()->NewNode(common()->StateValues(input_count), input_count,
                            nodes);
    NodeKey* new_key = new (zone()->New(sizeof(NodeKey))) NodeKey(node);
    lookup->key = new_key;
    lookup->value = node;
  } else {
    node = reinterpret_cast<Node*>(lookup->value);
  }
  return node;
}


class StateValuesCache::ValueArrayIterator {
 public:
  ValueArrayIterator(Node** values, size_t count)
      : values_(values), count_(count), current_(0) {}

  void Advance() {
    if (!done()) {
      current_++;
    }
  }

  bool done() { return current_ >= count_; }

  Node* node() {
    DCHECK(!done());
    return values_[current_];
  }

 private:
  Node** values_;
  size_t count_;
  size_t current_;
};


Node* StateValuesCache::BuildTree(ValueArrayIterator* it, size_t max_height) {
  if (max_height == 0) {
    Node* node = it->node();
    it->Advance();
    return node;
  }
  DCHECK(!it->done());

  NodeVector* buffer = GetWorkingSpace(max_height);
  size_t count = 0;
  for (; count < kMaxInputCount; count++) {
    if (it->done()) break;
    (*buffer)[count] = BuildTree(it, max_height - 1);
  }
  if (count == 1) {
    return (*buffer)[0];
  } else {
    return GetValuesNodeFromCache(&(buffer->front()), count);
  }
}


Node* StateValuesCache::GetNodeForValues(Node** values, size_t count) {
#if DEBUG
  for (size_t i = 0; i < count; i++) {
    DCHECK_NE(values[i]->opcode(), IrOpcode::kStateValues);
    DCHECK_NE(values[i]->opcode(), IrOpcode::kTypedStateValues);
  }
#endif
  if (count == 0) {
    return GetEmptyStateValues();
  }
  size_t height = 0;
  size_t max_nodes = 1;
  while (count > max_nodes) {
    height++;
    max_nodes *= kMaxInputCount;
  }

  ValueArrayIterator it(values, count);

  Node* tree = BuildTree(&it, height);

  // If the 'tree' is a single node, equip it with a StateValues wrapper.
  if (tree->opcode() != IrOpcode::kStateValues &&
      tree->opcode() != IrOpcode::kTypedStateValues) {
    tree = GetValuesNodeFromCache(&tree, 1);
  }

  return tree;
}


StateValuesAccess::iterator::iterator(Node* node) : current_depth_(0) {
  // A hacky way initialize - just set the index before the node we want
  // to process and then advance to it.
  stack_[current_depth_].node = node;
  stack_[current_depth_].index = -1;
  Advance();
}


StateValuesAccess::iterator::StatePos* StateValuesAccess::iterator::Top() {
  DCHECK(current_depth_ >= 0);
  DCHECK(current_depth_ < kMaxInlineDepth);
  return &(stack_[current_depth_]);
}


void StateValuesAccess::iterator::Push(Node* node) {
  current_depth_++;
  CHECK(current_depth_ < kMaxInlineDepth);
  stack_[current_depth_].node = node;
  stack_[current_depth_].index = 0;
}


void StateValuesAccess::iterator::Pop() {
  DCHECK(current_depth_ >= 0);
  current_depth_--;
}


bool StateValuesAccess::iterator::done() { return current_depth_ < 0; }


void StateValuesAccess::iterator::Advance() {
  // Advance the current index.
  Top()->index++;

  // Fix up the position to point to a valid node.
  while (true) {
    // TODO(jarin): Factor to a separate method.
    Node* node = Top()->node;
    int index = Top()->index;

    if (index >= node->InputCount()) {
      // Pop stack and move to the next sibling.
      Pop();
      if (done()) {
        // Stack is exhausted, we have reached the end.
        return;
      }
      Top()->index++;
    } else if (node->InputAt(index)->opcode() == IrOpcode::kStateValues ||
               node->InputAt(index)->opcode() == IrOpcode::kTypedStateValues) {
      // Nested state, we need to push to the stack.
      Push(node->InputAt(index));
    } else {
      // We are on a valid node, we can stop the iteration.
      return;
    }
  }
}


Node* StateValuesAccess::iterator::node() {
  return Top()->node->InputAt(Top()->index);
}


MachineType StateValuesAccess::iterator::type() {
  Node* state = Top()->node;
  if (state->opcode() == IrOpcode::kStateValues) {
    return MachineType::AnyTagged();
  } else {
    DCHECK_EQ(IrOpcode::kTypedStateValues, state->opcode());
    ZoneVector<MachineType> const* types = MachineTypesOf(state->op());
    return (*types)[Top()->index];
  }
}


bool StateValuesAccess::iterator::operator!=(iterator& other) {
  // We only allow comparison with end().
  CHECK(other.done());
  return !done();
}


StateValuesAccess::iterator& StateValuesAccess::iterator::operator++() {
  Advance();
  return *this;
}


StateValuesAccess::TypedNode StateValuesAccess::iterator::operator*() {
  return TypedNode(node(), type());
}


size_t StateValuesAccess::size() {
  size_t count = 0;
  for (int i = 0; i < node_->InputCount(); i++) {
    if (node_->InputAt(i)->opcode() == IrOpcode::kStateValues ||
        node_->InputAt(i)->opcode() == IrOpcode::kTypedStateValues) {
      count += StateValuesAccess(node_->InputAt(i)).size();
    } else {
      count++;
    }
  }
  return count;
}

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