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 912249 : RedundancyElimination::RedundancyElimination(Editor* editor, Zone* zone)
15 1824498 : : AdvancedReducer(editor), node_checks_(zone), zone_(zone) {}
16 :
17 : RedundancyElimination::~RedundancyElimination() = default;
18 :
19 158915789 : Reduction RedundancyElimination::Reduce(Node* node) {
20 84696656 : if (node_checks_.Get(node)) return NoChange();
21 74219133 : 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 937911 : return ReduceCheckNode(node);
40 : case IrOpcode::kSpeculativeNumberEqual:
41 : case IrOpcode::kSpeculativeNumberLessThan:
42 : case IrOpcode::kSpeculativeNumberLessThanOrEqual:
43 173665 : return ReduceSpeculativeNumberComparison(node);
44 : case IrOpcode::kSpeculativeNumberAdd:
45 : case IrOpcode::kSpeculativeNumberSubtract:
46 : case IrOpcode::kSpeculativeSafeIntegerAdd:
47 : case IrOpcode::kSpeculativeSafeIntegerSubtract:
48 : case IrOpcode::kSpeculativeToNumber:
49 411609 : return ReduceSpeculativeNumberOperation(node);
50 : case IrOpcode::kEffectPhi:
51 1528361 : return ReduceEffectPhi(node);
52 : case IrOpcode::kDead:
53 : break;
54 : case IrOpcode::kStart:
55 912262 : return ReduceStart(node);
56 : default:
57 70227907 : return ReduceOtherNode(node);
58 : }
59 : return NoChange();
60 : }
61 :
62 : // static
63 : RedundancyElimination::EffectPathChecks*
64 1008124 : RedundancyElimination::EffectPathChecks::Copy(Zone* zone,
65 : EffectPathChecks const* checks) {
66 1008124 : return new (zone->New(sizeof(EffectPathChecks))) EffectPathChecks(*checks);
67 : }
68 :
69 : // static
70 : RedundancyElimination::EffectPathChecks const*
71 0 : RedundancyElimination::EffectPathChecks::Empty(Zone* zone) {
72 912234 : 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 1358921 : 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 1358921 : Check* that_head = that->head_;
96 1358921 : size_t that_size = that->size_;
97 2862046 : while (that_size > size_) {
98 144204 : that_head = that_head->next;
99 144204 : that_size--;
100 : }
101 1396572 : while (size_ > that_size) {
102 37651 : head_ = head_->next;
103 37651 : size_--;
104 : }
105 :
106 : // Then we go through both lists in lock-step until we find
107 : // the common tail.
108 1363069 : while (head_ != that_head) {
109 : DCHECK_LT(0u, size_);
110 : DCHECK_NOT_NULL(head_);
111 4148 : size_--;
112 4148 : head_ = head_->next;
113 4148 : that_head = that_head->next;
114 : }
115 1358921 : }
116 :
117 : RedundancyElimination::EffectPathChecks const*
118 426736 : RedundancyElimination::EffectPathChecks::AddCheck(Zone* zone,
119 : Node* node) const {
120 426736 : Check* head = new (zone->New(sizeof(Check))) Check(node, head_);
121 : return new (zone->New(sizeof(EffectPathChecks)))
122 853478 : EffectPathChecks(head, size_ + 1);
123 : }
124 :
125 : namespace {
126 :
127 : // Does check {a} subsume check {b}?
128 7060866 : bool CheckSubsumes(Node const* a, Node const* b) {
129 4770419 : if (a->op() != b->op()) {
130 2551974 : if (a->opcode() == IrOpcode::kCheckInternalizedString &&
131 : b->opcode() == IrOpcode::kCheckString) {
132 : // CheckInternalizedString(node) implies CheckString(node)
133 2597725 : } else if (a->opcode() == IrOpcode::kCheckSmi &&
134 : b->opcode() == IrOpcode::kCheckNumber) {
135 : // CheckSmi(node) implies CheckNumber(node)
136 2665102 : } else if (a->opcode() == IrOpcode::kCheckedTaggedSignedToInt32 &&
137 : b->opcode() == IrOpcode::kCheckedTaggedToInt32) {
138 : // CheckedTaggedSignedToInt32(node) implies CheckedTaggedToInt32(node)
139 2553371 : } else if (a->opcode() == IrOpcode::kCheckReceiver &&
140 : b->opcode() == IrOpcode::kCheckReceiverOrNullOrUndefined) {
141 : // CheckReceiver(node) implies CheckReceiverOrNullOrUndefined(node)
142 2548830 : } else if (a->opcode() != b->opcode()) {
143 : return false;
144 : } else {
145 78547 : 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::kCheckedUint32Bounds:
158 : case IrOpcode::kCheckedUint32ToInt32:
159 : case IrOpcode::kCheckedUint32ToTaggedSigned:
160 : case IrOpcode::kCheckedUint64Bounds:
161 : case IrOpcode::kCheckedUint64ToInt32:
162 : case IrOpcode::kCheckedUint64ToTaggedSigned:
163 : break;
164 : case IrOpcode::kCheckedFloat64ToInt32:
165 : case IrOpcode::kCheckedFloat64ToInt64:
166 : case IrOpcode::kCheckedTaggedToInt32:
167 : case IrOpcode::kCheckedTaggedToInt64: {
168 99 : const CheckMinusZeroParameters& ap =
169 99 : CheckMinusZeroParametersOf(a->op());
170 99 : const CheckMinusZeroParameters& bp =
171 99 : CheckMinusZeroParametersOf(b->op());
172 99 : if (ap.mode() != bp.mode()) {
173 : return false;
174 : }
175 : break;
176 : }
177 : case IrOpcode::kCheckedTaggedToFloat64:
178 : case IrOpcode::kCheckedTruncateTaggedToWord32: {
179 12414 : CheckTaggedInputParameters const& ap =
180 12414 : CheckTaggedInputParametersOf(a->op());
181 12414 : CheckTaggedInputParameters const& bp =
182 12414 : CheckTaggedInputParametersOf(b->op());
183 : // {a} subsumes {b} if the modes are either the same, or {a} checks
184 : // for Number, in which case {b} will be subsumed no matter what.
185 12414 : if (ap.mode() != bp.mode() &&
186 : ap.mode() != CheckTaggedInputMode::kNumber) {
187 : return false;
188 : }
189 : break;
190 : }
191 : default:
192 : DCHECK(!IsCheckedWithFeedback(a->op()));
193 : return false;
194 : }
195 : }
196 : }
197 7457491 : for (int i = a->op()->ValueInputCount(); --i >= 0;) {
198 2646573 : if (a->InputAt(i) != b->InputAt(i)) return false;
199 : }
200 : return true;
201 : }
202 :
203 254907 : bool TypeSubsumes(Node* node, Node* replacement) {
204 254907 : if (!NodeProperties::IsTyped(node) || !NodeProperties::IsTyped(replacement)) {
205 : // If either node is untyped, we are running during an untyped optimization
206 : // phase, and replacement is OK.
207 : return true;
208 : }
209 : Type node_type = NodeProperties::GetType(node);
210 124768 : Type replacement_type = NodeProperties::GetType(replacement);
211 124768 : return replacement_type.Is(node_type);
212 : }
213 :
214 : } // namespace
215 :
216 681451 : Node* RedundancyElimination::EffectPathChecks::LookupCheck(Node* node) const {
217 5197227 : for (Check const* check = head_; check != nullptr; check = check->next) {
218 4770412 : if (CheckSubsumes(check->node, node) && TypeSubsumes(node, check->node)) {
219 : DCHECK(!check->node->IsDead());
220 254875 : return check->node;
221 : }
222 : }
223 : return nullptr;
224 : }
225 :
226 356837 : Node* RedundancyElimination::EffectPathChecks::LookupBoundsCheckFor(
227 : Node* node) const {
228 762755 : for (Check const* check = head_; check != nullptr; check = check->next) {
229 1011160 : if (check->node->opcode() == IrOpcode::kCheckBounds &&
230 : check->node->InputAt(0) == node) {
231 : return check->node;
232 : }
233 : }
234 : return nullptr;
235 : }
236 :
237 : RedundancyElimination::EffectPathChecks const*
238 134873455 : RedundancyElimination::PathChecksForEffectNodes::Get(Node* node) const {
239 134873455 : size_t const id = node->id();
240 360198385 : if (id < info_for_node_.size()) return info_for_node_[id];
241 : return nullptr;
242 : }
243 :
244 20852868 : void RedundancyElimination::PathChecksForEffectNodes::Set(
245 20852868 : Node* node, EffectPathChecks const* checks) {
246 20852868 : size_t const id = node->id();
247 41705736 : if (id >= info_for_node_.size()) info_for_node_.resize(id + 1, nullptr);
248 20852864 : info_for_node_[id] = checks;
249 20852864 : }
250 :
251 1364631 : Reduction RedundancyElimination::ReduceCheckNode(Node* node) {
252 937895 : Node* const effect = NodeProperties::GetEffectInput(node);
253 : EffectPathChecks const* checks = node_checks_.Get(effect);
254 : // If we do not know anything about the predecessor, do not propagate just yet
255 : // because we will have to recompute anyway once we compute the predecessor.
256 938059 : if (checks == nullptr) return NoChange();
257 : // See if we have another check that dominates us.
258 681451 : if (Node* check = checks->LookupCheck(node)) {
259 254873 : ReplaceWithValue(node, check);
260 : return Replace(check);
261 : }
262 :
263 : // Learn from this check.
264 426736 : return UpdateChecks(node, checks->AddCheck(zone(), node));
265 : }
266 :
267 3956291 : Reduction RedundancyElimination::ReduceEffectPhi(Node* node) {
268 1528353 : Node* const control = NodeProperties::GetControlInput(node);
269 1528373 : if (control->opcode() == IrOpcode::kLoop) {
270 : // Here we rely on having only reducible loops:
271 : // The loop entry edge always dominates the header, so we can just use
272 : // the information from the loop entry edge.
273 108555 : return TakeChecksFromFirstEffect(node);
274 : }
275 : DCHECK_EQ(IrOpcode::kMerge, control->opcode());
276 :
277 : // Shortcut for the case when we do not know anything about some input.
278 1419818 : int const input_count = node->op()->EffectInputCount();
279 5340692 : for (int i = 0; i < input_count; ++i) {
280 4332568 : Node* const effect = NodeProperties::GetEffectInput(node, i);
281 4332599 : if (node_checks_.Get(effect) == nullptr) return NoChange();
282 : }
283 :
284 : // Make a copy of the first input's checks and merge with the checks
285 : // from other inputs.
286 : EffectPathChecks* checks = EffectPathChecks::Copy(
287 2016244 : zone(), node_checks_.Get(NodeProperties::GetEffectInput(node, 0)));
288 2367056 : for (int i = 1; i < input_count; ++i) {
289 1358940 : Node* const input = NodeProperties::GetEffectInput(node, i);
290 1358943 : checks->Merge(node_checks_.Get(input));
291 : }
292 1008116 : return UpdateChecks(node, checks);
293 : }
294 :
295 173903 : Reduction RedundancyElimination::ReduceSpeculativeNumberComparison(Node* node) {
296 173903 : NumberOperationHint const hint = NumberOperationHintOf(node->op());
297 173900 : Node* const first = NodeProperties::GetValueInput(node, 0);
298 173896 : Type const first_type = NodeProperties::GetType(first);
299 173896 : Node* const second = NodeProperties::GetValueInput(node, 1);
300 173888 : Type const second_type = NodeProperties::GetType(second);
301 173888 : Node* const effect = NodeProperties::GetEffectInput(node);
302 : EffectPathChecks const* checks = node_checks_.Get(effect);
303 :
304 : // If we do not know anything about the predecessor, do not propagate just yet
305 : // because we will have to recompute anyway once we compute the predecessor.
306 173920 : if (checks == nullptr) return NoChange();
307 :
308 : // Avoid the potentially expensive lookups below if the {node}
309 : // has seen non-Smi inputs in the past, which is a clear signal
310 : // that the comparison is probably not performed on a value that
311 : // already passed an array bounds check.
312 92979 : if (hint == NumberOperationHint::kSignedSmall) {
313 : // Don't bother trying to find a CheckBounds for the {first} input
314 : // if it's type is already in UnsignedSmall range, since the bounds
315 : // check is only going to narrow that range further, but the result
316 : // is not going to make the representation selection any better.
317 82312 : if (!first_type.Is(Type::UnsignedSmall())) {
318 20771 : if (Node* check = checks->LookupBoundsCheckFor(first)) {
319 79 : if (!first_type.Is(NodeProperties::GetType(check))) {
320 : // Replace the {first} input with the {check}. This is safe,
321 : // despite the fact that {check} can truncate -0 to 0, because
322 : // the regular Number comparisons in JavaScript also identify
323 : // 0 and -0 (unlike special comparisons as Object.is).
324 79 : NodeProperties::ReplaceValueInput(node, check, 0);
325 79 : Reduction const reduction = ReduceSpeculativeNumberComparison(node);
326 79 : return reduction.Changed() ? reduction : Changed(node);
327 : }
328 : }
329 : }
330 :
331 : // Don't bother trying to find a CheckBounds for the {second} 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 82232 : if (!second_type.Is(Type::UnsignedSmall())) {
336 66075 : if (Node* check = checks->LookupBoundsCheckFor(second)) {
337 161 : if (!second_type.Is(NodeProperties::GetType(check))) {
338 : // Replace the {second} 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 161 : NodeProperties::ReplaceValueInput(node, check, 1);
343 161 : Reduction const reduction = ReduceSpeculativeNumberComparison(node);
344 161 : return reduction.Changed() ? reduction : Changed(node);
345 : }
346 : }
347 : }
348 : }
349 :
350 92740 : return UpdateChecks(node, checks);
351 : }
352 :
353 411610 : Reduction RedundancyElimination::ReduceSpeculativeNumberOperation(Node* node) {
354 : DCHECK(node->opcode() == IrOpcode::kSpeculativeNumberAdd ||
355 : node->opcode() == IrOpcode::kSpeculativeNumberSubtract ||
356 : node->opcode() == IrOpcode::kSpeculativeSafeIntegerAdd ||
357 : node->opcode() == IrOpcode::kSpeculativeSafeIntegerSubtract ||
358 : node->opcode() == IrOpcode::kSpeculativeToNumber);
359 : DCHECK_EQ(1, node->op()->EffectInputCount());
360 : DCHECK_EQ(1, node->op()->EffectOutputCount());
361 :
362 411610 : Node* const first = NodeProperties::GetValueInput(node, 0);
363 411591 : Node* const effect = NodeProperties::GetEffectInput(node);
364 : EffectPathChecks const* checks = node_checks_.Get(effect);
365 : // If we do not know anything about the predecessor, do not propagate just yet
366 : // because we will have to recompute anyway once we compute the predecessor.
367 411659 : if (checks == nullptr) return NoChange();
368 :
369 : // Check if there's a CheckBounds operation on {first}
370 : // in the graph already, which we might be able to
371 : // reuse here to improve the representation selection
372 : // for the {node} later on.
373 270028 : if (Node* check = checks->LookupBoundsCheckFor(first)) {
374 : // Only use the bounds {check} if its type is better
375 : // than the type of the {first} node, otherwise we
376 : // would end up replacing NumberConstant inputs with
377 : // CheckBounds operations, which is kind of pointless.
378 13242 : if (!NodeProperties::GetType(first).Is(NodeProperties::GetType(check))) {
379 3429 : NodeProperties::ReplaceValueInput(node, check, 0);
380 : }
381 : }
382 :
383 270024 : return UpdateChecks(node, checks);
384 : }
385 :
386 912234 : Reduction RedundancyElimination::ReduceStart(Node* node) {
387 912252 : return UpdateChecks(node, EffectPathChecks::Empty(zone()));
388 : }
389 :
390 70229312 : Reduction RedundancyElimination::ReduceOtherNode(Node* node) {
391 70229312 : if (node->op()->EffectInputCount() == 1) {
392 22617851 : if (node->op()->EffectOutputCount() == 1) {
393 20991920 : return TakeChecksFromFirstEffect(node);
394 : } else {
395 : // Effect terminators should be handled specially.
396 : return NoChange();
397 : }
398 : }
399 : DCHECK_EQ(0, node->op()->EffectInputCount());
400 : DCHECK_EQ(0, node->op()->EffectOutputCount());
401 : return NoChange();
402 : }
403 :
404 21100497 : Reduction RedundancyElimination::TakeChecksFromFirstEffect(Node* node) {
405 : DCHECK_EQ(1, node->op()->EffectOutputCount());
406 21100497 : Node* const effect = NodeProperties::GetEffectInput(node);
407 : EffectPathChecks const* checks = node_checks_.Get(effect);
408 : // If we do not know anything about the predecessor, do not propagate just yet
409 : // because we will have to recompute anyway once we compute the predecessor.
410 21100575 : if (checks == nullptr) return NoChange();
411 : // We just propagate the information from the effect input (ideally,
412 : // we would only revisit effect uses if there is change).
413 18143496 : return UpdateChecks(node, checks);
414 : }
415 :
416 20852924 : Reduction RedundancyElimination::UpdateChecks(Node* node,
417 : EffectPathChecks const* checks) {
418 : EffectPathChecks const* original = node_checks_.Get(node);
419 : // Only signal that the {node} has Changed, if the information about {checks}
420 : // has changed wrt. the {original}.
421 20852924 : if (checks != original) {
422 20852981 : if (original == nullptr || !checks->Equals(original)) {
423 20852924 : node_checks_.Set(node, checks);
424 : return Changed(node);
425 : }
426 : }
427 : return NoChange();
428 : }
429 :
430 : } // namespace compiler
431 : } // namespace internal
432 183867 : } // namespace v8
|
