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 928370 : RedundancyElimination::RedundancyElimination(Editor* editor, Zone* zone)
15 1856740 : : AdvancedReducer(editor), node_checks_(zone), zone_(zone) {}
16 :
17 : RedundancyElimination::~RedundancyElimination() = default;
18 :
19 93718116 : Reduction RedundancyElimination::Reduce(Node* node) {
20 93718116 : if (node_checks_.Get(node)) return NoChange();
21 81245928 : 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::kCheckNonEmptyString:
30 : case IrOpcode::kCheckNonEmptyOneByteString:
31 : case IrOpcode::kCheckNonEmptyTwoByteString:
32 : case IrOpcode::kCheckNotTaggedHole:
33 : case IrOpcode::kCheckNumber:
34 : case IrOpcode::kCheckReceiver:
35 : case IrOpcode::kCheckReceiverOrNullOrUndefined:
36 : case IrOpcode::kCheckSmi:
37 : case IrOpcode::kCheckString:
38 : case IrOpcode::kCheckSymbol:
39 : #define SIMPLIFIED_CHECKED_OP(Opcode) case IrOpcode::k##Opcode:
40 : SIMPLIFIED_CHECKED_OP_LIST(SIMPLIFIED_CHECKED_OP)
41 : #undef SIMPLIFIED_CHECKED_OP
42 934714 : return ReduceCheckNode(node);
43 : case IrOpcode::kSpeculativeNumberEqual:
44 : case IrOpcode::kSpeculativeNumberLessThan:
45 : case IrOpcode::kSpeculativeNumberLessThanOrEqual:
46 168198 : return ReduceSpeculativeNumberComparison(node);
47 : case IrOpcode::kSpeculativeNumberAdd:
48 : case IrOpcode::kSpeculativeNumberSubtract:
49 : case IrOpcode::kSpeculativeSafeIntegerAdd:
50 : case IrOpcode::kSpeculativeSafeIntegerSubtract:
51 : case IrOpcode::kSpeculativeToNumber:
52 396291 : return ReduceSpeculativeNumberOperation(node);
53 : case IrOpcode::kEffectPhi:
54 1550417 : return ReduceEffectPhi(node);
55 : case IrOpcode::kDead:
56 : break;
57 : case IrOpcode::kStart:
58 928374 : return ReduceStart(node);
59 : default:
60 77241827 : return ReduceOtherNode(node);
61 : }
62 : return NoChange();
63 : }
64 :
65 : // static
66 : RedundancyElimination::EffectPathChecks*
67 1028378 : RedundancyElimination::EffectPathChecks::Copy(Zone* zone,
68 : EffectPathChecks const* checks) {
69 1028378 : return new (zone->New(sizeof(EffectPathChecks))) EffectPathChecks(*checks);
70 : }
71 :
72 : // static
73 : RedundancyElimination::EffectPathChecks const*
74 928368 : RedundancyElimination::EffectPathChecks::Empty(Zone* zone) {
75 1856740 : return new (zone->New(sizeof(EffectPathChecks))) EffectPathChecks(nullptr, 0);
76 : }
77 :
78 0 : bool RedundancyElimination::EffectPathChecks::Equals(
79 : EffectPathChecks const* that) const {
80 0 : if (this->size_ != that->size_) return false;
81 0 : Check* this_head = this->head_;
82 0 : Check* that_head = that->head_;
83 0 : while (this_head != that_head) {
84 0 : if (this_head->node != that_head->node) return false;
85 0 : this_head = this_head->next;
86 0 : that_head = that_head->next;
87 : }
88 : return true;
89 : }
90 :
91 1445462 : void RedundancyElimination::EffectPathChecks::Merge(
92 : EffectPathChecks const* that) {
93 : // Change the current check list to a longest common tail of this check
94 : // list and the other list.
95 :
96 : // First, we throw away the prefix of the longer list, so that
97 : // we have lists of the same length.
98 1445462 : Check* that_head = that->head_;
99 1445462 : size_t that_size = that->size_;
100 1762290 : while (that_size > size_) {
101 158414 : that_head = that_head->next;
102 158414 : that_size--;
103 : }
104 1521540 : while (size_ > that_size) {
105 38039 : head_ = head_->next;
106 38039 : size_--;
107 : }
108 :
109 : // Then we go through both lists in lock-step until we find
110 : // the common tail.
111 1454128 : while (head_ != that_head) {
112 : DCHECK_LT(0u, size_);
113 : DCHECK_NOT_NULL(head_);
114 4333 : size_--;
115 4333 : head_ = head_->next;
116 4333 : that_head = that_head->next;
117 : }
118 1445462 : }
119 :
120 : RedundancyElimination::EffectPathChecks const*
121 428805 : RedundancyElimination::EffectPathChecks::AddCheck(Zone* zone,
122 : Node* node) const {
123 428808 : Check* head = new (zone->New(sizeof(Check))) Check(node, head_);
124 : return new (zone->New(sizeof(EffectPathChecks)))
125 857622 : EffectPathChecks(head, size_ + 1);
126 : }
127 :
128 : namespace {
129 :
130 : // Does check {a} subsume check {b}?
131 4950756 : bool CheckSubsumes(Node const* a, Node const* b) {
132 4950756 : if (a->op() != b->op()) {
133 2728132 : if (a->opcode() == IrOpcode::kCheckInternalizedString &&
134 : b->opcode() == IrOpcode::kCheckString) {
135 : // CheckInternalizedString(node) implies CheckString(node)
136 2725214 : } else if (a->opcode() == IrOpcode::kCheckNonEmptyString &&
137 : b->opcode() == IrOpcode::kCheckString) {
138 : // CheckNonEmptyString(node) implies CheckString(node)
139 2776577 : } else if (a->opcode() == IrOpcode::kCheckNonEmptyOneByteString &&
140 : b->opcode() == IrOpcode::kCheckNonEmptyString) {
141 : // CheckNonEmptyOneByteString(node) implies CheckNonEmptyString(node)
142 2725766 : } else if (a->opcode() == IrOpcode::kCheckNonEmptyTwoByteString &&
143 : b->opcode() == IrOpcode::kCheckNonEmptyString) {
144 : // CheckNonEmptyTwoByteString(node) implies CheckNonEmptyString(node)
145 2776596 : } else if (a->opcode() == IrOpcode::kCheckNonEmptyOneByteString &&
146 : b->opcode() == IrOpcode::kCheckString) {
147 : // CheckNonEmptyOneByteString(node) implies CheckString(node)
148 2725195 : } else if (a->opcode() == IrOpcode::kCheckNonEmptyTwoByteString &&
149 : b->opcode() == IrOpcode::kCheckString) {
150 : // CheckNonEmptyTwoByteString(node) implies CheckString(node)
151 2775398 : } else if (a->opcode() == IrOpcode::kCheckSmi &&
152 : b->opcode() == IrOpcode::kCheckNumber) {
153 : // CheckSmi(node) implies CheckNumber(node)
154 2840759 : } else if (a->opcode() == IrOpcode::kCheckedTaggedSignedToInt32 &&
155 : b->opcode() == IrOpcode::kCheckedTaggedToInt32) {
156 : // CheckedTaggedSignedToInt32(node) implies CheckedTaggedToInt32(node)
157 2728884 : } else if (a->opcode() == IrOpcode::kCheckReceiver &&
158 : b->opcode() == IrOpcode::kCheckReceiverOrNullOrUndefined) {
159 : // CheckReceiver(node) implies CheckReceiverOrNullOrUndefined(node)
160 2724414 : } else if (a->opcode() != b->opcode()) {
161 : return false;
162 : } else {
163 81144 : switch (a->opcode()) {
164 : case IrOpcode::kCheckBounds:
165 : case IrOpcode::kCheckSmi:
166 : case IrOpcode::kCheckString:
167 : case IrOpcode::kCheckNumber:
168 : break;
169 : case IrOpcode::kCheckedInt32ToTaggedSigned:
170 : case IrOpcode::kCheckedInt64ToInt32:
171 : case IrOpcode::kCheckedInt64ToTaggedSigned:
172 : case IrOpcode::kCheckedTaggedSignedToInt32:
173 : case IrOpcode::kCheckedTaggedToTaggedPointer:
174 : case IrOpcode::kCheckedTaggedToTaggedSigned:
175 : case IrOpcode::kCheckedCompressedToTaggedPointer:
176 : case IrOpcode::kCheckedCompressedToTaggedSigned:
177 : case IrOpcode::kCheckedTaggedToCompressedPointer:
178 : case IrOpcode::kCheckedTaggedToCompressedSigned:
179 : case IrOpcode::kCheckedUint32Bounds:
180 : case IrOpcode::kCheckedUint32ToInt32:
181 : case IrOpcode::kCheckedUint32ToTaggedSigned:
182 : case IrOpcode::kCheckedUint64Bounds:
183 : case IrOpcode::kCheckedUint64ToInt32:
184 : case IrOpcode::kCheckedUint64ToTaggedSigned:
185 : break;
186 : case IrOpcode::kCheckedFloat64ToInt32:
187 : case IrOpcode::kCheckedFloat64ToInt64:
188 : case IrOpcode::kCheckedTaggedToInt32:
189 : case IrOpcode::kCheckedTaggedToInt64: {
190 : const CheckMinusZeroParameters& ap =
191 99 : CheckMinusZeroParametersOf(a->op());
192 : const CheckMinusZeroParameters& bp =
193 99 : CheckMinusZeroParametersOf(b->op());
194 99 : if (ap.mode() != bp.mode()) {
195 : return false;
196 : }
197 : break;
198 : }
199 : case IrOpcode::kCheckedTaggedToFloat64:
200 : case IrOpcode::kCheckedTruncateTaggedToWord32: {
201 : CheckTaggedInputParameters const& ap =
202 7837 : CheckTaggedInputParametersOf(a->op());
203 : CheckTaggedInputParameters const& bp =
204 7837 : CheckTaggedInputParametersOf(b->op());
205 : // {a} subsumes {b} if the modes are either the same, or {a} checks
206 : // for Number, in which case {b} will be subsumed no matter what.
207 7837 : if (ap.mode() != bp.mode() &&
208 : ap.mode() != CheckTaggedInputMode::kNumber) {
209 : return false;
210 : }
211 : break;
212 : }
213 : default:
214 : DCHECK(!IsCheckedWithFeedback(a->op()));
215 : return false;
216 : }
217 : }
218 : }
219 2960945 : for (int i = a->op()->ValueInputCount(); --i >= 0;) {
220 2708537 : if (a->InputAt(i) != b->InputAt(i)) return false;
221 : }
222 : return true;
223 : }
224 :
225 252052 : bool TypeSubsumes(Node* node, Node* replacement) {
226 252052 : if (!NodeProperties::IsTyped(node) || !NodeProperties::IsTyped(replacement)) {
227 : // If either node is untyped, we are running during an untyped optimization
228 : // phase, and replacement is OK.
229 : return true;
230 : }
231 : Type node_type = NodeProperties::GetType(node);
232 123960 : Type replacement_type = NodeProperties::GetType(replacement);
233 123960 : return replacement_type.Is(node_type);
234 : }
235 :
236 : } // namespace
237 :
238 680482 : Node* RedundancyElimination::EffectPathChecks::LookupCheck(Node* node) const {
239 5380017 : for (Check const* check = head_; check != nullptr; check = check->next) {
240 4950929 : if (CheckSubsumes(check->node, node) && TypeSubsumes(node, check->node)) {
241 : DCHECK(!check->node->IsDead());
242 252035 : return check->node;
243 : }
244 : }
245 : return nullptr;
246 : }
247 :
248 345125 : Node* RedundancyElimination::EffectPathChecks::LookupBoundsCheckFor(
249 : Node* node) const {
250 799178 : for (Check const* check = head_; check != nullptr; check = check->next) {
251 1147543 : if (check->node->opcode() == IrOpcode::kCheckBounds &&
252 : check->node->InputAt(0) == node) {
253 : return check->node;
254 : }
255 : }
256 : return nullptr;
257 : }
258 :
259 : RedundancyElimination::EffectPathChecks const*
260 0 : RedundancyElimination::PathChecksForEffectNodes::Get(Node* node) const {
261 152795858 : size_t const id = node->id();
262 257922949 : if (id < info_for_node_.size()) return info_for_node_[id];
263 : return nullptr;
264 : }
265 :
266 24795939 : void RedundancyElimination::PathChecksForEffectNodes::Set(
267 : Node* node, EffectPathChecks const* checks) {
268 24795939 : size_t const id = node->id();
269 24795939 : if (id >= info_for_node_.size()) info_for_node_.resize(id + 1, nullptr);
270 24795933 : info_for_node_[id] = checks;
271 24795933 : }
272 :
273 934685 : Reduction RedundancyElimination::ReduceCheckNode(Node* node) {
274 934685 : Node* const effect = NodeProperties::GetEffectInput(node);
275 : EffectPathChecks const* checks = node_checks_.Get(effect);
276 : // If we do not know anything about the predecessor, do not propagate just yet
277 : // because we will have to recompute anyway once we compute the predecessor.
278 935040 : if (checks == nullptr) return NoChange();
279 : // See if we have another check that dominates us.
280 680478 : if (Node* check = checks->LookupCheck(node)) {
281 : ReplaceWithValue(node, check);
282 : return Replace(check);
283 : }
284 :
285 : // Learn from this check.
286 428811 : return UpdateChecks(node, checks->AddCheck(zone(), node));
287 : }
288 :
289 1550407 : Reduction RedundancyElimination::ReduceEffectPhi(Node* node) {
290 1550407 : Node* const control = NodeProperties::GetControlInput(node);
291 1550414 : if (control->opcode() == IrOpcode::kLoop) {
292 : // Here we rely on having only reducible loops:
293 : // The loop entry edge always dominates the header, so we can just use
294 : // the information from the loop entry edge.
295 102501 : return TakeChecksFromFirstEffect(node);
296 : }
297 : DCHECK_EQ(IrOpcode::kMerge, control->opcode());
298 :
299 : // Shortcut for the case when we do not know anything about some input.
300 : int const input_count = node->op()->EffectInputCount();
301 10958145 : for (int i = 0; i < input_count; ++i) {
302 5174647 : Node* const effect = NodeProperties::GetEffectInput(node, i);
303 5174679 : if (node_checks_.Get(effect) == nullptr) return NoChange();
304 : }
305 :
306 : // Make a copy of the first input's checks and merge with the checks
307 : // from other inputs.
308 1028382 : EffectPathChecks* checks = EffectPathChecks::Copy(
309 1028377 : zone(), node_checks_.Get(NodeProperties::GetEffectInput(node, 0)));
310 3919311 : for (int i = 1; i < input_count; ++i) {
311 1445466 : Node* const input = NodeProperties::GetEffectInput(node, i);
312 1445463 : checks->Merge(node_checks_.Get(input));
313 : }
314 1028382 : return UpdateChecks(node, checks);
315 : }
316 :
317 168410 : Reduction RedundancyElimination::ReduceSpeculativeNumberComparison(Node* node) {
318 168410 : NumberOperationHint const hint = NumberOperationHintOf(node->op());
319 168415 : Node* const first = NodeProperties::GetValueInput(node, 0);
320 168412 : Type const first_type = NodeProperties::GetType(first);
321 168412 : Node* const second = NodeProperties::GetValueInput(node, 1);
322 168402 : Type const second_type = NodeProperties::GetType(second);
323 168402 : Node* const effect = NodeProperties::GetEffectInput(node);
324 : EffectPathChecks const* checks = node_checks_.Get(effect);
325 :
326 : // If we do not know anything about the predecessor, do not propagate just yet
327 : // because we will have to recompute anyway once we compute the predecessor.
328 168449 : if (checks == nullptr) return NoChange();
329 :
330 : // Avoid the potentially expensive lookups below if the {node}
331 : // has seen non-Smi inputs in the past, which is a clear signal
332 : // that the comparison is probably not performed on a value that
333 : // already passed an array bounds check.
334 90671 : if (hint == NumberOperationHint::kSignedSmall) {
335 : // Don't bother trying to find a CheckBounds for the {first} 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 80619 : if (!first_type.Is(Type::UnsignedSmall())) {
340 20241 : if (Node* check = checks->LookupBoundsCheckFor(first)) {
341 79 : if (!first_type.Is(NodeProperties::GetType(check))) {
342 : // Replace the {first} 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 79 : NodeProperties::ReplaceValueInput(node, check, 0);
347 79 : Reduction const reduction = ReduceSpeculativeNumberComparison(node);
348 79 : return reduction.Changed() ? reduction : Changed(node);
349 : }
350 : }
351 : }
352 :
353 : // Don't bother trying to find a CheckBounds for the {second} input
354 : // if it's type is already in UnsignedSmall range, since the bounds
355 : // check is only going to narrow that range further, but the result
356 : // is not going to make the representation selection any better.
357 80546 : if (!second_type.Is(Type::UnsignedSmall())) {
358 65195 : if (Node* check = checks->LookupBoundsCheckFor(second)) {
359 132 : if (!second_type.Is(NodeProperties::GetType(check))) {
360 : // Replace the {second} input with the {check}. This is safe,
361 : // despite the fact that {check} can truncate -0 to 0, because
362 : // the regular Number comparisons in JavaScript also identify
363 : // 0 and -0 (unlike special comparisons as Object.is).
364 132 : NodeProperties::ReplaceValueInput(node, check, 1);
365 132 : Reduction const reduction = ReduceSpeculativeNumberComparison(node);
366 132 : return reduction.Changed() ? reduction : Changed(node);
367 : }
368 : }
369 : }
370 : }
371 :
372 90473 : return UpdateChecks(node, checks);
373 : }
374 :
375 396296 : Reduction RedundancyElimination::ReduceSpeculativeNumberOperation(Node* node) {
376 : DCHECK(node->opcode() == IrOpcode::kSpeculativeNumberAdd ||
377 : node->opcode() == IrOpcode::kSpeculativeNumberSubtract ||
378 : node->opcode() == IrOpcode::kSpeculativeSafeIntegerAdd ||
379 : node->opcode() == IrOpcode::kSpeculativeSafeIntegerSubtract ||
380 : node->opcode() == IrOpcode::kSpeculativeToNumber);
381 : DCHECK_EQ(1, node->op()->EffectInputCount());
382 : DCHECK_EQ(1, node->op()->EffectOutputCount());
383 :
384 396296 : Node* const first = NodeProperties::GetValueInput(node, 0);
385 396288 : Node* const effect = NodeProperties::GetEffectInput(node);
386 : EffectPathChecks const* checks = node_checks_.Get(effect);
387 : // If we do not know anything about the predecessor, do not propagate just yet
388 : // because we will have to recompute anyway once we compute the predecessor.
389 396464 : if (checks == nullptr) return NoChange();
390 :
391 : // Check if there's a CheckBounds operation on {first}
392 : // in the graph already, which we might be able to
393 : // reuse here to improve the representation selection
394 : // for the {node} later on.
395 259747 : if (Node* check = checks->LookupBoundsCheckFor(first)) {
396 : // Only use the bounds {check} if its type is better
397 : // than the type of the {first} node, otherwise we
398 : // would end up replacing NumberConstant inputs with
399 : // CheckBounds operations, which is kind of pointless.
400 12276 : if (!NodeProperties::GetType(first).Is(NodeProperties::GetType(check))) {
401 3107 : NodeProperties::ReplaceValueInput(node, check, 0);
402 : }
403 : }
404 :
405 259743 : return UpdateChecks(node, checks);
406 : }
407 :
408 928369 : Reduction RedundancyElimination::ReduceStart(Node* node) {
409 928369 : return UpdateChecks(node, EffectPathChecks::Empty(zone()));
410 : }
411 :
412 77245076 : Reduction RedundancyElimination::ReduceOtherNode(Node* node) {
413 77245076 : if (node->op()->EffectInputCount() == 1) {
414 26718674 : if (node->op()->EffectOutputCount() == 1) {
415 25030694 : return TakeChecksFromFirstEffect(node);
416 : } else {
417 : // Effect terminators should be handled specially.
418 : return NoChange();
419 : }
420 : }
421 : DCHECK_EQ(0, node->op()->EffectInputCount());
422 : DCHECK_EQ(0, node->op()->EffectOutputCount());
423 : return NoChange();
424 : }
425 :
426 25133179 : Reduction RedundancyElimination::TakeChecksFromFirstEffect(Node* node) {
427 : DCHECK_EQ(1, node->op()->EffectOutputCount());
428 25133179 : Node* const effect = NodeProperties::GetEffectInput(node);
429 : EffectPathChecks const* checks = node_checks_.Get(effect);
430 : // If we do not know anything about the predecessor, do not propagate just yet
431 : // because we will have to recompute anyway once we compute the predecessor.
432 25133321 : if (checks == nullptr) return NoChange();
433 : // We just propagate the information from the effect input (ideally,
434 : // we would only revisit effect uses if there is change).
435 22060726 : return UpdateChecks(node, checks);
436 : }
437 :
438 24795949 : Reduction RedundancyElimination::UpdateChecks(Node* node,
439 : EffectPathChecks const* checks) {
440 : EffectPathChecks const* original = node_checks_.Get(node);
441 : // Only signal that the {node} has Changed, if the information about {checks}
442 : // has changed wrt. the {original}.
443 24795949 : if (checks != original) {
444 24795934 : if (original == nullptr || !checks->Equals(original)) {
445 24795949 : node_checks_.Set(node, checks);
446 : return Changed(node);
447 : }
448 : }
449 : return NoChange();
450 : }
451 :
452 : } // namespace compiler
453 : } // namespace internal
454 122004 : } // namespace v8
|
