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
10namespace v8 {
11namespace internal {
12namespace compiler {
13
14RedundancyElimination::RedundancyElimination(Editor* editor, Zone* zone)
15 : AdvancedReducer(editor), node_checks_(zone), zone_(zone) {}
16
17RedundancyElimination::~RedundancyElimination() = default;
18
19Reduction RedundancyElimination::Reduce(Node* node) {
20 if (node_checks_.Get(node)) return NoChange();
21 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 return ReduceCheckNode(node);
43 case IrOpcode::kSpeculativeNumberEqual:
44 case IrOpcode::kSpeculativeNumberLessThan:
45 case IrOpcode::kSpeculativeNumberLessThanOrEqual:
46 return ReduceSpeculativeNumberComparison(node);
47 case IrOpcode::kSpeculativeNumberAdd:
48 case IrOpcode::kSpeculativeNumberSubtract:
49 case IrOpcode::kSpeculativeSafeIntegerAdd:
50 case IrOpcode::kSpeculativeSafeIntegerSubtract:
51 case IrOpcode::kSpeculativeToNumber:
52 return ReduceSpeculativeNumberOperation(node);
53 case IrOpcode::kEffectPhi:
54 return ReduceEffectPhi(node);
55 case IrOpcode::kDead:
56 break;
57 case IrOpcode::kStart:
58 return ReduceStart(node);
59 default:
60 return ReduceOtherNode(node);
61 }
62 return NoChange();
63}
64
65// static
66RedundancyElimination::EffectPathChecks*
67RedundancyElimination::EffectPathChecks::Copy(Zone* zone,
68 EffectPathChecks const* checks) {
69 return new (zone->New(sizeof(EffectPathChecks))) EffectPathChecks(*checks);
70}
71
72// static
73RedundancyElimination::EffectPathChecks const*
74RedundancyElimination::EffectPathChecks::Empty(Zone* zone) {
75 return new (zone->New(sizeof(EffectPathChecks))) EffectPathChecks(nullptr, 0);
76}
77
78bool RedundancyElimination::EffectPathChecks::Equals(
79 EffectPathChecks const* that) const {
80 if (this->size_ != that->size_) return false;
81 Check* this_head = this->head_;
82 Check* that_head = that->head_;
83 while (this_head != that_head) {
84 if (this_head->node != that_head->node) return false;
85 this_head = this_head->next;
86 that_head = that_head->next;
87 }
88 return true;
89}
90
91void 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 Check* that_head = that->head_;
99 size_t that_size = that->size_;
100 while (that_size > size_) {
101 that_head = that_head->next;
102 that_size--;
103 }
104 while (size_ > that_size) {
105 head_ = head_->next;
106 size_--;
107 }
108
109 // Then we go through both lists in lock-step until we find
110 // the common tail.
111 while (head_ != that_head) {
112 DCHECK_LT(0u, size_);
113 DCHECK_NOT_NULL(head_);
114 size_--;
115 head_ = head_->next;
116 that_head = that_head->next;
117 }
118}
119
120RedundancyElimination::EffectPathChecks const*
121RedundancyElimination::EffectPathChecks::AddCheck(Zone* zone,
122 Node* node) const {
123 Check* head = new (zone->New(sizeof(Check))) Check(node, head_);
124 return new (zone->New(sizeof(EffectPathChecks)))
125 EffectPathChecks(head, size_ + 1);
126}
127
128namespace {
129
130// Does check {a} subsume check {b}?
131bool CheckSubsumes(Node const* a, Node const* b) {
132 if (a->op() != b->op()) {
133 if (a->opcode() == IrOpcode::kCheckInternalizedString &&
134 b->opcode() == IrOpcode::kCheckString) {
135 // CheckInternalizedString(node) implies CheckString(node)
136 } else if (a->opcode() == IrOpcode::kCheckNonEmptyString &&
137 b->opcode() == IrOpcode::kCheckString) {
138 // CheckNonEmptyString(node) implies CheckString(node)
139 } else if (a->opcode() == IrOpcode::kCheckNonEmptyOneByteString &&
140 b->opcode() == IrOpcode::kCheckNonEmptyString) {
141 // CheckNonEmptyOneByteString(node) implies CheckNonEmptyString(node)
142 } else if (a->opcode() == IrOpcode::kCheckNonEmptyTwoByteString &&
143 b->opcode() == IrOpcode::kCheckNonEmptyString) {
144 // CheckNonEmptyTwoByteString(node) implies CheckNonEmptyString(node)
145 } else if (a->opcode() == IrOpcode::kCheckNonEmptyOneByteString &&
146 b->opcode() == IrOpcode::kCheckString) {
147 // CheckNonEmptyOneByteString(node) implies CheckString(node)
148 } else if (a->opcode() == IrOpcode::kCheckNonEmptyTwoByteString &&
149 b->opcode() == IrOpcode::kCheckString) {
150 // CheckNonEmptyTwoByteString(node) implies CheckString(node)
151 } else if (a->opcode() == IrOpcode::kCheckSmi &&
152 b->opcode() == IrOpcode::kCheckNumber) {
153 // CheckSmi(node) implies CheckNumber(node)
154 } else if (a->opcode() == IrOpcode::kCheckedTaggedSignedToInt32 &&
155 b->opcode() == IrOpcode::kCheckedTaggedToInt32) {
156 // CheckedTaggedSignedToInt32(node) implies CheckedTaggedToInt32(node)
157 } else if (a->opcode() == IrOpcode::kCheckReceiver &&
158 b->opcode() == IrOpcode::kCheckReceiverOrNullOrUndefined) {
159 // CheckReceiver(node) implies CheckReceiverOrNullOrUndefined(node)
160 } else if (a->opcode() != b->opcode()) {
161 return false;
162 } else {
163 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 CheckMinusZeroParametersOf(a->op());
192 const CheckMinusZeroParameters& bp =
193 CheckMinusZeroParametersOf(b->op());
194 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 CheckTaggedInputParametersOf(a->op());
203 CheckTaggedInputParameters const& bp =
204 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 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 for (int i = a->op()->ValueInputCount(); --i >= 0;) {
220 if (a->InputAt(i) != b->InputAt(i)) return false;
221 }
222 return true;
223}
224
225bool TypeSubsumes(Node* node, Node* replacement) {
226 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 Type replacement_type = NodeProperties::GetType(replacement);
233 return replacement_type.Is(node_type);
234}
235
236} // namespace
237
238Node* RedundancyElimination::EffectPathChecks::LookupCheck(Node* node) const {
239 for (Check const* check = head_; check != nullptr; check = check->next) {
240 if (CheckSubsumes(check->node, node) && TypeSubsumes(node, check->node)) {
241 DCHECK(!check->node->IsDead());
242 return check->node;
243 }
244 }
245 return nullptr;
246}
247
248Node* RedundancyElimination::EffectPathChecks::LookupBoundsCheckFor(
249 Node* node) const {
250 for (Check const* check = head_; check != nullptr; check = check->next) {
251 if (check->node->opcode() == IrOpcode::kCheckBounds &&
252 check->node->InputAt(0) == node) {
253 return check->node;
254 }
255 }
256 return nullptr;
257}
258
259RedundancyElimination::EffectPathChecks const*
260RedundancyElimination::PathChecksForEffectNodes::Get(Node* node) const {
261 size_t const id = node->id();
262 if (id < info_for_node_.size()) return info_for_node_[id];
263 return nullptr;
264}
265
266void RedundancyElimination::PathChecksForEffectNodes::Set(
267 Node* node, EffectPathChecks const* checks) {
268 size_t const id = node->id();
269 if (id >= info_for_node_.size()) info_for_node_.resize(id + 1, nullptr);
270 info_for_node_[id] = checks;
271}
272
273Reduction RedundancyElimination::ReduceCheckNode(Node* node) {
274 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 if (checks == nullptr) return NoChange();
279 // See if we have another check that dominates us.
280 if (Node* check = checks->LookupCheck(node)) {
281 ReplaceWithValue(node, check);
282 return Replace(check);
283 }
284
285 // Learn from this check.
286 return UpdateChecks(node, checks->AddCheck(zone(), node));
287}
288
289Reduction RedundancyElimination::ReduceEffectPhi(Node* node) {
290 Node* const control = NodeProperties::GetControlInput(node);
291 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 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 for (int i = 0; i < input_count; ++i) {
302 Node* const effect = NodeProperties::GetEffectInput(node, i);
303 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 EffectPathChecks* checks = EffectPathChecks::Copy(
309 zone(), node_checks_.Get(NodeProperties::GetEffectInput(node, 0)));
310 for (int i = 1; i < input_count; ++i) {
311 Node* const input = NodeProperties::GetEffectInput(node, i);
312 checks->Merge(node_checks_.Get(input));
313 }
314 return UpdateChecks(node, checks);
315}
316
317Reduction RedundancyElimination::ReduceSpeculativeNumberComparison(Node* node) {
318 NumberOperationHint const hint = NumberOperationHintOf(node->op());
319 Node* const first = NodeProperties::GetValueInput(node, 0);
320 Type const first_type = NodeProperties::GetType(first);
321 Node* const second = NodeProperties::GetValueInput(node, 1);
322 Type const second_type = NodeProperties::GetType(second);
323 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 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 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 if (!first_type.Is(Type::UnsignedSmall())) {
340 if (Node* check = checks->LookupBoundsCheckFor(first)) {
341 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 NodeProperties::ReplaceValueInput(node, check, 0);
347 Reduction const reduction = ReduceSpeculativeNumberComparison(node);
348 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 if (!second_type.Is(Type::UnsignedSmall())) {
358 if (Node* check = checks->LookupBoundsCheckFor(second)) {
359 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 NodeProperties::ReplaceValueInput(node, check, 1);
365 Reduction const reduction = ReduceSpeculativeNumberComparison(node);
366 return reduction.Changed() ? reduction : Changed(node);
367 }
368 }
369 }
370 }
371
372 return UpdateChecks(node, checks);
373}
374
375Reduction 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 Node* const first = NodeProperties::GetValueInput(node, 0);
385 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 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 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 if (!NodeProperties::GetType(first).Is(NodeProperties::GetType(check))) {
401 NodeProperties::ReplaceValueInput(node, check, 0);
402 }
403 }
404
405 return UpdateChecks(node, checks);
406}
407
408Reduction RedundancyElimination::ReduceStart(Node* node) {
409 return UpdateChecks(node, EffectPathChecks::Empty(zone()));
410}
411
412Reduction RedundancyElimination::ReduceOtherNode(Node* node) {
413 if (node->op()->EffectInputCount() == 1) {
414 if (node->op()->EffectOutputCount() == 1) {
415 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
426Reduction RedundancyElimination::TakeChecksFromFirstEffect(Node* node) {
427 DCHECK_EQ(1, node->op()->EffectOutputCount());
428 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 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 return UpdateChecks(node, checks);
436}
437
438Reduction 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 if (checks != original) {
444 if (original == nullptr || !checks->Equals(original)) {
445 node_checks_.Set(node, checks);
446 return Changed(node);
447 }
448 }
449 return NoChange();
450}
451
452} // namespace compiler
453} // namespace internal
454} // namespace v8
455