Line data Source code
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 :
13 : namespace v8 {
14 : namespace internal {
15 : namespace compiler {
16 :
17 2428347 : ValueNumberingReducer::ValueNumberingReducer(Zone* temp_zone, Zone* graph_zone)
18 : : entries_(nullptr),
19 : capacity_(0),
20 : size_(0),
21 : temp_zone_(temp_zone),
22 2428347 : graph_zone_(graph_zone) {}
23 :
24 : ValueNumberingReducer::~ValueNumberingReducer() = default;
25 :
26 :
27 138997893 : Reduction ValueNumberingReducer::Reduce(Node* node) {
28 136569789 : if (!node->op()->HasProperty(Operator::kIdempotent)) return NoChange();
29 :
30 72648319 : const size_t hash = NodeProperties::HashCode(node);
31 72651491 : if (!entries_) {
32 : DCHECK_EQ(0, size_);
33 : DCHECK_EQ(0, capacity_);
34 : // Allocate the initial entries and insert the first entry.
35 2428104 : capacity_ = kInitialCapacity;
36 2427990 : entries_ = temp_zone()->NewArray<Node*>(kInitialCapacity);
37 : memset(entries_, 0, sizeof(*entries_) * kInitialCapacity);
38 2427990 : entries_[hash & (kInitialCapacity - 1)] = node;
39 2427990 : size_ = 1;
40 : return NoChange();
41 : }
42 :
43 : DCHECK(size_ < capacity_);
44 : DCHECK(size_ + size_ / 4 < capacity_);
45 :
46 70223387 : const size_t mask = capacity_ - 1;
47 : size_t dead = capacity_;
48 :
49 125758445 : for (size_t i = hash & mask;; i = (i + 1) & mask) {
50 125758445 : Node* entry = entries_[i];
51 125758445 : if (!entry) {
52 65969478 : if (dead != capacity_) {
53 : // Reuse dead entry that we discovered on the way.
54 20148 : entries_[dead] = node;
55 : } else {
56 : // Have to insert a new entry.
57 65949330 : entries_[i] = node;
58 65949330 : size_++;
59 :
60 : // Resize to keep load factor below 80%
61 65949330 : if (size_ + size_ / 4 >= capacity_) Grow();
62 : }
63 : DCHECK(size_ + size_ / 4 < capacity_);
64 : return NoChange();
65 : }
66 :
67 59788967 : 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 6963726 : for (size_t j = (i + 1) & mask;; j = (j + 1) & mask) {
79 6963726 : Node* entry = entries_[j];
80 6963726 : if (!entry) {
81 : // No collision, {node} is fine.
82 : return NoChange();
83 : }
84 4896721 : if (entry->IsDead()) {
85 : continue;
86 : }
87 4888164 : if (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 40 : if (!entries_[(j + 1) & mask]) {
92 4 : entries_[j] = nullptr;
93 4 : size_--;
94 : return NoChange();
95 : }
96 : // Otherwise, keep searching for another collision.
97 : continue;
98 : }
99 4888124 : if (NodeProperties::Equals(entry, node)) {
100 324 : Reduction reduction = ReplaceIfTypesMatch(node, entry);
101 324 : if (reduction.Changed()) {
102 : // Overwrite the colliding entry with the actual entry.
103 324 : entries_[i] = entry;
104 : // Opportunistically clean-up the duplicate entry if we're at the
105 : // end of a bucket.
106 324 : if (!entries_[(j + 1) & mask]) {
107 64 : entries_[j] = nullptr;
108 64 : size_--;
109 : }
110 : }
111 324 : return reduction;
112 : }
113 4896364 : }
114 : }
115 :
116 : // Skip dead entries, but remember their indices so we can reuse them.
117 57721605 : if (entry->IsDead()) {
118 : dead = i;
119 : continue;
120 : }
121 57696021 : if (NodeProperties::Equals(entry, node)) {
122 2186517 : return ReplaceIfTypesMatch(node, entry);
123 : }
124 55535058 : }
125 : }
126 :
127 2186828 : Reduction ValueNumberingReducer::ReplaceIfTypesMatch(Node* node,
128 : Node* replacement) {
129 : // Make sure the replacement has at least as good type as the original node.
130 2186828 : if (NodeProperties::IsTyped(replacement) && NodeProperties::IsTyped(node)) {
131 794289 : Type replacement_type = NodeProperties::GetType(replacement);
132 794289 : Type node_type = NodeProperties::GetType(node);
133 794289 : 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 794 : if (node_type.Is(replacement_type)) {
140 : NodeProperties::SetType(replacement, node_type);
141 : } else {
142 : // Types are not comparable => do not replace.
143 0 : return NoChange();
144 : }
145 : }
146 : }
147 : return Replace(replacement);
148 : }
149 :
150 :
151 97320 : void ValueNumberingReducer::Grow() {
152 : // Allocate a new block of entries double the previous capacity.
153 48660 : Node** const old_entries = entries_;
154 48660 : size_t const old_capacity = capacity_;
155 48660 : capacity_ *= 2;
156 48689 : entries_ = temp_zone()->NewArray<Node*>(capacity_);
157 48689 : memset(entries_, 0, sizeof(*entries_) * capacity_);
158 48689 : size_ = 0;
159 48689 : size_t const mask = capacity_ - 1;
160 :
161 : // Insert the old entries into the new block (skipping dead nodes).
162 26769214 : for (size_t i = 0; i < old_capacity; ++i) {
163 26720554 : Node* const old_entry = old_entries[i];
164 48110410 : if (!old_entry || old_entry->IsDead()) continue;
165 28415996 : for (size_t j = NodeProperties::HashCode(old_entry) & mask;;
166 7035162 : j = (j + 1) & mask) {
167 28415967 : Node* const entry = entries_[j];
168 28415967 : if (entry == old_entry) {
169 : // Skip duplicate of the old entry.
170 : break;
171 : }
172 28381659 : if (!entry) {
173 21346497 : entries_[j] = old_entry;
174 21346497 : size_++;
175 21346497 : break;
176 : }
177 7035162 : }
178 : }
179 48660 : }
180 :
181 : } // namespace compiler
182 : } // namespace internal
183 183867 : } // namespace v8
|
