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