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