// Copyright 2014 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/value-numbering-reducer.h" #include <cstring> #include "src/base/functional.h" #include "src/compiler/node-properties.h" #include "src/compiler/node.h" namespace v8 { namespace internal { namespace compiler { ValueNumberingReducer::ValueNumberingReducer(Zone* temp_zone, Zone* graph_zone) : entries_(nullptr), capacity_(0), size_(0), temp_zone_(temp_zone), graph_zone_(graph_zone) {} ValueNumberingReducer::~ValueNumberingReducer() = default; Reduction ValueNumberingReducer::Reduce(Node* node) { if (!node->op()->HasProperty(Operator::kIdempotent)) return NoChange(); const size_t hash = NodeProperties::HashCode(node); if (!entries_) { DCHECK_EQ(0, size_); DCHECK_EQ(0, capacity_); // Allocate the initial entries and insert the first entry. capacity_ = kInitialCapacity; entries_ = temp_zone()->NewArray<Node*>(kInitialCapacity); memset(entries_, 0, sizeof(*entries_) * kInitialCapacity); entries_[hash & (kInitialCapacity - 1)] = node; size_ = 1; return NoChange(); } DCHECK(size_ < capacity_); DCHECK(size_ + size_ / 4 < capacity_); const size_t mask = capacity_ - 1; size_t dead = capacity_; for (size_t i = hash & mask;; i = (i + 1) & mask) { Node* entry = entries_[i]; if (!entry) { if (dead != capacity_) { // Reuse dead entry that we discovered on the way. entries_[dead] = node; } else { // Have to insert a new entry. entries_[i] = node; size_++; // Resize to keep load factor below 80% if (size_ + size_ / 4 >= capacity_) Grow(); } DCHECK(size_ + size_ / 4 < capacity_); return NoChange(); } if (entry == node) { // We need to check for a certain class of collisions here. Imagine the // following scenario: // // 1. We insert node1 with op1 and certain inputs at index i. // 2. We insert node2 with op2 and certain inputs at index i+1. // 3. Some other reducer changes node1 to op2 and the inputs from node2. // // Now we are called again to reduce node1, and we would return NoChange // in this case because we find node1 first, but what we should actually // do is return Replace(node2) instead. for (size_t j = (i + 1) & mask;; j = (j + 1) & mask) { Node* entry = entries_[j]; if (!entry) { // No collision, {node} is fine. return NoChange(); } if (entry->IsDead()) { continue; } if (entry == node) { // Collision with ourselves, doesn't count as a real collision. // Opportunistically clean-up the duplicate entry if we're at the end // of a bucket. if (!entries_[(j + 1) & mask]) { entries_[j] = nullptr; size_--; return NoChange(); } // Otherwise, keep searching for another collision. continue; } if (NodeProperties::Equals(entry, node)) { Reduction reduction = ReplaceIfTypesMatch(node, entry); if (reduction.Changed()) { // Overwrite the colliding entry with the actual entry. entries_[i] = entry; // Opportunistically clean-up the duplicate entry if we're at the // end of a bucket. if (!entries_[(j + 1) & mask]) { entries_[j] = nullptr; size_--; } } return reduction; } } } // Skip dead entries, but remember their indices so we can reuse them. if (entry->IsDead()) { dead = i; continue; } if (NodeProperties::Equals(entry, node)) { return ReplaceIfTypesMatch(node, entry); } } } Reduction ValueNumberingReducer::ReplaceIfTypesMatch(Node* node, Node* replacement) { // Make sure the replacement has at least as good type as the original node. if (NodeProperties::IsTyped(replacement) && NodeProperties::IsTyped(node)) { Type replacement_type = NodeProperties::GetType(replacement); Type node_type = NodeProperties::GetType(node); if (!replacement_type.Is(node_type)) { // Ideally, we would set an intersection of {replacement_type} and // {node_type} here. However, typing of NumberConstants assigns different // types to constants with the same value (it creates a fresh heap // number), which would make the intersection empty. To be safe, we use // the smaller type if the types are comparable. if (node_type.Is(replacement_type)) { NodeProperties::SetType(replacement, node_type); } else { // Types are not comparable => do not replace. return NoChange(); } } } return Replace(replacement); } void ValueNumberingReducer::Grow() { // Allocate a new block of entries double the previous capacity. Node** const old_entries = entries_; size_t const old_capacity = capacity_; capacity_ *= 2; entries_ = temp_zone()->NewArray<Node*>(capacity_); memset(entries_, 0, sizeof(*entries_) * capacity_); size_ = 0; size_t const mask = capacity_ - 1; // Insert the old entries into the new block (skipping dead nodes). for (size_t i = 0; i < old_capacity; ++i) { Node* const old_entry = old_entries[i]; if (!old_entry || old_entry->IsDead()) continue; for (size_t j = NodeProperties::HashCode(old_entry) & mask;; j = (j + 1) & mask) { Node* const entry = entries_[j]; if (entry == old_entry) { // Skip duplicate of the old entry. break; } if (!entry) { entries_[j] = old_entry; size_++; break; } } } } } // namespace compiler } // namespace internal } // namespace v8