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