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 : namespace {
18 :
19 175522360 : size_t HashCode(Node* node) {
20 87761180 : size_t h = base::hash_combine(node->op()->HashCode(), node->InputCount());
21 446409840 : for (Node* input : node->inputs()) {
22 : h = base::hash_combine(h, input->id());
23 : }
24 87753418 : return h;
25 : }
26 :
27 :
28 145367070 : bool Equals(Node* a, Node* b) {
29 : DCHECK_NOT_NULL(a);
30 : DCHECK_NOT_NULL(b);
31 : DCHECK_NOT_NULL(a->op());
32 : DCHECK_NOT_NULL(b->op());
33 145367070 : if (!a->op()->Equals(b->op())) return false;
34 3663008 : if (a->InputCount() != b->InputCount()) return false;
35 : Node::Inputs aInputs = a->inputs();
36 : Node::Inputs bInputs = b->inputs();
37 :
38 : auto aIt = aInputs.begin();
39 : auto bIt = bInputs.begin();
40 : auto aEnd = aInputs.end();
41 :
42 7414714 : for (; aIt != aEnd; ++aIt, ++bIt) {
43 : DCHECK_NOT_NULL(*aIt);
44 : DCHECK_NOT_NULL(*bIt);
45 17444010 : if ((*aIt)->id() != (*bIt)->id()) return false;
46 : }
47 : return true;
48 : }
49 :
50 : } // namespace
51 :
52 1254335 : ValueNumberingReducer::ValueNumberingReducer(Zone* temp_zone, Zone* graph_zone)
53 : : entries_(nullptr),
54 : capacity_(0),
55 : size_(0),
56 : temp_zone_(temp_zone),
57 1254335 : graph_zone_(graph_zone) {}
58 :
59 2508492 : ValueNumberingReducer::~ValueNumberingReducer() {}
60 :
61 :
62 124223710 : Reduction ValueNumberingReducer::Reduce(Node* node) {
63 122969464 : if (!node->op()->HasProperty(Operator::kIdempotent)) return NoChange();
64 :
65 65442175 : const size_t hash = HashCode(node);
66 65438932 : if (!entries_) {
67 : DCHECK(size_ == 0);
68 : DCHECK(capacity_ == 0);
69 : // Allocate the initial entries and insert the first entry.
70 1254246 : capacity_ = kInitialCapacity;
71 1254293 : entries_ = temp_zone()->NewArray<Node*>(kInitialCapacity);
72 : memset(entries_, 0, sizeof(*entries_) * kInitialCapacity);
73 1254293 : entries_[hash & (kInitialCapacity - 1)] = node;
74 1254293 : size_ = 1;
75 : return NoChange();
76 : }
77 :
78 : DCHECK(size_ < capacity_);
79 : DCHECK(size_ + size_ / 4 < capacity_);
80 :
81 64184686 : const size_t mask = capacity_ - 1;
82 : size_t dead = capacity_;
83 :
84 126993210 : for (size_t i = hash & mask;; i = (i + 1) & mask) {
85 126993210 : Node* entry = entries_[i];
86 126993210 : if (!entry) {
87 59854825 : if (dead != capacity_) {
88 : // Reuse dead entry that we discovered on the way.
89 20093 : entries_[dead] = node;
90 : } else {
91 : // Have to insert a new entry.
92 59834732 : entries_[i] = node;
93 59834732 : size_++;
94 :
95 : // Resize to keep load factor below 80%
96 59834732 : if (size_ + size_ / 4 >= capacity_) Grow();
97 : }
98 : DCHECK(size_ + size_ / 4 < capacity_);
99 : return NoChange();
100 : }
101 :
102 67138385 : if (entry == node) {
103 : // We need to check for a certain class of collisions here. Imagine the
104 : // following scenario:
105 : //
106 : // 1. We insert node1 with op1 and certain inputs at index i.
107 : // 2. We insert node2 with op2 and certain inputs at index i+1.
108 : // 3. Some other reducer changes node1 to op2 and the inputs from node2.
109 : //
110 : // Now we are called again to reduce node1, and we would return NoChange
111 : // in this case because we find node1 first, but what we should actually
112 : // do is return Replace(node2) instead.
113 11036923 : for (size_t j = (i + 1) & mask;; j = (j + 1) & mask) {
114 11036923 : Node* entry = entries_[j];
115 11036923 : if (!entry) {
116 : // No collision, {node} is fine.
117 : return NoChange();
118 : }
119 8306259 : if (entry->IsDead()) {
120 : continue;
121 : }
122 8301332 : if (entry == node) {
123 : // Collision with ourselves, doesn't count as a real collision.
124 : // Opportunistically clean-up the duplicate entry if we're at the end
125 : // of a bucket.
126 41 : if (!entries_[(j + 1) & mask]) {
127 3 : entries_[j] = nullptr;
128 3 : size_--;
129 : return NoChange();
130 : }
131 : // Otherwise, keep searching for another collision.
132 : continue;
133 : }
134 8301291 : if (Equals(entry, node)) {
135 366 : Reduction reduction = ReplaceIfTypesMatch(node, entry);
136 366 : if (reduction.Changed()) {
137 : // Overwrite the colliding entry with the actual entry.
138 366 : entries_[i] = entry;
139 : // Opportunistically clean-up the duplicate entry if we're at the
140 : // end of a bucket.
141 366 : if (!entries_[(j + 1) & mask]) {
142 128 : entries_[j] = nullptr;
143 128 : size_--;
144 : }
145 : }
146 366 : return reduction;
147 : }
148 8305889 : }
149 : }
150 :
151 : // Skip dead entries, but remember their indices so we can reuse them.
152 64407351 : if (entry->IsDead()) {
153 : dead = i;
154 : continue;
155 : }
156 64383521 : if (Equals(entry, node)) {
157 1599688 : return ReplaceIfTypesMatch(node, entry);
158 : }
159 62808524 : }
160 : }
161 :
162 1600054 : Reduction ValueNumberingReducer::ReplaceIfTypesMatch(Node* node,
163 : Node* replacement) {
164 : // Make sure the replacement has at least as good type as the original node.
165 2356213 : if (NodeProperties::IsTyped(replacement) && NodeProperties::IsTyped(node)) {
166 : Type* replacement_type = NodeProperties::GetType(replacement);
167 : Type* node_type = NodeProperties::GetType(node);
168 748274 : if (!replacement_type->Is(node_type)) {
169 : // Ideally, we would set an intersection of {replacement_type} and
170 : // {node_type} here. However, typing of NumberConstants assigns different
171 : // types to constants with the same value (it creates a fresh heap
172 : // number), which would make the intersection empty. To be safe, we use
173 : // the smaller type if the types are comparable.
174 477 : if (node_type->Is(replacement_type)) {
175 : NodeProperties::SetType(replacement, node_type);
176 : } else {
177 : // Types are not comparable => do not replace.
178 : return NoChange();
179 : }
180 : }
181 : }
182 : return Replace(replacement);
183 : }
184 :
185 :
186 126396 : void ValueNumberingReducer::Grow() {
187 : // Allocate a new block of entries double the previous capacity.
188 63198 : Node** const old_entries = entries_;
189 63198 : size_t const old_capacity = capacity_;
190 63198 : capacity_ *= 2;
191 63286 : entries_ = temp_zone()->NewArray<Node*>(capacity_);
192 63286 : memset(entries_, 0, sizeof(*entries_) * capacity_);
193 63286 : size_ = 0;
194 63286 : size_t const mask = capacity_ - 1;
195 :
196 : // Insert the old entries into the new block (skipping dead nodes).
197 27958857 : for (size_t i = 0; i < old_capacity; ++i) {
198 27895659 : Node* const old_entry = old_entries[i];
199 50228743 : if (!old_entry || old_entry->IsDead()) continue;
200 29685605 : for (size_t j = HashCode(old_entry) & mask;; j = (j + 1) & mask) {
201 29685517 : Node* const entry = entries_[j];
202 29685517 : if (entry == old_entry) {
203 : // Skip duplicate of the old entry.
204 : break;
205 : }
206 29641640 : if (!entry) {
207 22278705 : entries_[j] = old_entry;
208 22278705 : size_++;
209 22278705 : break;
210 : }
211 7362935 : }
212 : }
213 63198 : }
214 :
215 : } // namespace compiler
216 : } // namespace internal
217 : } // namespace v8
|
