1// Copyright 2014 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "src/compiler/value-numbering-reducer.h"
6
7#include <cstring>
8
9#include "src/base/functional.h"
10#include "src/compiler/node-properties.h"
11#include "src/compiler/node.h"
12
13namespace v8 {
14namespace internal {
15namespace compiler {
16
17ValueNumberingReducer::ValueNumberingReducer(Zone* temp_zone, Zone* graph_zone)
18    : entries_(nullptr),
19      capacity_(0),
20      size_(0),
21      temp_zone_(temp_zone),
22      graph_zone_(graph_zone) {}
23
24ValueNumberingReducer::~ValueNumberingReducer() = default;
25
26
27Reduction ValueNumberingReducer::Reduce(Node* node) {
28  if (!node->op()->HasProperty(Operator::kIdempotent)) return NoChange();
29
30  const size_t hash = NodeProperties::HashCode(node);
31  if (!entries_) {
32    DCHECK_EQ(0, size_);
33    DCHECK_EQ(0, capacity_);
34    // Allocate the initial entries and insert the first entry.
35    capacity_ = kInitialCapacity;
36    entries_ = temp_zone()->NewArray<Node*>(kInitialCapacity);
37    memset(entries_, 0, sizeof(*entries_) * kInitialCapacity);
38    entries_[hash & (kInitialCapacity - 1)] = node;
39    size_ = 1;
40    return NoChange();
41  }
42
43  DCHECK(size_ < capacity_);
44  DCHECK(size_ + size_ / 4 < capacity_);
45
46  const size_t mask = capacity_ - 1;
47  size_t dead = capacity_;
48
49  for (size_t i = hash & mask;; i = (i + 1) & mask) {
50    Node* entry = entries_[i];
51    if (!entry) {
52      if (dead != capacity_) {
53        // Reuse dead entry that we discovered on the way.
54        entries_[dead] = node;
55      } else {
56        // Have to insert a new entry.
57        entries_[i] = node;
58        size_++;
59
60        // Resize to keep load factor below 80%
61        if (size_ + size_ / 4 >= capacity_) Grow();
62      }
63      DCHECK(size_ + size_ / 4 < capacity_);
64      return NoChange();
65    }
66
67    if (entry == node) {
68      // We need to check for a certain class of collisions here. Imagine the
69      // following scenario:
70      //
71      //  1. We insert node1 with op1 and certain inputs at index i.
72      //  2. We insert node2 with op2 and certain inputs at index i+1.
73      //  3. Some other reducer changes node1 to op2 and the inputs from node2.
74      //
75      // Now we are called again to reduce node1, and we would return NoChange
76      // in this case because we find node1 first, but what we should actually
77      // do is return Replace(node2) instead.
78      for (size_t j = (i + 1) & mask;; j = (j + 1) & mask) {
79        Node* other_entry = entries_[j];
80        if (!other_entry) {
81          // No collision, {node} is fine.
82          return NoChange();
83        }
84        if (other_entry->IsDead()) {
85          continue;
86        }
87        if (other_entry == node) {
88          // Collision with ourselves, doesn't count as a real collision.
89          // Opportunistically clean-up the duplicate entry if we're at the end
90          // of a bucket.
91          if (!entries_[(j + 1) & mask]) {
92            entries_[j] = nullptr;
93            size_--;
94            return NoChange();
95          }
96          // Otherwise, keep searching for another collision.
97          continue;
98        }
99        if (NodeProperties::Equals(other_entry, node)) {
100          Reduction reduction = ReplaceIfTypesMatch(node, other_entry);
101          if (reduction.Changed()) {
102            // Overwrite the colliding entry with the actual entry.
103            entries_[i] = other_entry;
104            // Opportunistically clean-up the duplicate entry if we're at the
105            // end of a bucket.
106            if (!entries_[(j + 1) & mask]) {
107              entries_[j] = nullptr;
108              size_--;
109            }
110          }
111          return reduction;
112        }
113      }
114    }
115
116    // Skip dead entries, but remember their indices so we can reuse them.
117    if (entry->IsDead()) {
118      dead = i;
119      continue;
120    }
121    if (NodeProperties::Equals(entry, node)) {
122      return ReplaceIfTypesMatch(node, entry);
123    }
124  }
125}
126
127Reduction ValueNumberingReducer::ReplaceIfTypesMatch(Node* node,
128                                                     Node* replacement) {
129  // Make sure the replacement has at least as good type as the original node.
130  if (NodeProperties::IsTyped(replacement) && NodeProperties::IsTyped(node)) {
131    Type replacement_type = NodeProperties::GetType(replacement);
132    Type node_type = NodeProperties::GetType(node);
133    if (!replacement_type.Is(node_type)) {
134      // Ideally, we would set an intersection of {replacement_type} and
135      // {node_type} here. However, typing of NumberConstants assigns different
136      // types to constants with the same value (it creates a fresh heap
137      // number), which would make the intersection empty. To be safe, we use
138      // the smaller type if the types are comparable.
139      if (node_type.Is(replacement_type)) {
140        NodeProperties::SetType(replacement, node_type);
141      } else {
142        // Types are not comparable => do not replace.
143        return NoChange();
144      }
145    }
146  }
147  return Replace(replacement);
148}
149
150
151void ValueNumberingReducer::Grow() {
152  // Allocate a new block of entries double the previous capacity.
153  Node** const old_entries = entries_;
154  size_t const old_capacity = capacity_;
155  capacity_ *= 2;
156  entries_ = temp_zone()->NewArray<Node*>(capacity_);
157  memset(entries_, 0, sizeof(*entries_) * capacity_);
158  size_ = 0;
159  size_t const mask = capacity_ - 1;
160
161  // Insert the old entries into the new block (skipping dead nodes).
162  for (size_t i = 0; i < old_capacity; ++i) {
163    Node* const old_entry = old_entries[i];
164    if (!old_entry || old_entry->IsDead()) continue;
165    for (size_t j = NodeProperties::HashCode(old_entry) & mask;;
166         j = (j + 1) & mask) {
167      Node* const entry = entries_[j];
168      if (entry == old_entry) {
169        // Skip duplicate of the old entry.
170        break;
171      }
172      if (!entry) {
173        entries_[j] = old_entry;
174        size_++;
175        break;
176      }
177    }
178  }
179}
180
181}  // namespace compiler
182}  // namespace internal
183}  // namespace v8
184