| // 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" |
| |
| #include "src/bit-vector.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; |
| } |
| |
| DCHECK_EQ(IrOpcode::kStateValues, node->opcode()); |
| SparseInputMask node_mask = SparseInputMaskOf(node->op()); |
| |
| if (node_mask != key->mask) { |
| return false; |
| } |
| |
| // Comparing real inputs rather than sparse inputs, since we already know the |
| // sparse input masks are the same. |
| 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; |
| } |
| if (key1->mask != key2->mask) { |
| 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, SparseInputMask::Dense())); |
| } |
| return empty_state_values_; |
| } |
| |
| StateValuesCache::WorkingBuffer* StateValuesCache::GetWorkingSpace( |
| size_t level) { |
| if (working_space_.size() <= level) { |
| working_space_.resize(level + 1); |
| } |
| 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] == nullptr ? 0 : nodes[i]->id()); |
| } |
| return static_cast<int>(hash & 0x7FFFFFFF); |
| } |
| |
| } // namespace |
| |
| Node* StateValuesCache::GetValuesNodeFromCache(Node** nodes, size_t count, |
| SparseInputMask mask) { |
| StateValuesKey key(count, mask, 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 node_count = static_cast<int>(count); |
| node = graph()->NewNode(common()->StateValues(node_count, mask), node_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; |
| } |
| |
| SparseInputMask::BitMaskType StateValuesCache::FillBufferWithValues( |
| WorkingBuffer* node_buffer, size_t* node_count, size_t* values_idx, |
| Node** values, size_t count, const BitVector* liveness, |
| int liveness_offset) { |
| SparseInputMask::BitMaskType input_mask = 0; |
| |
| // Virtual nodes are the live nodes plus the implicit optimized out nodes, |
| // which are implied by the liveness mask. |
| size_t virtual_node_count = *node_count; |
| |
| while (*values_idx < count && *node_count < kMaxInputCount && |
| virtual_node_count < SparseInputMask::kMaxSparseInputs) { |
| DCHECK_LE(*values_idx, static_cast<size_t>(INT_MAX)); |
| |
| if (liveness == nullptr || |
| liveness->Contains(liveness_offset + static_cast<int>(*values_idx))) { |
| input_mask |= 1 << (virtual_node_count); |
| (*node_buffer)[(*node_count)++] = values[*values_idx]; |
| } |
| virtual_node_count++; |
| |
| (*values_idx)++; |
| } |
| |
| DCHECK_GE(StateValuesCache::kMaxInputCount, *node_count); |
| DCHECK_GE(SparseInputMask::kMaxSparseInputs, virtual_node_count); |
| |
| // Add the end marker at the end of the mask. |
| input_mask |= SparseInputMask::kEndMarker << virtual_node_count; |
| |
| return input_mask; |
| } |
| |
| Node* StateValuesCache::BuildTree(size_t* values_idx, Node** values, |
| size_t count, const BitVector* liveness, |
| int liveness_offset, size_t level) { |
| WorkingBuffer* node_buffer = GetWorkingSpace(level); |
| size_t node_count = 0; |
| SparseInputMask::BitMaskType input_mask = SparseInputMask::kDenseBitMask; |
| |
| if (level == 0) { |
| input_mask = FillBufferWithValues(node_buffer, &node_count, values_idx, |
| values, count, liveness, liveness_offset); |
| // Make sure we returned a sparse input mask. |
| DCHECK_NE(input_mask, SparseInputMask::kDenseBitMask); |
| } else { |
| while (*values_idx < count && node_count < kMaxInputCount) { |
| if (count - *values_idx < kMaxInputCount - node_count) { |
| // If we have fewer values remaining than inputs remaining, dump the |
| // remaining values into this node. |
| // TODO(leszeks): We could optimise this further by only counting |
| // remaining live nodes. |
| |
| size_t previous_input_count = node_count; |
| input_mask = |
| FillBufferWithValues(node_buffer, &node_count, values_idx, values, |
| count, liveness, liveness_offset); |
| // Make sure we have exhausted our values. |
| DCHECK_EQ(*values_idx, count); |
| // Make sure we returned a sparse input mask. |
| DCHECK_NE(input_mask, SparseInputMask::kDenseBitMask); |
| |
| // Make sure we haven't touched inputs below previous_input_count in the |
| // mask. |
| DCHECK_EQ(input_mask & ((1 << previous_input_count) - 1), 0u); |
| // Mark all previous inputs as live. |
| input_mask |= ((1 << previous_input_count) - 1); |
| |
| break; |
| |
| } else { |
| // Otherwise, add the values to a subtree and add that as an input. |
| Node* subtree = BuildTree(values_idx, values, count, liveness, |
| liveness_offset, level - 1); |
| (*node_buffer)[node_count++] = subtree; |
| // Don't touch the bitmask, so that it stays dense. |
| } |
| } |
| } |
| |
| if (node_count == 1 && input_mask == SparseInputMask::kDenseBitMask) { |
| // Elide the StateValue node if there is only one, dense input. This will |
| // only happen if we built a single subtree (as nodes with values are always |
| // sparse), and so we can replace ourselves with it. |
| DCHECK_EQ((*node_buffer)[0]->opcode(), IrOpcode::kStateValues); |
| return (*node_buffer)[0]; |
| } else { |
| return GetValuesNodeFromCache(node_buffer->data(), node_count, |
| SparseInputMask(input_mask)); |
| } |
| } |
| |
| #if DEBUG |
| namespace { |
| |
| void CheckTreeContainsValues(Node* tree, Node** values, size_t count, |
| const BitVector* liveness, int liveness_offset) { |
| DCHECK_EQ(count, StateValuesAccess(tree).size()); |
| |
| int i; |
| auto access = StateValuesAccess(tree); |
| auto it = access.begin(); |
| auto itend = access.end(); |
| for (i = 0; it != itend; ++it, ++i) { |
| if (liveness == nullptr || liveness->Contains(liveness_offset + i)) { |
| DCHECK_EQ((*it).node, values[i]); |
| } else { |
| DCHECK_NULL((*it).node); |
| } |
| } |
| DCHECK_EQ(static_cast<size_t>(i), count); |
| } |
| |
| } // namespace |
| #endif |
| |
| Node* StateValuesCache::GetNodeForValues(Node** values, size_t count, |
| const BitVector* liveness, |
| int liveness_offset) { |
| #if DEBUG |
| // Check that the values represent actual values, and not a tree of values. |
| for (size_t i = 0; i < count; i++) { |
| if (values[i] != nullptr) { |
| DCHECK_NE(values[i]->opcode(), IrOpcode::kStateValues); |
| DCHECK_NE(values[i]->opcode(), IrOpcode::kTypedStateValues); |
| } |
| } |
| if (liveness != nullptr) { |
| DCHECK_LE(liveness_offset + count, static_cast<size_t>(liveness->length())); |
| |
| for (size_t i = 0; i < count; i++) { |
| if (liveness->Contains(liveness_offset + static_cast<int>(i))) { |
| DCHECK_NOT_NULL(values[i]); |
| } |
| } |
| } |
| #endif |
| |
| if (count == 0) { |
| return GetEmptyStateValues(); |
| } |
| |
| // This is a worst-case tree height estimate, assuming that all values are |
| // live. We could get a better estimate by counting zeroes in the liveness |
| // vector, but there's no point -- any excess height in the tree will be |
| // collapsed by the single-input elision at the end of BuildTree. |
| size_t height = 0; |
| size_t max_inputs = kMaxInputCount; |
| while (count > max_inputs) { |
| height++; |
| max_inputs *= kMaxInputCount; |
| } |
| |
| size_t values_idx = 0; |
| Node* tree = |
| BuildTree(&values_idx, values, count, liveness, liveness_offset, height); |
| // The values should be exhausted by the end of BuildTree. |
| DCHECK_EQ(values_idx, count); |
| |
| // The 'tree' must be rooted with a state value node. |
| DCHECK_EQ(tree->opcode(), IrOpcode::kStateValues); |
| |
| #if DEBUG |
| CheckTreeContainsValues(tree, values, count, liveness, liveness_offset); |
| #endif |
| |
| return tree; |
| } |
| |
| StateValuesAccess::iterator::iterator(Node* node) : current_depth_(0) { |
| stack_[current_depth_] = |
| SparseInputMaskOf(node->op()).IterateOverInputs(node); |
| EnsureValid(); |
| } |
| |
| SparseInputMask::InputIterator* StateValuesAccess::iterator::Top() { |
| DCHECK_LE(0, current_depth_); |
| DCHECK_GT(kMaxInlineDepth, current_depth_); |
| return &(stack_[current_depth_]); |
| } |
| |
| void StateValuesAccess::iterator::Push(Node* node) { |
| current_depth_++; |
| CHECK_GT(kMaxInlineDepth, current_depth_); |
| stack_[current_depth_] = |
| SparseInputMaskOf(node->op()).IterateOverInputs(node); |
| } |
| |
| |
| void StateValuesAccess::iterator::Pop() { |
| DCHECK_LE(0, current_depth_); |
| current_depth_--; |
| } |
| |
| |
| bool StateValuesAccess::iterator::done() { return current_depth_ < 0; } |
| |
| |
| void StateValuesAccess::iterator::Advance() { |
| Top()->Advance(); |
| EnsureValid(); |
| } |
| |
| void StateValuesAccess::iterator::EnsureValid() { |
| while (true) { |
| SparseInputMask::InputIterator* top = Top(); |
| |
| if (top->IsEmpty()) { |
| // We are on a valid (albeit optimized out) node. |
| return; |
| } |
| |
| if (top->IsEnd()) { |
| // We have hit the end of this iterator. Pop the stack and move to the |
| // next sibling iterator. |
| Pop(); |
| if (done()) { |
| // Stack is exhausted, we have reached the end. |
| return; |
| } |
| Top()->Advance(); |
| continue; |
| } |
| |
| // At this point the value is known to be live and within our input nodes. |
| Node* value_node = top->GetReal(); |
| |
| if (value_node->opcode() == IrOpcode::kStateValues || |
| value_node->opcode() == IrOpcode::kTypedStateValues) { |
| // Nested state, we need to push to the stack. |
| Push(value_node); |
| continue; |
| } |
| |
| // We are on a valid node, we can stop the iteration. |
| return; |
| } |
| } |
| |
| Node* StateValuesAccess::iterator::node() { return Top()->Get(nullptr); } |
| |
| MachineType StateValuesAccess::iterator::type() { |
| Node* parent = Top()->parent(); |
| if (parent->opcode() == IrOpcode::kStateValues) { |
| return MachineType::AnyTagged(); |
| } else { |
| DCHECK_EQ(IrOpcode::kTypedStateValues, parent->opcode()); |
| |
| if (Top()->IsEmpty()) { |
| return MachineType::None(); |
| } else { |
| ZoneVector<MachineType> const* types = MachineTypesOf(parent->op()); |
| return (*types)[Top()->real_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; |
| SparseInputMask mask = SparseInputMaskOf(node_->op()); |
| |
| SparseInputMask::InputIterator iterator = mask.IterateOverInputs(node_); |
| |
| for (; !iterator.IsEnd(); iterator.Advance()) { |
| if (iterator.IsEmpty()) { |
| count++; |
| } else { |
| Node* value = iterator.GetReal(); |
| if (value->opcode() == IrOpcode::kStateValues || |
| value->opcode() == IrOpcode::kTypedStateValues) { |
| count += StateValuesAccess(value).size(); |
| } else { |
| count++; |
| } |
| } |
| } |
| |
| return count; |
| } |
| |
| } // namespace compiler |
| } // namespace internal |
| } // namespace v8 |