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/typed-optimization.h" |
6 | |
7 | #include "src/base/optional.h" |
8 | #include "src/compiler/compilation-dependencies.h" |
9 | #include "src/compiler/js-graph.h" |
10 | #include "src/compiler/js-heap-broker.h" |
11 | #include "src/compiler/node-matchers.h" |
12 | #include "src/compiler/node-properties.h" |
13 | #include "src/compiler/simplified-operator.h" |
14 | #include "src/compiler/type-cache.h" |
15 | #include "src/isolate-inl.h" |
16 | |
17 | namespace v8 { |
18 | namespace internal { |
19 | namespace compiler { |
20 | |
21 | TypedOptimization::TypedOptimization(Editor* editor, |
22 | CompilationDependencies* dependencies, |
23 | JSGraph* jsgraph, JSHeapBroker* broker) |
24 | : AdvancedReducer(editor), |
25 | dependencies_(dependencies), |
26 | jsgraph_(jsgraph), |
27 | broker_(broker), |
28 | true_type_( |
29 | Type::HeapConstant(broker, factory()->true_value(), graph()->zone())), |
30 | false_type_(Type::HeapConstant(broker, factory()->false_value(), |
31 | graph()->zone())), |
32 | type_cache_(TypeCache::Get()) {} |
33 | |
34 | TypedOptimization::~TypedOptimization() = default; |
35 | |
36 | Reduction TypedOptimization::Reduce(Node* node) { |
37 | DisallowHeapAccess no_heap_access; |
38 | switch (node->opcode()) { |
39 | case IrOpcode::kConvertReceiver: |
40 | return ReduceConvertReceiver(node); |
41 | case IrOpcode::kCheckHeapObject: |
42 | return ReduceCheckHeapObject(node); |
43 | case IrOpcode::kCheckNotTaggedHole: |
44 | return ReduceCheckNotTaggedHole(node); |
45 | case IrOpcode::kCheckMaps: |
46 | return ReduceCheckMaps(node); |
47 | case IrOpcode::kCheckNumber: |
48 | return ReduceCheckNumber(node); |
49 | case IrOpcode::kCheckString: |
50 | return ReduceCheckString(node); |
51 | case IrOpcode::kCheckEqualsInternalizedString: |
52 | return ReduceCheckEqualsInternalizedString(node); |
53 | case IrOpcode::kCheckEqualsSymbol: |
54 | return ReduceCheckEqualsSymbol(node); |
55 | case IrOpcode::kLoadField: |
56 | return ReduceLoadField(node); |
57 | case IrOpcode::kNumberCeil: |
58 | case IrOpcode::kNumberRound: |
59 | case IrOpcode::kNumberTrunc: |
60 | return ReduceNumberRoundop(node); |
61 | case IrOpcode::kNumberFloor: |
62 | return ReduceNumberFloor(node); |
63 | case IrOpcode::kNumberSilenceNaN: |
64 | return ReduceNumberSilenceNaN(node); |
65 | case IrOpcode::kNumberToUint8Clamped: |
66 | return ReduceNumberToUint8Clamped(node); |
67 | case IrOpcode::kPhi: |
68 | return ReducePhi(node); |
69 | case IrOpcode::kReferenceEqual: |
70 | return ReduceReferenceEqual(node); |
71 | case IrOpcode::kStringEqual: |
72 | case IrOpcode::kStringLessThan: |
73 | case IrOpcode::kStringLessThanOrEqual: |
74 | return ReduceStringComparison(node); |
75 | case IrOpcode::kStringLength: |
76 | return ReduceStringLength(node); |
77 | case IrOpcode::kSameValue: |
78 | return ReduceSameValue(node); |
79 | case IrOpcode::kSelect: |
80 | return ReduceSelect(node); |
81 | case IrOpcode::kTypeOf: |
82 | return ReduceTypeOf(node); |
83 | case IrOpcode::kToBoolean: |
84 | return ReduceToBoolean(node); |
85 | case IrOpcode::kSpeculativeToNumber: |
86 | return ReduceSpeculativeToNumber(node); |
87 | case IrOpcode::kSpeculativeNumberAdd: |
88 | return ReduceSpeculativeNumberAdd(node); |
89 | case IrOpcode::kSpeculativeNumberSubtract: |
90 | case IrOpcode::kSpeculativeNumberMultiply: |
91 | case IrOpcode::kSpeculativeNumberDivide: |
92 | case IrOpcode::kSpeculativeNumberModulus: |
93 | return ReduceSpeculativeNumberBinop(node); |
94 | case IrOpcode::kSpeculativeNumberEqual: |
95 | case IrOpcode::kSpeculativeNumberLessThan: |
96 | case IrOpcode::kSpeculativeNumberLessThanOrEqual: |
97 | return ReduceSpeculativeNumberComparison(node); |
98 | default: |
99 | break; |
100 | } |
101 | return NoChange(); |
102 | } |
103 | |
104 | namespace { |
105 | |
106 | base::Optional<MapRef> GetStableMapFromObjectType(JSHeapBroker* broker, |
107 | Type object_type) { |
108 | if (object_type.IsHeapConstant()) { |
109 | HeapObjectRef object = object_type.AsHeapConstant()->Ref(); |
110 | MapRef object_map = object.map(); |
111 | if (object_map.is_stable()) return object_map; |
112 | } |
113 | return {}; |
114 | } |
115 | |
116 | } // namespace |
117 | |
118 | Reduction TypedOptimization::ReduceConvertReceiver(Node* node) { |
119 | Node* const value = NodeProperties::GetValueInput(node, 0); |
120 | Type const value_type = NodeProperties::GetType(value); |
121 | Node* const global_proxy = NodeProperties::GetValueInput(node, 1); |
122 | if (value_type.Is(Type::Receiver())) { |
123 | ReplaceWithValue(node, value); |
124 | return Replace(value); |
125 | } else if (value_type.Is(Type::NullOrUndefined())) { |
126 | ReplaceWithValue(node, global_proxy); |
127 | return Replace(global_proxy); |
128 | } |
129 | return NoChange(); |
130 | } |
131 | |
132 | Reduction TypedOptimization::ReduceCheckHeapObject(Node* node) { |
133 | Node* const input = NodeProperties::GetValueInput(node, 0); |
134 | Type const input_type = NodeProperties::GetType(input); |
135 | if (!input_type.Maybe(Type::SignedSmall())) { |
136 | ReplaceWithValue(node, input); |
137 | return Replace(input); |
138 | } |
139 | return NoChange(); |
140 | } |
141 | |
142 | Reduction TypedOptimization::ReduceCheckNotTaggedHole(Node* node) { |
143 | Node* const input = NodeProperties::GetValueInput(node, 0); |
144 | Type const input_type = NodeProperties::GetType(input); |
145 | if (!input_type.Maybe(Type::Hole())) { |
146 | ReplaceWithValue(node, input); |
147 | return Replace(input); |
148 | } |
149 | return NoChange(); |
150 | } |
151 | |
152 | Reduction TypedOptimization::ReduceCheckMaps(Node* node) { |
153 | // The CheckMaps(o, ...map...) can be eliminated if map is stable, |
154 | // o has type Constant(object) and map == object->map, and either |
155 | // (1) map cannot transition further, or |
156 | // (2) we can add a code dependency on the stability of map |
157 | // (to guard the Constant type information). |
158 | Node* const object = NodeProperties::GetValueInput(node, 0); |
159 | Type const object_type = NodeProperties::GetType(object); |
160 | Node* const effect = NodeProperties::GetEffectInput(node); |
161 | base::Optional<MapRef> object_map = |
162 | GetStableMapFromObjectType(broker(), object_type); |
163 | if (object_map.has_value()) { |
164 | for (int i = 1; i < node->op()->ValueInputCount(); ++i) { |
165 | Node* const map = NodeProperties::GetValueInput(node, i); |
166 | Type const map_type = NodeProperties::GetType(map); |
167 | if (map_type.IsHeapConstant() && |
168 | map_type.AsHeapConstant()->Ref().equals(*object_map)) { |
169 | if (object_map->CanTransition()) { |
170 | dependencies()->DependOnStableMap(*object_map); |
171 | } |
172 | return Replace(effect); |
173 | } |
174 | } |
175 | } |
176 | return NoChange(); |
177 | } |
178 | |
179 | Reduction TypedOptimization::ReduceCheckNumber(Node* node) { |
180 | Node* const input = NodeProperties::GetValueInput(node, 0); |
181 | Type const input_type = NodeProperties::GetType(input); |
182 | if (input_type.Is(Type::Number())) { |
183 | ReplaceWithValue(node, input); |
184 | return Replace(input); |
185 | } |
186 | return NoChange(); |
187 | } |
188 | |
189 | Reduction TypedOptimization::ReduceCheckString(Node* node) { |
190 | Node* const input = NodeProperties::GetValueInput(node, 0); |
191 | Type const input_type = NodeProperties::GetType(input); |
192 | if (input_type.Is(Type::String())) { |
193 | ReplaceWithValue(node, input); |
194 | return Replace(input); |
195 | } |
196 | return NoChange(); |
197 | } |
198 | |
199 | Reduction TypedOptimization::ReduceCheckEqualsInternalizedString(Node* node) { |
200 | Node* const exp = NodeProperties::GetValueInput(node, 0); |
201 | Type const exp_type = NodeProperties::GetType(exp); |
202 | Node* const val = NodeProperties::GetValueInput(node, 1); |
203 | Type const val_type = NodeProperties::GetType(val); |
204 | Node* const effect = NodeProperties::GetEffectInput(node); |
205 | if (val_type.Is(exp_type)) return Replace(effect); |
206 | // TODO(turbofan): Should we also try to optimize the |
207 | // non-internalized String case for {val} here? |
208 | return NoChange(); |
209 | } |
210 | |
211 | Reduction TypedOptimization::ReduceCheckEqualsSymbol(Node* node) { |
212 | Node* const exp = NodeProperties::GetValueInput(node, 0); |
213 | Type const exp_type = NodeProperties::GetType(exp); |
214 | Node* const val = NodeProperties::GetValueInput(node, 1); |
215 | Type const val_type = NodeProperties::GetType(val); |
216 | Node* const effect = NodeProperties::GetEffectInput(node); |
217 | if (val_type.Is(exp_type)) return Replace(effect); |
218 | return NoChange(); |
219 | } |
220 | |
221 | Reduction TypedOptimization::ReduceLoadField(Node* node) { |
222 | Node* const object = NodeProperties::GetValueInput(node, 0); |
223 | Type const object_type = NodeProperties::GetType(object); |
224 | FieldAccess const& access = FieldAccessOf(node->op()); |
225 | if (access.base_is_tagged == kTaggedBase && |
226 | access.offset == HeapObject::kMapOffset) { |
227 | // We can replace LoadField[Map](o) with map if is stable, and |
228 | // o has type Constant(object) and map == object->map, and either |
229 | // (1) map cannot transition further, or |
230 | // (2) deoptimization is enabled and we can add a code dependency on the |
231 | // stability of map (to guard the Constant type information). |
232 | base::Optional<MapRef> object_map = |
233 | GetStableMapFromObjectType(broker(), object_type); |
234 | if (object_map.has_value()) { |
235 | dependencies()->DependOnStableMap(*object_map); |
236 | Node* const value = jsgraph()->Constant(*object_map); |
237 | ReplaceWithValue(node, value); |
238 | return Replace(value); |
239 | } |
240 | } |
241 | return NoChange(); |
242 | } |
243 | |
244 | Reduction TypedOptimization::ReduceNumberFloor(Node* node) { |
245 | Node* const input = NodeProperties::GetValueInput(node, 0); |
246 | Type const input_type = NodeProperties::GetType(input); |
247 | if (input_type.Is(type_cache_->kIntegerOrMinusZeroOrNaN)) { |
248 | return Replace(input); |
249 | } |
250 | if (input_type.Is(Type::PlainNumber()) && |
251 | (input->opcode() == IrOpcode::kNumberDivide || |
252 | input->opcode() == IrOpcode::kSpeculativeNumberDivide)) { |
253 | Node* const lhs = NodeProperties::GetValueInput(input, 0); |
254 | Type const lhs_type = NodeProperties::GetType(lhs); |
255 | Node* const rhs = NodeProperties::GetValueInput(input, 1); |
256 | Type const rhs_type = NodeProperties::GetType(rhs); |
257 | if (lhs_type.Is(Type::Unsigned32()) && rhs_type.Is(Type::Unsigned32())) { |
258 | // We can replace |
259 | // |
260 | // NumberFloor(NumberDivide(lhs: unsigned32, |
261 | // rhs: unsigned32)): plain-number |
262 | // |
263 | // with |
264 | // |
265 | // NumberToUint32(NumberDivide(lhs, rhs)) |
266 | // |
267 | // and just smash the type [0...lhs.Max] on the {node}, |
268 | // as the truncated result must be loewr than {lhs}'s maximum |
269 | // value (note that {rhs} cannot be less than 1 due to the |
270 | // plain-number type constraint on the {node}). |
271 | NodeProperties::ChangeOp(node, simplified()->NumberToUint32()); |
272 | NodeProperties::SetType(node, |
273 | Type::Range(0, lhs_type.Max(), graph()->zone())); |
274 | return Changed(node); |
275 | } |
276 | } |
277 | return NoChange(); |
278 | } |
279 | |
280 | Reduction TypedOptimization::ReduceNumberRoundop(Node* node) { |
281 | Node* const input = NodeProperties::GetValueInput(node, 0); |
282 | Type const input_type = NodeProperties::GetType(input); |
283 | if (input_type.Is(type_cache_->kIntegerOrMinusZeroOrNaN)) { |
284 | return Replace(input); |
285 | } |
286 | return NoChange(); |
287 | } |
288 | |
289 | Reduction TypedOptimization::ReduceNumberSilenceNaN(Node* node) { |
290 | Node* const input = NodeProperties::GetValueInput(node, 0); |
291 | Type const input_type = NodeProperties::GetType(input); |
292 | if (input_type.Is(Type::OrderedNumber())) { |
293 | return Replace(input); |
294 | } |
295 | return NoChange(); |
296 | } |
297 | |
298 | Reduction TypedOptimization::ReduceNumberToUint8Clamped(Node* node) { |
299 | Node* const input = NodeProperties::GetValueInput(node, 0); |
300 | Type const input_type = NodeProperties::GetType(input); |
301 | if (input_type.Is(type_cache_->kUint8)) { |
302 | return Replace(input); |
303 | } |
304 | return NoChange(); |
305 | } |
306 | |
307 | Reduction TypedOptimization::ReducePhi(Node* node) { |
308 | // Try to narrow the type of the Phi {node}, which might be more precise now |
309 | // after lowering based on types, i.e. a SpeculativeNumberAdd has a more |
310 | // precise type than the JSAdd that was in the graph when the Typer was run. |
311 | DCHECK_EQ(IrOpcode::kPhi, node->opcode()); |
312 | int arity = node->op()->ValueInputCount(); |
313 | Type type = NodeProperties::GetType(node->InputAt(0)); |
314 | for (int i = 1; i < arity; ++i) { |
315 | type = Type::Union(type, NodeProperties::GetType(node->InputAt(i)), |
316 | graph()->zone()); |
317 | } |
318 | Type const node_type = NodeProperties::GetType(node); |
319 | if (!node_type.Is(type)) { |
320 | type = Type::Intersect(node_type, type, graph()->zone()); |
321 | NodeProperties::SetType(node, type); |
322 | return Changed(node); |
323 | } |
324 | return NoChange(); |
325 | } |
326 | |
327 | Reduction TypedOptimization::ReduceReferenceEqual(Node* node) { |
328 | DCHECK_EQ(IrOpcode::kReferenceEqual, node->opcode()); |
329 | Node* const lhs = NodeProperties::GetValueInput(node, 0); |
330 | Node* const rhs = NodeProperties::GetValueInput(node, 1); |
331 | Type const lhs_type = NodeProperties::GetType(lhs); |
332 | Type const rhs_type = NodeProperties::GetType(rhs); |
333 | if (!lhs_type.Maybe(rhs_type)) { |
334 | Node* replacement = jsgraph()->FalseConstant(); |
335 | // Make sure we do not widen the type. |
336 | if (NodeProperties::GetType(replacement) |
337 | .Is(NodeProperties::GetType(node))) { |
338 | return Replace(jsgraph()->FalseConstant()); |
339 | } |
340 | } |
341 | return NoChange(); |
342 | } |
343 | |
344 | const Operator* TypedOptimization::NumberComparisonFor(const Operator* op) { |
345 | switch (op->opcode()) { |
346 | case IrOpcode::kStringEqual: |
347 | return simplified()->NumberEqual(); |
348 | case IrOpcode::kStringLessThan: |
349 | return simplified()->NumberLessThan(); |
350 | case IrOpcode::kStringLessThanOrEqual: |
351 | return simplified()->NumberLessThanOrEqual(); |
352 | default: |
353 | break; |
354 | } |
355 | UNREACHABLE(); |
356 | } |
357 | |
358 | Reduction TypedOptimization:: |
359 | TryReduceStringComparisonOfStringFromSingleCharCodeToConstant( |
360 | Node* comparison, const StringRef& string, bool inverted) { |
361 | switch (comparison->opcode()) { |
362 | case IrOpcode::kStringEqual: |
363 | if (string.length() != 1) { |
364 | // String.fromCharCode(x) always has length 1. |
365 | return Replace(jsgraph()->BooleanConstant(false)); |
366 | } |
367 | break; |
368 | case IrOpcode::kStringLessThan: |
369 | V8_FALLTHROUGH; |
370 | case IrOpcode::kStringLessThanOrEqual: |
371 | if (string.length() == 0) { |
372 | // String.fromCharCode(x) <= "" is always false, |
373 | // "" < String.fromCharCode(x) is always true. |
374 | return Replace(jsgraph()->BooleanConstant(inverted)); |
375 | } |
376 | break; |
377 | default: |
378 | UNREACHABLE(); |
379 | } |
380 | return NoChange(); |
381 | } |
382 | |
383 | // Try to reduces a string comparison of the form |
384 | // String.fromCharCode(x) {comparison} {constant} if inverted is false, |
385 | // and {constant} {comparison} String.fromCharCode(x) if inverted is true. |
386 | Reduction |
387 | TypedOptimization::TryReduceStringComparisonOfStringFromSingleCharCode( |
388 | Node* comparison, Node* from_char_code, Type constant_type, bool inverted) { |
389 | DCHECK_EQ(IrOpcode::kStringFromSingleCharCode, from_char_code->opcode()); |
390 | |
391 | if (!constant_type.IsHeapConstant()) return NoChange(); |
392 | ObjectRef constant = constant_type.AsHeapConstant()->Ref(); |
393 | |
394 | if (!constant.IsString()) return NoChange(); |
395 | StringRef string = constant.AsString(); |
396 | |
397 | // Check if comparison can be resolved statically. |
398 | Reduction red = TryReduceStringComparisonOfStringFromSingleCharCodeToConstant( |
399 | comparison, string, inverted); |
400 | if (red.Changed()) return red; |
401 | |
402 | const Operator* comparison_op = NumberComparisonFor(comparison->op()); |
403 | Node* from_char_code_repl = NodeProperties::GetValueInput(from_char_code, 0); |
404 | Type from_char_code_repl_type = NodeProperties::GetType(from_char_code_repl); |
405 | if (!from_char_code_repl_type.Is(type_cache_->kUint16)) { |
406 | // Convert to signed int32 to satisfy type of {NumberBitwiseAnd}. |
407 | from_char_code_repl = |
408 | graph()->NewNode(simplified()->NumberToInt32(), from_char_code_repl); |
409 | from_char_code_repl = graph()->NewNode( |
410 | simplified()->NumberBitwiseAnd(), from_char_code_repl, |
411 | jsgraph()->Constant(std::numeric_limits<uint16_t>::max())); |
412 | } |
413 | Node* constant_repl = jsgraph()->Constant(string.GetFirstChar()); |
414 | |
415 | Node* number_comparison = nullptr; |
416 | if (inverted) { |
417 | // "x..." <= String.fromCharCode(z) is true if x < z. |
418 | if (string.length() > 1 && |
419 | comparison->opcode() == IrOpcode::kStringLessThanOrEqual) { |
420 | comparison_op = simplified()->NumberLessThan(); |
421 | } |
422 | number_comparison = |
423 | graph()->NewNode(comparison_op, constant_repl, from_char_code_repl); |
424 | } else { |
425 | // String.fromCharCode(z) < "x..." is true if z <= x. |
426 | if (string.length() > 1 && |
427 | comparison->opcode() == IrOpcode::kStringLessThan) { |
428 | comparison_op = simplified()->NumberLessThanOrEqual(); |
429 | } |
430 | number_comparison = |
431 | graph()->NewNode(comparison_op, from_char_code_repl, constant_repl); |
432 | } |
433 | ReplaceWithValue(comparison, number_comparison); |
434 | return Replace(number_comparison); |
435 | } |
436 | |
437 | Reduction TypedOptimization::ReduceStringComparison(Node* node) { |
438 | DCHECK(IrOpcode::kStringEqual == node->opcode() || |
439 | IrOpcode::kStringLessThan == node->opcode() || |
440 | IrOpcode::kStringLessThanOrEqual == node->opcode()); |
441 | Node* const lhs = NodeProperties::GetValueInput(node, 0); |
442 | Node* const rhs = NodeProperties::GetValueInput(node, 1); |
443 | Type lhs_type = NodeProperties::GetType(lhs); |
444 | Type rhs_type = NodeProperties::GetType(rhs); |
445 | if (lhs->opcode() == IrOpcode::kStringFromSingleCharCode) { |
446 | if (rhs->opcode() == IrOpcode::kStringFromSingleCharCode) { |
447 | Node* left = NodeProperties::GetValueInput(lhs, 0); |
448 | Node* right = NodeProperties::GetValueInput(rhs, 0); |
449 | Type left_type = NodeProperties::GetType(left); |
450 | Type right_type = NodeProperties::GetType(right); |
451 | if (!left_type.Is(type_cache_->kUint16)) { |
452 | // Convert to signed int32 to satisfy type of {NumberBitwiseAnd}. |
453 | left = graph()->NewNode(simplified()->NumberToInt32(), left); |
454 | left = graph()->NewNode( |
455 | simplified()->NumberBitwiseAnd(), left, |
456 | jsgraph()->Constant(std::numeric_limits<uint16_t>::max())); |
457 | } |
458 | if (!right_type.Is(type_cache_->kUint16)) { |
459 | // Convert to signed int32 to satisfy type of {NumberBitwiseAnd}. |
460 | right = graph()->NewNode(simplified()->NumberToInt32(), right); |
461 | right = graph()->NewNode( |
462 | simplified()->NumberBitwiseAnd(), right, |
463 | jsgraph()->Constant(std::numeric_limits<uint16_t>::max())); |
464 | } |
465 | Node* equal = |
466 | graph()->NewNode(NumberComparisonFor(node->op()), left, right); |
467 | ReplaceWithValue(node, equal); |
468 | return Replace(equal); |
469 | } else { |
470 | return TryReduceStringComparisonOfStringFromSingleCharCode( |
471 | node, lhs, rhs_type, false); |
472 | } |
473 | } else if (rhs->opcode() == IrOpcode::kStringFromSingleCharCode) { |
474 | return TryReduceStringComparisonOfStringFromSingleCharCode(node, rhs, |
475 | lhs_type, true); |
476 | } |
477 | return NoChange(); |
478 | } |
479 | |
480 | Reduction TypedOptimization::ReduceStringLength(Node* node) { |
481 | DCHECK_EQ(IrOpcode::kStringLength, node->opcode()); |
482 | Node* const input = NodeProperties::GetValueInput(node, 0); |
483 | switch (input->opcode()) { |
484 | case IrOpcode::kHeapConstant: { |
485 | // Constant-fold the String::length of the {input}. |
486 | HeapObjectMatcher m(input); |
487 | if (m.Ref(broker()).IsString()) { |
488 | uint32_t const length = m.Ref(broker()).AsString().length(); |
489 | Node* value = jsgraph()->Constant(length); |
490 | return Replace(value); |
491 | } |
492 | break; |
493 | } |
494 | case IrOpcode::kStringConcat: { |
495 | // The first value input to the {input} is the resulting length. |
496 | return Replace(input->InputAt(0)); |
497 | } |
498 | default: |
499 | break; |
500 | } |
501 | return NoChange(); |
502 | } |
503 | |
504 | Reduction TypedOptimization::ReduceSameValue(Node* node) { |
505 | DCHECK_EQ(IrOpcode::kSameValue, node->opcode()); |
506 | Node* const lhs = NodeProperties::GetValueInput(node, 0); |
507 | Node* const rhs = NodeProperties::GetValueInput(node, 1); |
508 | Type const lhs_type = NodeProperties::GetType(lhs); |
509 | Type const rhs_type = NodeProperties::GetType(rhs); |
510 | if (lhs == rhs) { |
511 | // SameValue(x,x) => #true |
512 | return Replace(jsgraph()->TrueConstant()); |
513 | } else if (lhs_type.Is(Type::Unique()) && rhs_type.Is(Type::Unique())) { |
514 | // SameValue(x:unique,y:unique) => ReferenceEqual(x,y) |
515 | NodeProperties::ChangeOp(node, simplified()->ReferenceEqual()); |
516 | return Changed(node); |
517 | } else if (lhs_type.Is(Type::String()) && rhs_type.Is(Type::String())) { |
518 | // SameValue(x:string,y:string) => StringEqual(x,y) |
519 | NodeProperties::ChangeOp(node, simplified()->StringEqual()); |
520 | return Changed(node); |
521 | } else if (lhs_type.Is(Type::MinusZero())) { |
522 | // SameValue(x:minus-zero,y) => ObjectIsMinusZero(y) |
523 | node->RemoveInput(0); |
524 | NodeProperties::ChangeOp(node, simplified()->ObjectIsMinusZero()); |
525 | return Changed(node); |
526 | } else if (rhs_type.Is(Type::MinusZero())) { |
527 | // SameValue(x,y:minus-zero) => ObjectIsMinusZero(x) |
528 | node->RemoveInput(1); |
529 | NodeProperties::ChangeOp(node, simplified()->ObjectIsMinusZero()); |
530 | return Changed(node); |
531 | } else if (lhs_type.Is(Type::NaN())) { |
532 | // SameValue(x:nan,y) => ObjectIsNaN(y) |
533 | node->RemoveInput(0); |
534 | NodeProperties::ChangeOp(node, simplified()->ObjectIsNaN()); |
535 | return Changed(node); |
536 | } else if (rhs_type.Is(Type::NaN())) { |
537 | // SameValue(x,y:nan) => ObjectIsNaN(x) |
538 | node->RemoveInput(1); |
539 | NodeProperties::ChangeOp(node, simplified()->ObjectIsNaN()); |
540 | return Changed(node); |
541 | } else if (lhs_type.Is(Type::PlainNumber()) && |
542 | rhs_type.Is(Type::PlainNumber())) { |
543 | // SameValue(x:plain-number,y:plain-number) => NumberEqual(x,y) |
544 | NodeProperties::ChangeOp(node, simplified()->NumberEqual()); |
545 | return Changed(node); |
546 | } |
547 | return NoChange(); |
548 | } |
549 | |
550 | Reduction TypedOptimization::ReduceSelect(Node* node) { |
551 | DCHECK_EQ(IrOpcode::kSelect, node->opcode()); |
552 | Node* const condition = NodeProperties::GetValueInput(node, 0); |
553 | Type const condition_type = NodeProperties::GetType(condition); |
554 | Node* const vtrue = NodeProperties::GetValueInput(node, 1); |
555 | Type const vtrue_type = NodeProperties::GetType(vtrue); |
556 | Node* const vfalse = NodeProperties::GetValueInput(node, 2); |
557 | Type const vfalse_type = NodeProperties::GetType(vfalse); |
558 | if (condition_type.Is(true_type_)) { |
559 | // Select(condition:true, vtrue, vfalse) => vtrue |
560 | return Replace(vtrue); |
561 | } |
562 | if (condition_type.Is(false_type_)) { |
563 | // Select(condition:false, vtrue, vfalse) => vfalse |
564 | return Replace(vfalse); |
565 | } |
566 | if (vtrue_type.Is(true_type_) && vfalse_type.Is(false_type_)) { |
567 | // Select(condition, vtrue:true, vfalse:false) => condition |
568 | return Replace(condition); |
569 | } |
570 | if (vtrue_type.Is(false_type_) && vfalse_type.Is(true_type_)) { |
571 | // Select(condition, vtrue:false, vfalse:true) => BooleanNot(condition) |
572 | node->TrimInputCount(1); |
573 | NodeProperties::ChangeOp(node, simplified()->BooleanNot()); |
574 | return Changed(node); |
575 | } |
576 | // Try to narrow the type of the Select {node}, which might be more precise |
577 | // now after lowering based on types. |
578 | Type type = Type::Union(vtrue_type, vfalse_type, graph()->zone()); |
579 | Type const node_type = NodeProperties::GetType(node); |
580 | if (!node_type.Is(type)) { |
581 | type = Type::Intersect(node_type, type, graph()->zone()); |
582 | NodeProperties::SetType(node, type); |
583 | return Changed(node); |
584 | } |
585 | return NoChange(); |
586 | } |
587 | |
588 | Reduction TypedOptimization::ReduceSpeculativeToNumber(Node* node) { |
589 | DCHECK_EQ(IrOpcode::kSpeculativeToNumber, node->opcode()); |
590 | Node* const input = NodeProperties::GetValueInput(node, 0); |
591 | Type const input_type = NodeProperties::GetType(input); |
592 | if (input_type.Is(Type::Number())) { |
593 | // SpeculativeToNumber(x:number) => x |
594 | ReplaceWithValue(node, input); |
595 | return Replace(input); |
596 | } |
597 | return NoChange(); |
598 | } |
599 | |
600 | Reduction TypedOptimization::ReduceTypeOf(Node* node) { |
601 | Node* const input = node->InputAt(0); |
602 | Type const type = NodeProperties::GetType(input); |
603 | Factory* const f = factory(); |
604 | if (type.Is(Type::Boolean())) { |
605 | return Replace( |
606 | jsgraph()->Constant(ObjectRef(broker(), f->boolean_string()))); |
607 | } else if (type.Is(Type::Number())) { |
608 | return Replace( |
609 | jsgraph()->Constant(ObjectRef(broker(), f->number_string()))); |
610 | } else if (type.Is(Type::String())) { |
611 | return Replace( |
612 | jsgraph()->Constant(ObjectRef(broker(), f->string_string()))); |
613 | } else if (type.Is(Type::BigInt())) { |
614 | return Replace( |
615 | jsgraph()->Constant(ObjectRef(broker(), f->bigint_string()))); |
616 | } else if (type.Is(Type::Symbol())) { |
617 | return Replace( |
618 | jsgraph()->Constant(ObjectRef(broker(), f->symbol_string()))); |
619 | } else if (type.Is(Type::OtherUndetectableOrUndefined())) { |
620 | return Replace( |
621 | jsgraph()->Constant(ObjectRef(broker(), f->undefined_string()))); |
622 | } else if (type.Is(Type::NonCallableOrNull())) { |
623 | return Replace( |
624 | jsgraph()->Constant(ObjectRef(broker(), f->object_string()))); |
625 | } else if (type.Is(Type::Function())) { |
626 | return Replace( |
627 | jsgraph()->Constant(ObjectRef(broker(), f->function_string()))); |
628 | } |
629 | return NoChange(); |
630 | } |
631 | |
632 | Reduction TypedOptimization::ReduceToBoolean(Node* node) { |
633 | Node* const input = node->InputAt(0); |
634 | Type const input_type = NodeProperties::GetType(input); |
635 | if (input_type.Is(Type::Boolean())) { |
636 | // ToBoolean(x:boolean) => x |
637 | return Replace(input); |
638 | } else if (input_type.Is(Type::OrderedNumber())) { |
639 | // SToBoolean(x:ordered-number) => BooleanNot(NumberEqual(x,#0)) |
640 | node->ReplaceInput(0, graph()->NewNode(simplified()->NumberEqual(), input, |
641 | jsgraph()->ZeroConstant())); |
642 | node->TrimInputCount(1); |
643 | NodeProperties::ChangeOp(node, simplified()->BooleanNot()); |
644 | return Changed(node); |
645 | } else if (input_type.Is(Type::Number())) { |
646 | // ToBoolean(x:number) => NumberToBoolean(x) |
647 | node->TrimInputCount(1); |
648 | NodeProperties::ChangeOp(node, simplified()->NumberToBoolean()); |
649 | return Changed(node); |
650 | } else if (input_type.Is(Type::DetectableReceiverOrNull())) { |
651 | // ToBoolean(x:detectable receiver \/ null) |
652 | // => BooleanNot(ReferenceEqual(x,#null)) |
653 | node->ReplaceInput(0, graph()->NewNode(simplified()->ReferenceEqual(), |
654 | input, jsgraph()->NullConstant())); |
655 | node->TrimInputCount(1); |
656 | NodeProperties::ChangeOp(node, simplified()->BooleanNot()); |
657 | return Changed(node); |
658 | } else if (input_type.Is(Type::ReceiverOrNullOrUndefined())) { |
659 | // ToBoolean(x:receiver \/ null \/ undefined) |
660 | // => BooleanNot(ObjectIsUndetectable(x)) |
661 | node->ReplaceInput( |
662 | 0, graph()->NewNode(simplified()->ObjectIsUndetectable(), input)); |
663 | node->TrimInputCount(1); |
664 | NodeProperties::ChangeOp(node, simplified()->BooleanNot()); |
665 | return Changed(node); |
666 | } else if (input_type.Is(Type::String())) { |
667 | // ToBoolean(x:string) => BooleanNot(ReferenceEqual(x,"")) |
668 | node->ReplaceInput(0, |
669 | graph()->NewNode(simplified()->ReferenceEqual(), input, |
670 | jsgraph()->EmptyStringConstant())); |
671 | node->TrimInputCount(1); |
672 | NodeProperties::ChangeOp(node, simplified()->BooleanNot()); |
673 | return Changed(node); |
674 | } |
675 | return NoChange(); |
676 | } |
677 | |
678 | namespace { |
679 | bool BothAre(Type t1, Type t2, Type t3) { return t1.Is(t3) && t2.Is(t3); } |
680 | |
681 | bool NeitherCanBe(Type t1, Type t2, Type t3) { |
682 | return !t1.Maybe(t3) && !t2.Maybe(t3); |
683 | } |
684 | |
685 | const Operator* NumberOpFromSpeculativeNumberOp( |
686 | SimplifiedOperatorBuilder* simplified, const Operator* op) { |
687 | switch (op->opcode()) { |
688 | case IrOpcode::kSpeculativeNumberEqual: |
689 | return simplified->NumberEqual(); |
690 | case IrOpcode::kSpeculativeNumberLessThan: |
691 | return simplified->NumberLessThan(); |
692 | case IrOpcode::kSpeculativeNumberLessThanOrEqual: |
693 | return simplified->NumberLessThanOrEqual(); |
694 | case IrOpcode::kSpeculativeNumberAdd: |
695 | // Handled by ReduceSpeculativeNumberAdd. |
696 | UNREACHABLE(); |
697 | case IrOpcode::kSpeculativeNumberSubtract: |
698 | return simplified->NumberSubtract(); |
699 | case IrOpcode::kSpeculativeNumberMultiply: |
700 | return simplified->NumberMultiply(); |
701 | case IrOpcode::kSpeculativeNumberDivide: |
702 | return simplified->NumberDivide(); |
703 | case IrOpcode::kSpeculativeNumberModulus: |
704 | return simplified->NumberModulus(); |
705 | default: |
706 | break; |
707 | } |
708 | UNREACHABLE(); |
709 | } |
710 | |
711 | } // namespace |
712 | |
713 | Reduction TypedOptimization::ReduceSpeculativeNumberAdd(Node* node) { |
714 | Node* const lhs = NodeProperties::GetValueInput(node, 0); |
715 | Node* const rhs = NodeProperties::GetValueInput(node, 1); |
716 | Type const lhs_type = NodeProperties::GetType(lhs); |
717 | Type const rhs_type = NodeProperties::GetType(rhs); |
718 | NumberOperationHint hint = NumberOperationHintOf(node->op()); |
719 | if ((hint == NumberOperationHint::kNumber || |
720 | hint == NumberOperationHint::kNumberOrOddball) && |
721 | BothAre(lhs_type, rhs_type, Type::PlainPrimitive()) && |
722 | NeitherCanBe(lhs_type, rhs_type, Type::StringOrReceiver())) { |
723 | // SpeculativeNumberAdd(x:-string, y:-string) => |
724 | // NumberAdd(ToNumber(x), ToNumber(y)) |
725 | Node* const toNum_lhs = ConvertPlainPrimitiveToNumber(lhs); |
726 | Node* const toNum_rhs = ConvertPlainPrimitiveToNumber(rhs); |
727 | Node* const value = |
728 | graph()->NewNode(simplified()->NumberAdd(), toNum_lhs, toNum_rhs); |
729 | ReplaceWithValue(node, value); |
730 | return Replace(value); |
731 | } |
732 | return NoChange(); |
733 | } |
734 | |
735 | Reduction TypedOptimization::ReduceJSToNumberInput(Node* input) { |
736 | // Try constant-folding of JSToNumber with constant inputs. |
737 | Type input_type = NodeProperties::GetType(input); |
738 | |
739 | if (input_type.Is(Type::String())) { |
740 | HeapObjectMatcher m(input); |
741 | if (m.HasValue() && m.Ref(broker()).IsString()) { |
742 | StringRef input_value = m.Ref(broker()).AsString(); |
743 | double number; |
744 | ASSIGN_RETURN_NO_CHANGE_IF_DATA_MISSING(number, input_value.ToNumber()); |
745 | return Replace(jsgraph()->Constant(number)); |
746 | } |
747 | } |
748 | if (input_type.IsHeapConstant()) { |
749 | HeapObjectRef input_value = input_type.AsHeapConstant()->Ref(); |
750 | double value; |
751 | if (input_value.OddballToNumber().To(&value)) { |
752 | return Replace(jsgraph()->Constant(value)); |
753 | } |
754 | } |
755 | if (input_type.Is(Type::Number())) { |
756 | // JSToNumber(x:number) => x |
757 | return Changed(input); |
758 | } |
759 | if (input_type.Is(Type::Undefined())) { |
760 | // JSToNumber(undefined) => #NaN |
761 | return Replace(jsgraph()->NaNConstant()); |
762 | } |
763 | if (input_type.Is(Type::Null())) { |
764 | // JSToNumber(null) => #0 |
765 | return Replace(jsgraph()->ZeroConstant()); |
766 | } |
767 | return NoChange(); |
768 | } |
769 | |
770 | Node* TypedOptimization::ConvertPlainPrimitiveToNumber(Node* node) { |
771 | DCHECK(NodeProperties::GetType(node).Is(Type::PlainPrimitive())); |
772 | // Avoid inserting too many eager ToNumber() operations. |
773 | Reduction const reduction = ReduceJSToNumberInput(node); |
774 | if (reduction.Changed()) return reduction.replacement(); |
775 | if (NodeProperties::GetType(node).Is(Type::Number())) { |
776 | return node; |
777 | } |
778 | return graph()->NewNode(simplified()->PlainPrimitiveToNumber(), node); |
779 | } |
780 | |
781 | Reduction TypedOptimization::ReduceSpeculativeNumberBinop(Node* node) { |
782 | Node* const lhs = NodeProperties::GetValueInput(node, 0); |
783 | Node* const rhs = NodeProperties::GetValueInput(node, 1); |
784 | Type const lhs_type = NodeProperties::GetType(lhs); |
785 | Type const rhs_type = NodeProperties::GetType(rhs); |
786 | NumberOperationHint hint = NumberOperationHintOf(node->op()); |
787 | if ((hint == NumberOperationHint::kNumber || |
788 | hint == NumberOperationHint::kNumberOrOddball) && |
789 | BothAre(lhs_type, rhs_type, Type::NumberOrUndefinedOrNullOrBoolean())) { |
790 | // We intentionally do this only in the Number and NumberOrOddball hint case |
791 | // because simplified lowering of these speculative ops may do some clever |
792 | // reductions in the other cases. |
793 | Node* const toNum_lhs = ConvertPlainPrimitiveToNumber(lhs); |
794 | Node* const toNum_rhs = ConvertPlainPrimitiveToNumber(rhs); |
795 | Node* const value = graph()->NewNode( |
796 | NumberOpFromSpeculativeNumberOp(simplified(), node->op()), toNum_lhs, |
797 | toNum_rhs); |
798 | ReplaceWithValue(node, value); |
799 | return Replace(value); |
800 | } |
801 | return NoChange(); |
802 | } |
803 | |
804 | Reduction TypedOptimization::ReduceSpeculativeNumberComparison(Node* node) { |
805 | Node* const lhs = NodeProperties::GetValueInput(node, 0); |
806 | Node* const rhs = NodeProperties::GetValueInput(node, 1); |
807 | Type const lhs_type = NodeProperties::GetType(lhs); |
808 | Type const rhs_type = NodeProperties::GetType(rhs); |
809 | if (BothAre(lhs_type, rhs_type, Type::Signed32()) || |
810 | BothAre(lhs_type, rhs_type, Type::Unsigned32())) { |
811 | Node* const value = graph()->NewNode( |
812 | NumberOpFromSpeculativeNumberOp(simplified(), node->op()), lhs, rhs); |
813 | ReplaceWithValue(node, value); |
814 | return Replace(value); |
815 | } |
816 | return NoChange(); |
817 | } |
818 | |
819 | Factory* TypedOptimization::factory() const { |
820 | return jsgraph()->isolate()->factory(); |
821 | } |
822 | |
823 | Graph* TypedOptimization::graph() const { return jsgraph()->graph(); } |
824 | |
825 | SimplifiedOperatorBuilder* TypedOptimization::simplified() const { |
826 | return jsgraph()->simplified(); |
827 | } |
828 | |
829 | } // namespace compiler |
830 | } // namespace internal |
831 | } // namespace v8 |
832 | |