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 927707 : RedundancyElimination::RedundancyElimination(Editor* editor, Zone* zone)
15 1855414 : : AdvancedReducer(editor), node_checks_(zone), zone_(zone) {}
16 :
17 : RedundancyElimination::~RedundancyElimination() = default;
18 :
19 96523572 : Reduction RedundancyElimination::Reduce(Node* node) {
20 96523572 : if (node_checks_.Get(node)) return NoChange();
21 83563333 : 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 945675 : return ReduceCheckNode(node);
43 : case IrOpcode::kSpeculativeNumberEqual:
44 : case IrOpcode::kSpeculativeNumberLessThan:
45 : case IrOpcode::kSpeculativeNumberLessThanOrEqual:
46 170887 : return ReduceSpeculativeNumberComparison(node);
47 : case IrOpcode::kSpeculativeNumberAdd:
48 : case IrOpcode::kSpeculativeNumberSubtract:
49 : case IrOpcode::kSpeculativeSafeIntegerAdd:
50 : case IrOpcode::kSpeculativeSafeIntegerSubtract:
51 : case IrOpcode::kSpeculativeToNumber:
52 403435 : return ReduceSpeculativeNumberOperation(node);
53 : case IrOpcode::kEffectPhi:
54 1539135 : return ReduceEffectPhi(node);
55 : case IrOpcode::kDead:
56 : break;
57 : case IrOpcode::kStart:
58 927721 : return ReduceStart(node);
59 : default:
60 79550381 : return ReduceOtherNode(node);
61 : }
62 : return NoChange();
63 : }
64 :
65 : // static
66 : RedundancyElimination::EffectPathChecks*
67 1021906 : RedundancyElimination::EffectPathChecks::Copy(Zone* zone,
68 : EffectPathChecks const* checks) {
69 1021907 : return new (zone->New(sizeof(EffectPathChecks))) EffectPathChecks(*checks);
70 : }
71 :
72 : // static
73 : RedundancyElimination::EffectPathChecks const*
74 927698 : RedundancyElimination::EffectPathChecks::Empty(Zone* zone) {
75 1855408 : 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 1426960 : 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 1426960 : Check* that_head = that->head_;
99 1426960 : size_t that_size = that->size_;
100 1743590 : while (that_size > size_) {
101 158315 : that_head = that_head->next;
102 158315 : that_size--;
103 : }
104 1502564 : while (size_ > that_size) {
105 37802 : head_ = head_->next;
106 37802 : size_--;
107 : }
108 :
109 : // Then we go through both lists in lock-step until we find
110 : // the common tail.
111 1435778 : while (head_ != that_head) {
112 : DCHECK_LT(0u, size_);
113 : DCHECK_NOT_NULL(head_);
114 4409 : size_--;
115 4409 : head_ = head_->next;
116 4409 : that_head = that_head->next;
117 : }
118 1426960 : }
119 :
120 : RedundancyElimination::EffectPathChecks const*
121 428675 : RedundancyElimination::EffectPathChecks::AddCheck(Zone* zone,
122 : Node* node) const {
123 428674 : Check* head = new (zone->New(sizeof(Check))) Check(node, head_);
124 : return new (zone->New(sizeof(EffectPathChecks)))
125 857348 : EffectPathChecks(head, size_ + 1);
126 : }
127 :
128 : namespace {
129 :
130 : // Does check {a} subsume check {b}?
131 5016020 : bool CheckSubsumes(Node const* a, Node const* b) {
132 5016020 : if (a->op() != b->op()) {
133 2724082 : if (a->opcode() == IrOpcode::kCheckInternalizedString &&
134 : b->opcode() == IrOpcode::kCheckString) {
135 : // CheckInternalizedString(node) implies CheckString(node)
136 2720608 : } else if (a->opcode() == IrOpcode::kCheckNonEmptyString &&
137 : b->opcode() == IrOpcode::kCheckString) {
138 : // CheckNonEmptyString(node) implies CheckString(node)
139 2765884 : } else if (a->opcode() == IrOpcode::kCheckNonEmptyOneByteString &&
140 : b->opcode() == IrOpcode::kCheckNonEmptyString) {
141 : // CheckNonEmptyOneByteString(node) implies CheckNonEmptyString(node)
142 2721214 : } else if (a->opcode() == IrOpcode::kCheckNonEmptyTwoByteString &&
143 : b->opcode() == IrOpcode::kCheckNonEmptyString) {
144 : // CheckNonEmptyTwoByteString(node) implies CheckNonEmptyString(node)
145 2765933 : } else if (a->opcode() == IrOpcode::kCheckNonEmptyOneByteString &&
146 : b->opcode() == IrOpcode::kCheckString) {
147 : // CheckNonEmptyOneByteString(node) implies CheckString(node)
148 2720094 : } else if (a->opcode() == IrOpcode::kCheckNonEmptyTwoByteString &&
149 : b->opcode() == IrOpcode::kCheckString) {
150 : // CheckNonEmptyTwoByteString(node) implies CheckString(node)
151 2769981 : } else if (a->opcode() == IrOpcode::kCheckSmi &&
152 : b->opcode() == IrOpcode::kCheckNumber) {
153 : // CheckSmi(node) implies CheckNumber(node)
154 2835090 : } else if (a->opcode() == IrOpcode::kCheckedTaggedSignedToInt32 &&
155 : b->opcode() == IrOpcode::kCheckedTaggedToInt32) {
156 : // CheckedTaggedSignedToInt32(node) implies CheckedTaggedToInt32(node)
157 2723899 : } else if (a->opcode() == IrOpcode::kCheckReceiver &&
158 : b->opcode() == IrOpcode::kCheckReceiverOrNullOrUndefined) {
159 : // CheckReceiver(node) implies CheckReceiverOrNullOrUndefined(node)
160 2719343 : } else if (a->opcode() != b->opcode()) {
161 : return false;
162 : } else {
163 83313 : 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::kCheckedUint32Bounds:
176 : case IrOpcode::kCheckedUint32ToInt32:
177 : case IrOpcode::kCheckedUint32ToTaggedSigned:
178 : case IrOpcode::kCheckedUint64Bounds:
179 : case IrOpcode::kCheckedUint64ToInt32:
180 : case IrOpcode::kCheckedUint64ToTaggedSigned:
181 : break;
182 : case IrOpcode::kCheckedFloat64ToInt32:
183 : case IrOpcode::kCheckedFloat64ToInt64:
184 : case IrOpcode::kCheckedTaggedToInt32:
185 : case IrOpcode::kCheckedTaggedToInt64: {
186 : const CheckMinusZeroParameters& ap =
187 163 : CheckMinusZeroParametersOf(a->op());
188 : const CheckMinusZeroParameters& bp =
189 163 : CheckMinusZeroParametersOf(b->op());
190 163 : if (ap.mode() != bp.mode()) {
191 : return false;
192 : }
193 : break;
194 : }
195 : case IrOpcode::kCheckedTaggedToFloat64:
196 : case IrOpcode::kCheckedTruncateTaggedToWord32: {
197 : CheckTaggedInputParameters const& ap =
198 8821 : CheckTaggedInputParametersOf(a->op());
199 : CheckTaggedInputParameters const& bp =
200 8821 : CheckTaggedInputParametersOf(b->op());
201 : // {a} subsumes {b} if the modes are either the same, or {a} checks
202 : // for Number, in which case {b} will be subsumed no matter what.
203 8821 : if (ap.mode() != bp.mode() &&
204 : ap.mode() != CheckTaggedInputMode::kNumber) {
205 : return false;
206 : }
207 : break;
208 : }
209 : default:
210 : DCHECK(!IsCheckedWithFeedback(a->op()));
211 : return false;
212 : }
213 : }
214 : }
215 2956741 : for (int i = a->op()->ValueInputCount(); --i >= 0;) {
216 2701900 : if (a->InputAt(i) != b->InputAt(i)) return false;
217 : }
218 : return true;
219 : }
220 :
221 254586 : bool TypeSubsumes(Node* node, Node* replacement) {
222 254586 : if (!NodeProperties::IsTyped(node) || !NodeProperties::IsTyped(replacement)) {
223 : // If either node is untyped, we are running during an untyped optimization
224 : // phase, and replacement is OK.
225 : return true;
226 : }
227 : Type node_type = NodeProperties::GetType(node);
228 124658 : Type replacement_type = NodeProperties::GetType(replacement);
229 124658 : return replacement_type.Is(node_type);
230 : }
231 :
232 : } // namespace
233 :
234 683100 : Node* RedundancyElimination::EffectPathChecks::LookupCheck(Node* node) const {
235 5444949 : for (Check const* check = head_; check != nullptr; check = check->next) {
236 5016059 : if (CheckSubsumes(check->node, node) && TypeSubsumes(node, check->node)) {
237 : DCHECK(!check->node->IsDead());
238 254570 : return check->node;
239 : }
240 : }
241 : return nullptr;
242 : }
243 :
244 347382 : Node* RedundancyElimination::EffectPathChecks::LookupBoundsCheckFor(
245 : Node* node) const {
246 842395 : for (Check const* check = head_; check != nullptr; check = check->next) {
247 1190769 : if (check->node->opcode() == IrOpcode::kCheckBounds &&
248 : check->node->InputAt(0) == node) {
249 : return check->node;
250 : }
251 : }
252 : return nullptr;
253 : }
254 :
255 : RedundancyElimination::EffectPathChecks const*
256 0 : RedundancyElimination::PathChecksForEffectNodes::Get(Node* node) const {
257 157517138 : size_t const id = node->id();
258 265535211 : if (id < info_for_node_.size()) return info_for_node_[id];
259 : return nullptr;
260 : }
261 :
262 25796906 : void RedundancyElimination::PathChecksForEffectNodes::Set(
263 : Node* node, EffectPathChecks const* checks) {
264 25796906 : size_t const id = node->id();
265 25796906 : if (id >= info_for_node_.size()) info_for_node_.resize(id + 1, nullptr);
266 25796878 : info_for_node_[id] = checks;
267 25796878 : }
268 :
269 945654 : Reduction RedundancyElimination::ReduceCheckNode(Node* node) {
270 945654 : Node* const effect = NodeProperties::GetEffectInput(node);
271 : EffectPathChecks const* checks = node_checks_.Get(effect);
272 : // If we do not know anything about the predecessor, do not propagate just yet
273 : // because we will have to recompute anyway once we compute the predecessor.
274 945832 : if (checks == nullptr) return NoChange();
275 : // See if we have another check that dominates us.
276 683116 : if (Node* check = checks->LookupCheck(node)) {
277 : ReplaceWithValue(node, check);
278 : return Replace(check);
279 : }
280 :
281 : // Learn from this check.
282 428674 : return UpdateChecks(node, checks->AddCheck(zone(), node));
283 : }
284 :
285 1539129 : Reduction RedundancyElimination::ReduceEffectPhi(Node* node) {
286 1539129 : Node* const control = NodeProperties::GetControlInput(node);
287 1539145 : if (control->opcode() == IrOpcode::kLoop) {
288 : // Here we rely on having only reducible loops:
289 : // The loop entry edge always dominates the header, so we can just use
290 : // the information from the loop entry edge.
291 102430 : return TakeChecksFromFirstEffect(node);
292 : }
293 : DCHECK_EQ(IrOpcode::kMerge, control->opcode());
294 :
295 : // Shortcut for the case when we do not know anything about some input.
296 : int const input_count = node->op()->EffectInputCount();
297 10696985 : for (int i = 0; i < input_count; ++i) {
298 5044941 : Node* const effect = NodeProperties::GetEffectInput(node, i);
299 5044965 : if (node_checks_.Get(effect) == nullptr) return NoChange();
300 : }
301 :
302 : // Make a copy of the first input's checks and merge with the checks
303 : // from other inputs.
304 1021909 : EffectPathChecks* checks = EffectPathChecks::Copy(
305 1021907 : zone(), node_checks_.Get(NodeProperties::GetEffectInput(node, 0)));
306 3875830 : for (int i = 1; i < input_count; ++i) {
307 1426965 : Node* const input = NodeProperties::GetEffectInput(node, i);
308 1426954 : checks->Merge(node_checks_.Get(input));
309 : }
310 1021904 : return UpdateChecks(node, checks);
311 : }
312 :
313 171106 : Reduction RedundancyElimination::ReduceSpeculativeNumberComparison(Node* node) {
314 171106 : NumberOperationHint const hint = NumberOperationHintOf(node->op());
315 171103 : Node* const first = NodeProperties::GetValueInput(node, 0);
316 171100 : Type const first_type = NodeProperties::GetType(first);
317 171100 : Node* const second = NodeProperties::GetValueInput(node, 1);
318 171097 : Type const second_type = NodeProperties::GetType(second);
319 171097 : Node* const effect = NodeProperties::GetEffectInput(node);
320 : EffectPathChecks const* checks = node_checks_.Get(effect);
321 :
322 : // If we do not know anything about the predecessor, do not propagate just yet
323 : // because we will have to recompute anyway once we compute the predecessor.
324 171118 : if (checks == nullptr) return NoChange();
325 :
326 : // Avoid the potentially expensive lookups below if the {node}
327 : // has seen non-Smi inputs in the past, which is a clear signal
328 : // that the comparison is probably not performed on a value that
329 : // already passed an array bounds check.
330 91305 : if (hint == NumberOperationHint::kSignedSmall) {
331 : // Don't bother trying to find a CheckBounds for the {first} input
332 : // if it's type is already in UnsignedSmall range, since the bounds
333 : // check is only going to narrow that range further, but the result
334 : // is not going to make the representation selection any better.
335 80778 : if (!first_type.Is(Type::UnsignedSmall())) {
336 19746 : if (Node* check = checks->LookupBoundsCheckFor(first)) {
337 79 : if (!first_type.Is(NodeProperties::GetType(check))) {
338 : // Replace the {first} input with the {check}. This is safe,
339 : // despite the fact that {check} can truncate -0 to 0, because
340 : // the regular Number comparisons in JavaScript also identify
341 : // 0 and -0 (unlike special comparisons as Object.is).
342 79 : NodeProperties::ReplaceValueInput(node, check, 0);
343 79 : Reduction const reduction = ReduceSpeculativeNumberComparison(node);
344 79 : return reduction.Changed() ? reduction : Changed(node);
345 : }
346 : }
347 : }
348 :
349 : // Don't bother trying to find a CheckBounds for the {second} input
350 : // if it's type is already in UnsignedSmall range, since the bounds
351 : // check is only going to narrow that range further, but the result
352 : // is not going to make the representation selection any better.
353 80700 : if (!second_type.Is(Type::UnsignedSmall())) {
354 65403 : if (Node* check = checks->LookupBoundsCheckFor(second)) {
355 136 : if (!second_type.Is(NodeProperties::GetType(check))) {
356 : // Replace the {second} input with the {check}. This is safe,
357 : // despite the fact that {check} can truncate -0 to 0, because
358 : // the regular Number comparisons in JavaScript also identify
359 : // 0 and -0 (unlike special comparisons as Object.is).
360 136 : NodeProperties::ReplaceValueInput(node, check, 1);
361 136 : Reduction const reduction = ReduceSpeculativeNumberComparison(node);
362 136 : return reduction.Changed() ? reduction : Changed(node);
363 : }
364 : }
365 : }
366 : }
367 :
368 91097 : return UpdateChecks(node, checks);
369 : }
370 :
371 403439 : Reduction RedundancyElimination::ReduceSpeculativeNumberOperation(Node* node) {
372 : DCHECK(node->opcode() == IrOpcode::kSpeculativeNumberAdd ||
373 : node->opcode() == IrOpcode::kSpeculativeNumberSubtract ||
374 : node->opcode() == IrOpcode::kSpeculativeSafeIntegerAdd ||
375 : node->opcode() == IrOpcode::kSpeculativeSafeIntegerSubtract ||
376 : node->opcode() == IrOpcode::kSpeculativeToNumber);
377 : DCHECK_EQ(1, node->op()->EffectInputCount());
378 : DCHECK_EQ(1, node->op()->EffectOutputCount());
379 :
380 403439 : Node* const first = NodeProperties::GetValueInput(node, 0);
381 403432 : Node* const effect = NodeProperties::GetEffectInput(node);
382 : EffectPathChecks const* checks = node_checks_.Get(effect);
383 : // If we do not know anything about the predecessor, do not propagate just yet
384 : // because we will have to recompute anyway once we compute the predecessor.
385 403508 : if (checks == nullptr) return NoChange();
386 :
387 : // Check if there's a CheckBounds operation on {first}
388 : // in the graph already, which we might be able to
389 : // reuse here to improve the representation selection
390 : // for the {node} later on.
391 262262 : if (Node* check = checks->LookupBoundsCheckFor(first)) {
392 : // Only use the bounds {check} if its type is better
393 : // than the type of the {first} node, otherwise we
394 : // would end up replacing NumberConstant inputs with
395 : // CheckBounds operations, which is kind of pointless.
396 12366 : if (!NodeProperties::GetType(first).Is(NodeProperties::GetType(check))) {
397 3141 : NodeProperties::ReplaceValueInput(node, check, 0);
398 : }
399 : }
400 :
401 262261 : return UpdateChecks(node, checks);
402 : }
403 :
404 927699 : Reduction RedundancyElimination::ReduceStart(Node* node) {
405 927699 : return UpdateChecks(node, EffectPathChecks::Empty(zone()));
406 : }
407 :
408 79552437 : Reduction RedundancyElimination::ReduceOtherNode(Node* node) {
409 79552437 : if (node->op()->EffectInputCount() == 1) {
410 27764109 : if (node->op()->EffectOutputCount() == 1) {
411 26079858 : return TakeChecksFromFirstEffect(node);
412 : } else {
413 : // Effect terminators should be handled specially.
414 : return NoChange();
415 : }
416 : }
417 : DCHECK_EQ(0, node->op()->EffectInputCount());
418 : DCHECK_EQ(0, node->op()->EffectOutputCount());
419 : return NoChange();
420 : }
421 :
422 26182284 : Reduction RedundancyElimination::TakeChecksFromFirstEffect(Node* node) {
423 : DCHECK_EQ(1, node->op()->EffectOutputCount());
424 26182284 : Node* const effect = NodeProperties::GetEffectInput(node);
425 : EffectPathChecks const* checks = node_checks_.Get(effect);
426 : // If we do not know anything about the predecessor, do not propagate just yet
427 : // because we will have to recompute anyway once we compute the predecessor.
428 26182375 : if (checks == nullptr) return NoChange();
429 : // We just propagate the information from the effect input (ideally,
430 : // we would only revisit effect uses if there is change).
431 23065589 : return UpdateChecks(node, checks);
432 : }
433 :
434 25796907 : Reduction RedundancyElimination::UpdateChecks(Node* node,
435 : EffectPathChecks const* checks) {
436 : EffectPathChecks const* original = node_checks_.Get(node);
437 : // Only signal that the {node} has Changed, if the information about {checks}
438 : // has changed wrt. the {original}.
439 25796907 : if (checks != original) {
440 25796908 : if (original == nullptr || !checks->Equals(original)) {
441 25796907 : node_checks_.Set(node, checks);
442 : return Changed(node);
443 : }
444 : }
445 : return NoChange();
446 : }
447 :
448 : } // namespace compiler
449 : } // namespace internal
450 120216 : } // namespace v8
|
