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