[turbofan] Cache for reusing value vector nodes in frame states.

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_.Lookup(&key, hash, true, 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 (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 = 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) {
+      // 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);
+}
+
+
+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;
+}
+
+
+Node* StateValuesAccess::iterator::operator*() { return node(); }
+
+
+size_t StateValuesAccess::size() {
+  size_t count = 0;
+  for (int i = 0; i < node_->InputCount(); i++) {
+    if (node_->InputAt(i)->opcode() == IrOpcode::kStateValues) {
+      count += StateValuesAccess(node_->InputAt(i)).size();
+    } else {
+      count++;
+    }
+  }
+  return count;
+}
+
+}  // namespace compiler
+}  // namespace internal
+}  // namespace v8