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 | RedundancyElimination::RedundancyElimination(Editor* editor, Zone* zone) |
15 | : AdvancedReducer(editor), node_checks_(zone), zone_(zone) {} |
16 | |
17 | RedundancyElimination::~RedundancyElimination() = default; |
18 | |
19 | Reduction 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 |
66 | RedundancyElimination::EffectPathChecks* |
67 | RedundancyElimination::EffectPathChecks::Copy(Zone* zone, |
68 | EffectPathChecks const* checks) { |
69 | return new (zone->New(sizeof(EffectPathChecks))) EffectPathChecks(*checks); |
70 | } |
71 | |
72 | // static |
73 | RedundancyElimination::EffectPathChecks const* |
74 | RedundancyElimination::EffectPathChecks::Empty(Zone* zone) { |
75 | return new (zone->New(sizeof(EffectPathChecks))) EffectPathChecks(nullptr, 0); |
76 | } |
77 | |
78 | bool 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 | |
91 | 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 | 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 | |
120 | RedundancyElimination::EffectPathChecks const* |
121 | RedundancyElimination::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 | |
128 | namespace { |
129 | |
130 | // Does check {a} subsume check {b}? |
131 | bool 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 | |
225 | bool 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 | |
238 | Node* 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 | |
248 | Node* 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 | |
259 | RedundancyElimination::EffectPathChecks const* |
260 | RedundancyElimination::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 | |
266 | void 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 | |
273 | Reduction 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 | |
289 | Reduction 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 | |
317 | Reduction 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 | |
375 | 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 | 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 | |
408 | Reduction RedundancyElimination::ReduceStart(Node* node) { |
409 | return UpdateChecks(node, EffectPathChecks::Empty(zone())); |
410 | } |
411 | |
412 | Reduction 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 | |
426 | Reduction 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 | |
438 | 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 | 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 | |