Line data Source code
1 : // Copyright 2016 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/redundancy-elimination.h"
6 :
7 : #include "src/compiler/node-properties.h"
8 : #include "src/compiler/simplified-operator.h"
9 :
10 : namespace v8 {
11 : namespace internal {
12 : namespace compiler {
13 :
14 927831 : RedundancyElimination::RedundancyElimination(Editor* editor, Zone* zone)
15 1855662 : : AdvancedReducer(editor), node_checks_(zone), zone_(zone) {}
16 :
17 : RedundancyElimination::~RedundancyElimination() = default;
18 :
19 93508184 : Reduction RedundancyElimination::Reduce(Node* node) {
20 93508184 : if (node_checks_.Get(node)) return NoChange();
21 81065024 : switch (node->opcode()) {
22 : case IrOpcode::kCheckBounds:
23 : case IrOpcode::kCheckEqualsInternalizedString:
24 : case IrOpcode::kCheckEqualsSymbol:
25 : case IrOpcode::kCheckFloat64Hole:
26 : case IrOpcode::kCheckHeapObject:
27 : case IrOpcode::kCheckIf:
28 : case IrOpcode::kCheckInternalizedString:
29 : case IrOpcode::kCheckNotTaggedHole:
30 : case IrOpcode::kCheckNumber:
31 : case IrOpcode::kCheckReceiver:
32 : case IrOpcode::kCheckReceiverOrNullOrUndefined:
33 : case IrOpcode::kCheckSmi:
34 : case IrOpcode::kCheckString:
35 : case IrOpcode::kCheckSymbol:
36 : #define SIMPLIFIED_CHECKED_OP(Opcode) case IrOpcode::k##Opcode:
37 : SIMPLIFIED_CHECKED_OP_LIST(SIMPLIFIED_CHECKED_OP)
38 : #undef SIMPLIFIED_CHECKED_OP
39 919724 : return ReduceCheckNode(node);
40 : case IrOpcode::kSpeculativeNumberEqual:
41 : case IrOpcode::kSpeculativeNumberLessThan:
42 : case IrOpcode::kSpeculativeNumberLessThanOrEqual:
43 168842 : return ReduceSpeculativeNumberComparison(node);
44 : case IrOpcode::kSpeculativeNumberAdd:
45 : case IrOpcode::kSpeculativeNumberSubtract:
46 : case IrOpcode::kSpeculativeSafeIntegerAdd:
47 : case IrOpcode::kSpeculativeSafeIntegerSubtract:
48 : case IrOpcode::kSpeculativeToNumber:
49 398060 : return ReduceSpeculativeNumberOperation(node);
50 : case IrOpcode::kEffectPhi:
51 1543421 : return ReduceEffectPhi(node);
52 : case IrOpcode::kDead:
53 : break;
54 : case IrOpcode::kStart:
55 927835 : return ReduceStart(node);
56 : default:
57 77081007 : return ReduceOtherNode(node);
58 : }
59 : return NoChange();
60 : }
61 :
62 : // static
63 : RedundancyElimination::EffectPathChecks*
64 1027021 : RedundancyElimination::EffectPathChecks::Copy(Zone* zone,
65 : EffectPathChecks const* checks) {
66 1027021 : return new (zone->New(sizeof(EffectPathChecks))) EffectPathChecks(*checks);
67 : }
68 :
69 : // static
70 : RedundancyElimination::EffectPathChecks const*
71 927825 : RedundancyElimination::EffectPathChecks::Empty(Zone* zone) {
72 1855654 : return new (zone->New(sizeof(EffectPathChecks))) EffectPathChecks(nullptr, 0);
73 : }
74 :
75 0 : bool RedundancyElimination::EffectPathChecks::Equals(
76 : EffectPathChecks const* that) const {
77 0 : if (this->size_ != that->size_) return false;
78 0 : Check* this_head = this->head_;
79 0 : Check* that_head = that->head_;
80 0 : while (this_head != that_head) {
81 0 : if (this_head->node != that_head->node) return false;
82 0 : this_head = this_head->next;
83 0 : that_head = that_head->next;
84 : }
85 : return true;
86 : }
87 :
88 1441589 : void RedundancyElimination::EffectPathChecks::Merge(
89 : EffectPathChecks const* that) {
90 : // Change the current check list to a longest common tail of this check
91 : // list and the other list.
92 :
93 : // First, we throw away the prefix of the longer list, so that
94 : // we have lists of the same length.
95 1441589 : Check* that_head = that->head_;
96 1441589 : size_t that_size = that->size_;
97 1744731 : while (that_size > size_) {
98 151571 : that_head = that_head->next;
99 151571 : that_size--;
100 : }
101 1515731 : while (size_ > that_size) {
102 37071 : head_ = head_->next;
103 37071 : size_--;
104 : }
105 :
106 : // Then we go through both lists in lock-step until we find
107 : // the common tail.
108 1450317 : while (head_ != that_head) {
109 : DCHECK_LT(0u, size_);
110 : DCHECK_NOT_NULL(head_);
111 4364 : size_--;
112 4364 : head_ = head_->next;
113 4364 : that_head = that_head->next;
114 : }
115 1441589 : }
116 :
117 : RedundancyElimination::EffectPathChecks const*
118 421001 : RedundancyElimination::EffectPathChecks::AddCheck(Zone* zone,
119 : Node* node) const {
120 421002 : Check* head = new (zone->New(sizeof(Check))) Check(node, head_);
121 : return new (zone->New(sizeof(EffectPathChecks)))
122 842004 : EffectPathChecks(head, size_ + 1);
123 : }
124 :
125 : namespace {
126 :
127 : // Does check {a} subsume check {b}?
128 4746180 : bool CheckSubsumes(Node const* a, Node const* b) {
129 4746180 : if (a->op() != b->op()) {
130 2562514 : if (a->opcode() == IrOpcode::kCheckInternalizedString &&
131 : b->opcode() == IrOpcode::kCheckString) {
132 : // CheckInternalizedString(node) implies CheckString(node)
133 2608508 : } else if (a->opcode() == IrOpcode::kCheckSmi &&
134 : b->opcode() == IrOpcode::kCheckNumber) {
135 : // CheckSmi(node) implies CheckNumber(node)
136 2675305 : } else if (a->opcode() == IrOpcode::kCheckedTaggedSignedToInt32 &&
137 : b->opcode() == IrOpcode::kCheckedTaggedToInt32) {
138 : // CheckedTaggedSignedToInt32(node) implies CheckedTaggedToInt32(node)
139 2563991 : } else if (a->opcode() == IrOpcode::kCheckReceiver &&
140 : b->opcode() == IrOpcode::kCheckReceiverOrNullOrUndefined) {
141 : // CheckReceiver(node) implies CheckReceiverOrNullOrUndefined(node)
142 2559478 : } else if (a->opcode() != b->opcode()) {
143 : return false;
144 : } else {
145 79221 : switch (a->opcode()) {
146 : case IrOpcode::kCheckBounds:
147 : case IrOpcode::kCheckSmi:
148 : case IrOpcode::kCheckString:
149 : case IrOpcode::kCheckNumber:
150 : break;
151 : case IrOpcode::kCheckedInt32ToTaggedSigned:
152 : case IrOpcode::kCheckedInt64ToInt32:
153 : case IrOpcode::kCheckedInt64ToTaggedSigned:
154 : case IrOpcode::kCheckedTaggedSignedToInt32:
155 : case IrOpcode::kCheckedTaggedToTaggedPointer:
156 : case IrOpcode::kCheckedTaggedToTaggedSigned:
157 : case IrOpcode::kCheckedCompressedToTaggedPointer:
158 : case IrOpcode::kCheckedCompressedToTaggedSigned:
159 : case IrOpcode::kCheckedTaggedToCompressedPointer:
160 : case IrOpcode::kCheckedTaggedToCompressedSigned:
161 : case IrOpcode::kCheckedUint32Bounds:
162 : case IrOpcode::kCheckedUint32ToInt32:
163 : case IrOpcode::kCheckedUint32ToTaggedSigned:
164 : case IrOpcode::kCheckedUint64Bounds:
165 : case IrOpcode::kCheckedUint64ToInt32:
166 : case IrOpcode::kCheckedUint64ToTaggedSigned:
167 : break;
168 : case IrOpcode::kCheckedFloat64ToInt32:
169 : case IrOpcode::kCheckedFloat64ToInt64:
170 : case IrOpcode::kCheckedTaggedToInt32:
171 : case IrOpcode::kCheckedTaggedToInt64: {
172 : const CheckMinusZeroParameters& ap =
173 99 : CheckMinusZeroParametersOf(a->op());
174 : const CheckMinusZeroParameters& bp =
175 99 : CheckMinusZeroParametersOf(b->op());
176 99 : if (ap.mode() != bp.mode()) {
177 : return false;
178 : }
179 : break;
180 : }
181 : case IrOpcode::kCheckedTaggedToFloat64:
182 : case IrOpcode::kCheckedTruncateTaggedToWord32: {
183 : CheckTaggedInputParameters const& ap =
184 7840 : CheckTaggedInputParametersOf(a->op());
185 : CheckTaggedInputParameters const& bp =
186 7840 : CheckTaggedInputParametersOf(b->op());
187 : // {a} subsumes {b} if the modes are either the same, or {a} checks
188 : // for Number, in which case {b} will be subsumed no matter what.
189 7840 : if (ap.mode() != bp.mode() &&
190 : ap.mode() != CheckTaggedInputMode::kNumber) {
191 : return false;
192 : }
193 : break;
194 : }
195 : default:
196 : DCHECK(!IsCheckedWithFeedback(a->op()));
197 : return false;
198 : }
199 : }
200 : }
201 2907777 : for (int i = a->op()->ValueInputCount(); --i >= 0;) {
202 2650773 : if (a->InputAt(i) != b->InputAt(i)) return false;
203 : }
204 : return true;
205 : }
206 :
207 252787 : bool TypeSubsumes(Node* node, Node* replacement) {
208 252787 : if (!NodeProperties::IsTyped(node) || !NodeProperties::IsTyped(replacement)) {
209 : // If either node is untyped, we are running during an untyped optimization
210 : // phase, and replacement is OK.
211 : return true;
212 : }
213 : Type node_type = NodeProperties::GetType(node);
214 123766 : Type replacement_type = NodeProperties::GetType(replacement);
215 123766 : return replacement_type.Is(node_type);
216 : }
217 :
218 : } // namespace
219 :
220 673642 : Node* RedundancyElimination::EffectPathChecks::LookupCheck(Node* node) const {
221 5167236 : for (Check const* check = head_; check != nullptr; check = check->next) {
222 4746212 : if (CheckSubsumes(check->node, node) && TypeSubsumes(node, check->node)) {
223 : DCHECK(!check->node->IsDead());
224 252754 : return check->node;
225 : }
226 : }
227 : return nullptr;
228 : }
229 :
230 346874 : Node* RedundancyElimination::EffectPathChecks::LookupBoundsCheckFor(
231 : Node* node) const {
232 786230 : for (Check const* check = head_; check != nullptr; check = check->next) {
233 1116777 : if (check->node->opcode() == IrOpcode::kCheckBounds &&
234 : check->node->InputAt(0) == node) {
235 : return check->node;
236 : }
237 : }
238 : return nullptr;
239 : }
240 :
241 : RedundancyElimination::EffectPathChecks const*
242 0 : RedundancyElimination::PathChecksForEffectNodes::Get(Node* node) const {
243 152397176 : size_t const id = node->id();
244 257180296 : if (id < info_for_node_.size()) return info_for_node_[id];
245 : return nullptr;
246 : }
247 :
248 24739467 : void RedundancyElimination::PathChecksForEffectNodes::Set(
249 : Node* node, EffectPathChecks const* checks) {
250 24739467 : size_t const id = node->id();
251 24739467 : if (id >= info_for_node_.size()) info_for_node_.resize(id + 1, nullptr);
252 24739454 : info_for_node_[id] = checks;
253 24739454 : }
254 :
255 919708 : Reduction RedundancyElimination::ReduceCheckNode(Node* node) {
256 919708 : Node* const effect = NodeProperties::GetEffectInput(node);
257 : EffectPathChecks const* checks = node_checks_.Get(effect);
258 : // If we do not know anything about the predecessor, do not propagate just yet
259 : // because we will have to recompute anyway once we compute the predecessor.
260 919848 : if (checks == nullptr) return NoChange();
261 : // See if we have another check that dominates us.
262 673645 : if (Node* check = checks->LookupCheck(node)) {
263 : ReplaceWithValue(node, check);
264 : return Replace(check);
265 : }
266 :
267 : // Learn from this check.
268 421000 : return UpdateChecks(node, checks->AddCheck(zone(), node));
269 : }
270 :
271 1543419 : Reduction RedundancyElimination::ReduceEffectPhi(Node* node) {
272 1543419 : Node* const control = NodeProperties::GetControlInput(node);
273 1543435 : if (control->opcode() == IrOpcode::kLoop) {
274 : // Here we rely on having only reducible loops:
275 : // The loop entry edge always dominates the header, so we can just use
276 : // the information from the loop entry edge.
277 101808 : return TakeChecksFromFirstEffect(node);
278 : }
279 : DCHECK_EQ(IrOpcode::kMerge, control->opcode());
280 :
281 : // Shortcut for the case when we do not know anything about some input.
282 : int const input_count = node->op()->EffectInputCount();
283 10904305 : for (int i = 0; i < input_count; ++i) {
284 5145944 : Node* const effect = NodeProperties::GetEffectInput(node, i);
285 5145960 : if (node_checks_.Get(effect) == nullptr) return NoChange();
286 : }
287 :
288 : // Make a copy of the first input's checks and merge with the checks
289 : // from other inputs.
290 1027022 : EffectPathChecks* checks = EffectPathChecks::Copy(
291 1027019 : zone(), node_checks_.Get(NodeProperties::GetEffectInput(node, 0)));
292 3910201 : for (int i = 1; i < input_count; ++i) {
293 1441590 : Node* const input = NodeProperties::GetEffectInput(node, i);
294 1441585 : checks->Merge(node_checks_.Get(input));
295 : }
296 1027020 : return UpdateChecks(node, checks);
297 : }
298 :
299 169072 : Reduction RedundancyElimination::ReduceSpeculativeNumberComparison(Node* node) {
300 169072 : NumberOperationHint const hint = NumberOperationHintOf(node->op());
301 169071 : Node* const first = NodeProperties::GetValueInput(node, 0);
302 169070 : Type const first_type = NodeProperties::GetType(first);
303 169070 : Node* const second = NodeProperties::GetValueInput(node, 1);
304 169065 : Type const second_type = NodeProperties::GetType(second);
305 169065 : Node* const effect = NodeProperties::GetEffectInput(node);
306 : EffectPathChecks const* checks = node_checks_.Get(effect);
307 :
308 : // If we do not know anything about the predecessor, do not propagate just yet
309 : // because we will have to recompute anyway once we compute the predecessor.
310 169095 : if (checks == nullptr) return NoChange();
311 :
312 : // Avoid the potentially expensive lookups below if the {node}
313 : // has seen non-Smi inputs in the past, which is a clear signal
314 : // that the comparison is probably not performed on a value that
315 : // already passed an array bounds check.
316 91130 : if (hint == NumberOperationHint::kSignedSmall) {
317 : // Don't bother trying to find a CheckBounds for the {first} input
318 : // if it's type is already in UnsignedSmall range, since the bounds
319 : // check is only going to narrow that range further, but the result
320 : // is not going to make the representation selection any better.
321 81023 : if (!first_type.Is(Type::UnsignedSmall())) {
322 20188 : if (Node* check = checks->LookupBoundsCheckFor(first)) {
323 79 : if (!first_type.Is(NodeProperties::GetType(check))) {
324 : // Replace the {first} input with the {check}. This is safe,
325 : // despite the fact that {check} can truncate -0 to 0, because
326 : // the regular Number comparisons in JavaScript also identify
327 : // 0 and -0 (unlike special comparisons as Object.is).
328 79 : NodeProperties::ReplaceValueInput(node, check, 0);
329 79 : Reduction const reduction = ReduceSpeculativeNumberComparison(node);
330 79 : return reduction.Changed() ? reduction : Changed(node);
331 : }
332 : }
333 : }
334 :
335 : // Don't bother trying to find a CheckBounds for the {second} input
336 : // if it's type is already in UnsignedSmall range, since the bounds
337 : // check is only going to narrow that range further, but the result
338 : // is not going to make the representation selection any better.
339 80945 : if (!second_type.Is(Type::UnsignedSmall())) {
340 65640 : if (Node* check = checks->LookupBoundsCheckFor(second)) {
341 151 : if (!second_type.Is(NodeProperties::GetType(check))) {
342 : // Replace the {second} input with the {check}. This is safe,
343 : // despite the fact that {check} can truncate -0 to 0, because
344 : // the regular Number comparisons in JavaScript also identify
345 : // 0 and -0 (unlike special comparisons as Object.is).
346 151 : NodeProperties::ReplaceValueInput(node, check, 1);
347 151 : Reduction const reduction = ReduceSpeculativeNumberComparison(node);
348 151 : return reduction.Changed() ? reduction : Changed(node);
349 : }
350 : }
351 : }
352 : }
353 :
354 90907 : return UpdateChecks(node, checks);
355 : }
356 :
357 398062 : Reduction RedundancyElimination::ReduceSpeculativeNumberOperation(Node* node) {
358 : DCHECK(node->opcode() == IrOpcode::kSpeculativeNumberAdd ||
359 : node->opcode() == IrOpcode::kSpeculativeNumberSubtract ||
360 : node->opcode() == IrOpcode::kSpeculativeSafeIntegerAdd ||
361 : node->opcode() == IrOpcode::kSpeculativeSafeIntegerSubtract ||
362 : node->opcode() == IrOpcode::kSpeculativeToNumber);
363 : DCHECK_EQ(1, node->op()->EffectInputCount());
364 : DCHECK_EQ(1, node->op()->EffectOutputCount());
365 :
366 398062 : Node* const first = NodeProperties::GetValueInput(node, 0);
367 398047 : Node* const effect = NodeProperties::GetEffectInput(node);
368 : EffectPathChecks const* checks = node_checks_.Get(effect);
369 : // If we do not know anything about the predecessor, do not propagate just yet
370 : // because we will have to recompute anyway once we compute the predecessor.
371 398200 : if (checks == nullptr) return NoChange();
372 :
373 : // Check if there's a CheckBounds operation on {first}
374 : // in the graph already, which we might be able to
375 : // reuse here to improve the representation selection
376 : // for the {node} later on.
377 261078 : if (Node* check = checks->LookupBoundsCheckFor(first)) {
378 : // Only use the bounds {check} if its type is better
379 : // than the type of the {first} node, otherwise we
380 : // would end up replacing NumberConstant inputs with
381 : // CheckBounds operations, which is kind of pointless.
382 12432 : if (!NodeProperties::GetType(first).Is(NodeProperties::GetType(check))) {
383 3152 : NodeProperties::ReplaceValueInput(node, check, 0);
384 : }
385 : }
386 :
387 261074 : return UpdateChecks(node, checks);
388 : }
389 :
390 927828 : Reduction RedundancyElimination::ReduceStart(Node* node) {
391 927828 : return UpdateChecks(node, EffectPathChecks::Empty(zone()));
392 : }
393 :
394 77083843 : Reduction RedundancyElimination::ReduceOtherNode(Node* node) {
395 77083843 : if (node->op()->EffectInputCount() == 1) {
396 26626400 : if (node->op()->EffectOutputCount() == 1) {
397 24945853 : return TakeChecksFromFirstEffect(node);
398 : } else {
399 : // Effect terminators should be handled specially.
400 : return NoChange();
401 : }
402 : }
403 : DCHECK_EQ(0, node->op()->EffectInputCount());
404 : DCHECK_EQ(0, node->op()->EffectOutputCount());
405 : return NoChange();
406 : }
407 :
408 25047641 : Reduction RedundancyElimination::TakeChecksFromFirstEffect(Node* node) {
409 : DCHECK_EQ(1, node->op()->EffectOutputCount());
410 25047641 : Node* const effect = NodeProperties::GetEffectInput(node);
411 : EffectPathChecks const* checks = node_checks_.Get(effect);
412 : // If we do not know anything about the predecessor, do not propagate just yet
413 : // because we will have to recompute anyway once we compute the predecessor.
414 25047819 : if (checks == nullptr) return NoChange();
415 : // We just propagate the information from the effect input (ideally,
416 : // we would only revisit effect uses if there is change).
417 22012039 : return UpdateChecks(node, checks);
418 : }
419 :
420 24739466 : Reduction RedundancyElimination::UpdateChecks(Node* node,
421 : EffectPathChecks const* checks) {
422 : EffectPathChecks const* original = node_checks_.Get(node);
423 : // Only signal that the {node} has Changed, if the information about {checks}
424 : // has changed wrt. the {original}.
425 24739466 : if (checks != original) {
426 24739458 : if (original == nullptr || !checks->Equals(original)) {
427 24739466 : node_checks_.Set(node, checks);
428 : return Changed(node);
429 : }
430 : }
431 : return NoChange();
432 : }
433 :
434 : } // namespace compiler
435 : } // namespace internal
436 122036 : } // namespace v8
|
