1// Copyright 2014 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/typer.h"
6
7#include <iomanip>
8
9#include "src/base/flags.h"
10#include "src/bootstrapper.h"
11#include "src/compiler/common-operator.h"
12#include "src/compiler/graph-reducer.h"
13#include "src/compiler/js-operator.h"
14#include "src/compiler/linkage.h"
15#include "src/compiler/loop-variable-optimizer.h"
16#include "src/compiler/node-properties.h"
17#include "src/compiler/node.h"
18#include "src/compiler/operation-typer.h"
19#include "src/compiler/simplified-operator.h"
20#include "src/compiler/type-cache.h"
21#include "src/objects-inl.h"
22
23namespace v8 {
24namespace internal {
25namespace compiler {
26
27class Typer::Decorator final : public GraphDecorator {
28 public:
29  explicit Decorator(Typer* typer) : typer_(typer) {}
30  void Decorate(Node* node) final;
31
32 private:
33  Typer* const typer_;
34};
35
36Typer::Typer(Isolate* isolate, Flags flags, Graph* graph)
37    : isolate_(isolate),
38      flags_(flags),
39      graph_(graph),
40      decorator_(nullptr),
41      cache_(TypeCache::Get()),
42      operation_typer_(isolate, zone()) {
43  Zone* zone = this->zone();
44  Factory* const factory = isolate->factory();
45
46  singleton_false_ = Type::HeapConstant(factory->false_value(), zone);
47  singleton_true_ = Type::HeapConstant(factory->true_value(), zone);
48  singleton_the_hole_ = Type::HeapConstant(factory->the_hole_value(), zone);
49  falsish_ = Type::Union(
50      Type::Undetectable(),
51      Type::Union(Type::Union(singleton_false_, cache_.kZeroish, zone),
52                  singleton_the_hole_, zone),
53      zone);
54  truish_ = Type::Union(
55      singleton_true_,
56      Type::Union(Type::DetectableReceiver(), Type::Symbol(), zone), zone);
57
58  decorator_ = new (zone) Decorator(this);
59  graph_->AddDecorator(decorator_);
60}
61
62
63Typer::~Typer() {
64  graph_->RemoveDecorator(decorator_);
65}
66
67
68class Typer::Visitor : public Reducer {
69 public:
70  explicit Visitor(Typer* typer, LoopVariableOptimizer* induction_vars)
71      : typer_(typer),
72        induction_vars_(induction_vars),
73        weakened_nodes_(typer->zone()) {}
74
75  Reduction Reduce(Node* node) override {
76    if (node->op()->ValueOutputCount() == 0) return NoChange();
77    switch (node->opcode()) {
78#define DECLARE_CASE(x) \
79  case IrOpcode::k##x:  \
80    return UpdateType(node, TypeBinaryOp(node, x##Typer));
81      JS_SIMPLE_BINOP_LIST(DECLARE_CASE)
82#undef DECLARE_CASE
83
84#define DECLARE_CASE(x) \
85  case IrOpcode::k##x:  \
86    return UpdateType(node, Type##x(node));
87      DECLARE_CASE(Start)
88      DECLARE_CASE(IfException)
89      // VALUE_OP_LIST without JS_SIMPLE_BINOP_LIST:
90      COMMON_OP_LIST(DECLARE_CASE)
91      SIMPLIFIED_COMPARE_BINOP_LIST(DECLARE_CASE)
92      SIMPLIFIED_OTHER_OP_LIST(DECLARE_CASE)
93      JS_SIMPLE_UNOP_LIST(DECLARE_CASE)
94      JS_OBJECT_OP_LIST(DECLARE_CASE)
95      JS_CONTEXT_OP_LIST(DECLARE_CASE)
96      JS_OTHER_OP_LIST(DECLARE_CASE)
97#undef DECLARE_CASE
98
99#define DECLARE_CASE(x) \
100  case IrOpcode::k##x:  \
101    return UpdateType(node, TypeBinaryOp(node, x));
102      SIMPLIFIED_NUMBER_BINOP_LIST(DECLARE_CASE)
103      SIMPLIFIED_SPECULATIVE_NUMBER_BINOP_LIST(DECLARE_CASE)
104#undef DECLARE_CASE
105
106#define DECLARE_CASE(x) \
107  case IrOpcode::k##x:  \
108    return UpdateType(node, TypeUnaryOp(node, x));
109      SIMPLIFIED_NUMBER_UNOP_LIST(DECLARE_CASE)
110#undef DECLARE_CASE
111
112#define DECLARE_CASE(x) case IrOpcode::k##x:
113      DECLARE_CASE(Loop)
114      DECLARE_CASE(Branch)
115      DECLARE_CASE(IfTrue)
116      DECLARE_CASE(IfFalse)
117      DECLARE_CASE(IfSuccess)
118      DECLARE_CASE(Switch)
119      DECLARE_CASE(IfValue)
120      DECLARE_CASE(IfDefault)
121      DECLARE_CASE(Merge)
122      DECLARE_CASE(Deoptimize)
123      DECLARE_CASE(DeoptimizeIf)
124      DECLARE_CASE(DeoptimizeUnless)
125      DECLARE_CASE(Return)
126      DECLARE_CASE(TailCall)
127      DECLARE_CASE(Terminate)
128      DECLARE_CASE(OsrNormalEntry)
129      DECLARE_CASE(OsrLoopEntry)
130      DECLARE_CASE(Throw)
131      DECLARE_CASE(End)
132      SIMPLIFIED_CHANGE_OP_LIST(DECLARE_CASE)
133      SIMPLIFIED_CHECKED_OP_LIST(DECLARE_CASE)
134      MACHINE_SIMD_OP_LIST(DECLARE_CASE)
135      MACHINE_OP_LIST(DECLARE_CASE)
136#undef DECLARE_CASE
137      break;
138    }
139    return NoChange();
140  }
141
142  Type* TypeNode(Node* node) {
143    switch (node->opcode()) {
144#define DECLARE_CASE(x) \
145      case IrOpcode::k##x: return TypeBinaryOp(node, x##Typer);
146      JS_SIMPLE_BINOP_LIST(DECLARE_CASE)
147#undef DECLARE_CASE
148
149#define DECLARE_CASE(x) case IrOpcode::k##x: return Type##x(node);
150      DECLARE_CASE(Start)
151      DECLARE_CASE(IfException)
152      // VALUE_OP_LIST without JS_SIMPLE_BINOP_LIST:
153      COMMON_OP_LIST(DECLARE_CASE)
154      SIMPLIFIED_COMPARE_BINOP_LIST(DECLARE_CASE)
155      SIMPLIFIED_OTHER_OP_LIST(DECLARE_CASE)
156      JS_SIMPLE_UNOP_LIST(DECLARE_CASE)
157      JS_OBJECT_OP_LIST(DECLARE_CASE)
158      JS_CONTEXT_OP_LIST(DECLARE_CASE)
159      JS_OTHER_OP_LIST(DECLARE_CASE)
160#undef DECLARE_CASE
161
162#define DECLARE_CASE(x) \
163  case IrOpcode::k##x:  \
164    return TypeBinaryOp(node, x);
165      SIMPLIFIED_NUMBER_BINOP_LIST(DECLARE_CASE)
166      SIMPLIFIED_SPECULATIVE_NUMBER_BINOP_LIST(DECLARE_CASE)
167#undef DECLARE_CASE
168
169#define DECLARE_CASE(x) \
170  case IrOpcode::k##x:  \
171    return TypeUnaryOp(node, x);
172      SIMPLIFIED_NUMBER_UNOP_LIST(DECLARE_CASE)
173#undef DECLARE_CASE
174
175#define DECLARE_CASE(x) case IrOpcode::k##x:
176      DECLARE_CASE(Loop)
177      DECLARE_CASE(Branch)
178      DECLARE_CASE(IfTrue)
179      DECLARE_CASE(IfFalse)
180      DECLARE_CASE(IfSuccess)
181      DECLARE_CASE(Switch)
182      DECLARE_CASE(IfValue)
183      DECLARE_CASE(IfDefault)
184      DECLARE_CASE(Merge)
185      DECLARE_CASE(Deoptimize)
186      DECLARE_CASE(DeoptimizeIf)
187      DECLARE_CASE(DeoptimizeUnless)
188      DECLARE_CASE(Return)
189      DECLARE_CASE(TailCall)
190      DECLARE_CASE(Terminate)
191      DECLARE_CASE(OsrNormalEntry)
192      DECLARE_CASE(OsrLoopEntry)
193      DECLARE_CASE(Throw)
194      DECLARE_CASE(End)
195      SIMPLIFIED_CHANGE_OP_LIST(DECLARE_CASE)
196      SIMPLIFIED_CHECKED_OP_LIST(DECLARE_CASE)
197      MACHINE_SIMD_OP_LIST(DECLARE_CASE)
198      MACHINE_OP_LIST(DECLARE_CASE)
199#undef DECLARE_CASE
200      break;
201    }
202    UNREACHABLE();
203    return nullptr;
204  }
205
206  Type* TypeConstant(Handle<Object> value);
207
208 private:
209  Typer* typer_;
210  LoopVariableOptimizer* induction_vars_;
211  ZoneSet<NodeId> weakened_nodes_;
212
213#define DECLARE_METHOD(x) inline Type* Type##x(Node* node);
214  DECLARE_METHOD(Start)
215  DECLARE_METHOD(IfException)
216  COMMON_OP_LIST(DECLARE_METHOD)
217  SIMPLIFIED_COMPARE_BINOP_LIST(DECLARE_METHOD)
218  SIMPLIFIED_OTHER_OP_LIST(DECLARE_METHOD)
219  JS_OP_LIST(DECLARE_METHOD)
220#undef DECLARE_METHOD
221
222  Type* TypeOrNone(Node* node) {
223    return NodeProperties::IsTyped(node) ? NodeProperties::GetType(node)
224                                         : Type::None();
225  }
226
227  Type* Operand(Node* node, int i) {
228    Node* operand_node = NodeProperties::GetValueInput(node, i);
229    return TypeOrNone(operand_node);
230  }
231
232  Type* Weaken(Node* node, Type* current_type, Type* previous_type);
233
234  Zone* zone() { return typer_->zone(); }
235  Isolate* isolate() { return typer_->isolate(); }
236  Graph* graph() { return typer_->graph(); }
237
238  void SetWeakened(NodeId node_id) { weakened_nodes_.insert(node_id); }
239  bool IsWeakened(NodeId node_id) {
240    return weakened_nodes_.find(node_id) != weakened_nodes_.end();
241  }
242
243  typedef Type* (*UnaryTyperFun)(Type*, Typer* t);
244  typedef Type* (*BinaryTyperFun)(Type*, Type*, Typer* t);
245
246  Type* TypeUnaryOp(Node* node, UnaryTyperFun);
247  Type* TypeBinaryOp(Node* node, BinaryTyperFun);
248
249  enum ComparisonOutcomeFlags {
250    kComparisonTrue = 1,
251    kComparisonFalse = 2,
252    kComparisonUndefined = 4
253  };
254  typedef base::Flags<ComparisonOutcomeFlags> ComparisonOutcome;
255
256  static ComparisonOutcome Invert(ComparisonOutcome, Typer*);
257  static Type* Invert(Type*, Typer*);
258  static Type* FalsifyUndefined(ComparisonOutcome, Typer*);
259
260  static Type* ToPrimitive(Type*, Typer*);
261  static Type* ToBoolean(Type*, Typer*);
262  static Type* ToInteger(Type*, Typer*);
263  static Type* ToLength(Type*, Typer*);
264  static Type* ToName(Type*, Typer*);
265  static Type* ToNumber(Type*, Typer*);
266  static Type* ToObject(Type*, Typer*);
267  static Type* ToString(Type*, Typer*);
268#define DECLARE_METHOD(Name)                \
269  static Type* Name(Type* type, Typer* t) { \
270    return t->operation_typer_.Name(type);  \
271  }
272  SIMPLIFIED_NUMBER_UNOP_LIST(DECLARE_METHOD)
273#undef DECLARE_METHOD
274#define DECLARE_METHOD(Name)                          \
275  static Type* Name(Type* lhs, Type* rhs, Typer* t) { \
276    return t->operation_typer_.Name(lhs, rhs);        \
277  }
278  SIMPLIFIED_NUMBER_BINOP_LIST(DECLARE_METHOD)
279  SIMPLIFIED_SPECULATIVE_NUMBER_BINOP_LIST(DECLARE_METHOD)
280#undef DECLARE_METHOD
281
282  static Type* ObjectIsCallable(Type*, Typer*);
283  static Type* ObjectIsNumber(Type*, Typer*);
284  static Type* ObjectIsReceiver(Type*, Typer*);
285  static Type* ObjectIsSmi(Type*, Typer*);
286  static Type* ObjectIsString(Type*, Typer*);
287  static Type* ObjectIsUndetectable(Type*, Typer*);
288
289  static ComparisonOutcome JSCompareTyper(Type*, Type*, Typer*);
290
291#define DECLARE_METHOD(x) static Type* x##Typer(Type*, Type*, Typer*);
292  JS_SIMPLE_BINOP_LIST(DECLARE_METHOD)
293#undef DECLARE_METHOD
294
295  static Type* JSCallFunctionTyper(Type*, Typer*);
296
297  static Type* ReferenceEqualTyper(Type*, Type*, Typer*);
298  static Type* StringFromCharCodeTyper(Type*, Typer*);
299  static Type* StringFromCodePointTyper(Type*, Typer*);
300
301  Reduction UpdateType(Node* node, Type* current) {
302    if (NodeProperties::IsTyped(node)) {
303      // Widen the type of a previously typed node.
304      Type* previous = NodeProperties::GetType(node);
305      if (node->opcode() == IrOpcode::kPhi ||
306          node->opcode() == IrOpcode::kInductionVariablePhi) {
307        // Speed up termination in the presence of range types:
308        current = Weaken(node, current, previous);
309      }
310
311      CHECK(previous->Is(current));
312
313      NodeProperties::SetType(node, current);
314      if (!current->Is(previous)) {
315        // If something changed, revisit all uses.
316        return Changed(node);
317      }
318      return NoChange();
319    } else {
320      // No previous type, simply update the type.
321      NodeProperties::SetType(node, current);
322      return Changed(node);
323    }
324  }
325};
326
327void Typer::Run() { Run(NodeVector(zone()), nullptr); }
328
329void Typer::Run(const NodeVector& roots,
330                LoopVariableOptimizer* induction_vars) {
331  if (induction_vars != nullptr) {
332    induction_vars->ChangeToInductionVariablePhis();
333  }
334  Visitor visitor(this, induction_vars);
335  GraphReducer graph_reducer(zone(), graph());
336  graph_reducer.AddReducer(&visitor);
337  for (Node* const root : roots) graph_reducer.ReduceNode(root);
338  graph_reducer.ReduceGraph();
339
340  if (induction_vars != nullptr) {
341    induction_vars->ChangeToPhisAndInsertGuards();
342  }
343}
344
345void Typer::Decorator::Decorate(Node* node) {
346  if (node->op()->ValueOutputCount() > 0) {
347    // Only eagerly type-decorate nodes with known input types.
348    // Other cases will generally require a proper fixpoint iteration with Run.
349    bool is_typed = NodeProperties::IsTyped(node);
350    if (is_typed || NodeProperties::AllValueInputsAreTyped(node)) {
351      Visitor typing(typer_, nullptr);
352      Type* type = typing.TypeNode(node);
353      if (is_typed) {
354        type = Type::Intersect(type, NodeProperties::GetType(node),
355                               typer_->zone());
356      }
357      NodeProperties::SetType(node, type);
358    }
359  }
360}
361
362
363// -----------------------------------------------------------------------------
364
365// Helper functions that lift a function f on types to a function on bounds,
366// and uses that to type the given node.  Note that f is never called with None
367// as an argument.
368
369
370Type* Typer::Visitor::TypeUnaryOp(Node* node, UnaryTyperFun f) {
371  Type* input = Operand(node, 0);
372  return input->IsInhabited() ? f(input, typer_) : Type::None();
373}
374
375
376Type* Typer::Visitor::TypeBinaryOp(Node* node, BinaryTyperFun f) {
377  Type* left = Operand(node, 0);
378  Type* right = Operand(node, 1);
379  return left->IsInhabited() && right->IsInhabited() ? f(left, right, typer_)
380                                                     : Type::None();
381}
382
383
384Type* Typer::Visitor::Invert(Type* type, Typer* t) {
385  DCHECK(type->Is(Type::Boolean()));
386  DCHECK(type->IsInhabited());
387  if (type->Is(t->singleton_false_)) return t->singleton_true_;
388  if (type->Is(t->singleton_true_)) return t->singleton_false_;
389  return type;
390}
391
392
393Typer::Visitor::ComparisonOutcome Typer::Visitor::Invert(
394    ComparisonOutcome outcome, Typer* t) {
395  ComparisonOutcome result(0);
396  if ((outcome & kComparisonUndefined) != 0) result |= kComparisonUndefined;
397  if ((outcome & kComparisonTrue) != 0) result |= kComparisonFalse;
398  if ((outcome & kComparisonFalse) != 0) result |= kComparisonTrue;
399  return result;
400}
401
402
403Type* Typer::Visitor::FalsifyUndefined(ComparisonOutcome outcome, Typer* t) {
404  if ((outcome & kComparisonFalse) != 0 ||
405      (outcome & kComparisonUndefined) != 0) {
406    return (outcome & kComparisonTrue) != 0 ? Type::Boolean()
407                                            : t->singleton_false_;
408  }
409  // Type should be non empty, so we know it should be true.
410  DCHECK((outcome & kComparisonTrue) != 0);
411  return t->singleton_true_;
412}
413
414// Type conversion.
415
416Type* Typer::Visitor::ToPrimitive(Type* type, Typer* t) {
417  if (type->Is(Type::Primitive()) && !type->Maybe(Type::Receiver())) {
418    return type;
419  }
420  return Type::Primitive();
421}
422
423
424Type* Typer::Visitor::ToBoolean(Type* type, Typer* t) {
425  if (type->Is(Type::Boolean())) return type;
426  if (type->Is(t->falsish_)) return t->singleton_false_;
427  if (type->Is(t->truish_)) return t->singleton_true_;
428  if (type->Is(Type::Number())) {
429    return t->operation_typer()->NumberToBoolean(type);
430  }
431  return Type::Boolean();
432}
433
434
435// static
436Type* Typer::Visitor::ToInteger(Type* type, Typer* t) {
437  // ES6 section 7.1.4 ToInteger ( argument )
438  type = ToNumber(type, t);
439  if (type->Is(t->cache_.kIntegerOrMinusZero)) return type;
440  if (type->Is(t->cache_.kIntegerOrMinusZeroOrNaN)) {
441    return Type::Union(
442        Type::Intersect(type, t->cache_.kIntegerOrMinusZero, t->zone()),
443        t->cache_.kSingletonZero, t->zone());
444  }
445  return t->cache_.kIntegerOrMinusZero;
446}
447
448
449// static
450Type* Typer::Visitor::ToLength(Type* type, Typer* t) {
451  // ES6 section 7.1.15 ToLength ( argument )
452  type = ToInteger(type, t);
453  double min = type->Min();
454  double max = type->Max();
455  if (min <= 0.0) min = 0.0;
456  if (max > kMaxSafeInteger) max = kMaxSafeInteger;
457  if (max <= min) max = min;
458  return Type::Range(min, max, t->zone());
459}
460
461
462// static
463Type* Typer::Visitor::ToName(Type* type, Typer* t) {
464  // ES6 section 7.1.14 ToPropertyKey ( argument )
465  type = ToPrimitive(type, t);
466  if (type->Is(Type::Name())) return type;
467  if (type->Maybe(Type::Symbol())) return Type::Name();
468  return ToString(type, t);
469}
470
471
472// static
473Type* Typer::Visitor::ToNumber(Type* type, Typer* t) {
474  return t->operation_typer_.ToNumber(type);
475}
476
477
478// static
479Type* Typer::Visitor::ToObject(Type* type, Typer* t) {
480  // ES6 section 7.1.13 ToObject ( argument )
481  if (type->Is(Type::Receiver())) return type;
482  if (type->Is(Type::Primitive())) return Type::OtherObject();
483  if (!type->Maybe(Type::OtherUndetectable())) {
484    return Type::DetectableReceiver();
485  }
486  return Type::Receiver();
487}
488
489
490// static
491Type* Typer::Visitor::ToString(Type* type, Typer* t) {
492  // ES6 section 7.1.12 ToString ( argument )
493  type = ToPrimitive(type, t);
494  if (type->Is(Type::String())) return type;
495  return Type::String();
496}
497
498// Type checks.
499
500Type* Typer::Visitor::ObjectIsCallable(Type* type, Typer* t) {
501  if (type->Is(Type::Function())) return t->singleton_true_;
502  if (type->Is(Type::Primitive())) return t->singleton_false_;
503  return Type::Boolean();
504}
505
506Type* Typer::Visitor::ObjectIsNumber(Type* type, Typer* t) {
507  if (type->Is(Type::Number())) return t->singleton_true_;
508  if (!type->Maybe(Type::Number())) return t->singleton_false_;
509  return Type::Boolean();
510}
511
512
513Type* Typer::Visitor::ObjectIsReceiver(Type* type, Typer* t) {
514  if (type->Is(Type::Receiver())) return t->singleton_true_;
515  if (!type->Maybe(Type::Receiver())) return t->singleton_false_;
516  return Type::Boolean();
517}
518
519
520Type* Typer::Visitor::ObjectIsSmi(Type* type, Typer* t) {
521  if (!type->Maybe(Type::SignedSmall())) return t->singleton_false_;
522  return Type::Boolean();
523}
524
525Type* Typer::Visitor::ObjectIsString(Type* type, Typer* t) {
526  if (type->Is(Type::String())) return t->singleton_true_;
527  if (!type->Maybe(Type::String())) return t->singleton_false_;
528  return Type::Boolean();
529}
530
531Type* Typer::Visitor::ObjectIsUndetectable(Type* type, Typer* t) {
532  if (type->Is(Type::Undetectable())) return t->singleton_true_;
533  if (!type->Maybe(Type::Undetectable())) return t->singleton_false_;
534  return Type::Boolean();
535}
536
537
538// -----------------------------------------------------------------------------
539
540
541// Control operators.
542
543Type* Typer::Visitor::TypeStart(Node* node) { return Type::Internal(); }
544
545Type* Typer::Visitor::TypeIfException(Node* node) {
546  return Type::NonInternal();
547}
548
549// Common operators.
550
551Type* Typer::Visitor::TypeParameter(Node* node) {
552  Node* const start = node->InputAt(0);
553  DCHECK_EQ(IrOpcode::kStart, start->opcode());
554  int const parameter_count = start->op()->ValueOutputCount() - 4;
555  DCHECK_LE(1, parameter_count);
556  int const index = ParameterIndexOf(node->op());
557  if (index == Linkage::kJSCallClosureParamIndex) {
558    return Type::Function();
559  } else if (index == 0) {
560    if (typer_->flags() & Typer::kThisIsReceiver) {
561      return Type::Receiver();
562    } else {
563      // Parameter[this] can be the_hole for derived class constructors.
564      return Type::Union(Type::Hole(), Type::NonInternal(), typer_->zone());
565    }
566  } else if (index == Linkage::GetJSCallNewTargetParamIndex(parameter_count)) {
567    if (typer_->flags() & Typer::kNewTargetIsReceiver) {
568      return Type::Receiver();
569    } else {
570      return Type::Union(Type::Receiver(), Type::Undefined(), typer_->zone());
571    }
572  } else if (index == Linkage::GetJSCallArgCountParamIndex(parameter_count)) {
573    return Type::Range(0.0, Code::kMaxArguments, typer_->zone());
574  } else if (index == Linkage::GetJSCallContextParamIndex(parameter_count)) {
575    return Type::OtherInternal();
576  }
577  return Type::NonInternal();
578}
579
580Type* Typer::Visitor::TypeOsrValue(Node* node) { return Type::Any(); }
581
582Type* Typer::Visitor::TypeOsrGuard(Node* node) {
583  switch (OsrGuardTypeOf(node->op())) {
584    case OsrGuardType::kUninitialized:
585      return Type::None();
586    case OsrGuardType::kSignedSmall:
587      return Type::SignedSmall();
588    case OsrGuardType::kAny:
589      return Type::Any();
590  }
591  UNREACHABLE();
592  return nullptr;
593}
594
595Type* Typer::Visitor::TypeRetain(Node* node) {
596  UNREACHABLE();
597  return nullptr;
598}
599
600Type* Typer::Visitor::TypeInt32Constant(Node* node) {
601  UNREACHABLE();
602  return nullptr;
603}
604
605Type* Typer::Visitor::TypeInt64Constant(Node* node) {
606  UNREACHABLE();
607  return nullptr;
608}
609
610Type* Typer::Visitor::TypeRelocatableInt32Constant(Node* node) {
611  UNREACHABLE();
612  return nullptr;
613}
614
615Type* Typer::Visitor::TypeRelocatableInt64Constant(Node* node) {
616  UNREACHABLE();
617  return nullptr;
618}
619
620Type* Typer::Visitor::TypeFloat32Constant(Node* node) {
621  UNREACHABLE();
622  return nullptr;
623}
624
625Type* Typer::Visitor::TypeFloat64Constant(Node* node) {
626  UNREACHABLE();
627  return nullptr;
628}
629
630Type* Typer::Visitor::TypeNumberConstant(Node* node) {
631  double number = OpParameter<double>(node);
632  return Type::NewConstant(number, zone());
633}
634
635Type* Typer::Visitor::TypeHeapConstant(Node* node) {
636  return TypeConstant(OpParameter<Handle<HeapObject>>(node));
637}
638
639Type* Typer::Visitor::TypeExternalConstant(Node* node) {
640  return Type::ExternalPointer();
641}
642
643Type* Typer::Visitor::TypePointerConstant(Node* node) {
644  return Type::ExternalPointer();
645}
646
647Type* Typer::Visitor::TypeSelect(Node* node) {
648  return Type::Union(Operand(node, 1), Operand(node, 2), zone());
649}
650
651Type* Typer::Visitor::TypePhi(Node* node) {
652  int arity = node->op()->ValueInputCount();
653  Type* type = Operand(node, 0);
654  for (int i = 1; i < arity; ++i) {
655    type = Type::Union(type, Operand(node, i), zone());
656  }
657  return type;
658}
659
660Type* Typer::Visitor::TypeInductionVariablePhi(Node* node) {
661  int arity = NodeProperties::GetControlInput(node)->op()->ControlInputCount();
662  DCHECK_EQ(IrOpcode::kLoop, NodeProperties::GetControlInput(node)->opcode());
663  DCHECK_EQ(2, NodeProperties::GetControlInput(node)->InputCount());
664
665  Type* initial_type = Operand(node, 0);
666  Type* increment_type = Operand(node, 2);
667
668  // We only handle integer induction variables (otherwise ranges
669  // do not apply and we cannot do anything).
670  if (!initial_type->Is(typer_->cache_.kInteger) ||
671      !increment_type->Is(typer_->cache_.kInteger)) {
672    // Fallback to normal phi typing, but ensure monotonicity.
673    // (Unfortunately, without baking in the previous type, monotonicity might
674    // be violated because we might not yet have retyped the incrementing
675    // operation even though the increment's type might been already reflected
676    // in the induction variable phi.)
677    Type* type = NodeProperties::IsTyped(node) ? NodeProperties::GetType(node)
678                                               : Type::None();
679    for (int i = 0; i < arity; ++i) {
680      type = Type::Union(type, Operand(node, i), zone());
681    }
682    return type;
683  }
684  // If we do not have enough type information for the initial value or
685  // the increment, just return the initial value's type.
686  if (!initial_type->IsInhabited() ||
687      increment_type->Is(typer_->cache_.kSingletonZero)) {
688    return initial_type;
689  }
690
691  // Now process the bounds.
692  auto res = induction_vars_->induction_variables().find(node->id());
693  DCHECK(res != induction_vars_->induction_variables().end());
694  InductionVariable* induction_var = res->second;
695
696  InductionVariable::ArithmeticType arithmetic_type = induction_var->Type();
697
698  double min = -V8_INFINITY;
699  double max = V8_INFINITY;
700
701  double increment_min;
702  double increment_max;
703  if (arithmetic_type == InductionVariable::ArithmeticType::kAddition) {
704    increment_min = increment_type->Min();
705    increment_max = increment_type->Max();
706  } else {
707    DCHECK(arithmetic_type == InductionVariable::ArithmeticType::kSubtraction);
708    increment_min = -increment_type->Max();
709    increment_max = -increment_type->Min();
710  }
711
712  if (increment_min >= 0) {
713    // increasing sequence
714    min = initial_type->Min();
715    for (auto bound : induction_var->upper_bounds()) {
716      Type* bound_type = TypeOrNone(bound.bound);
717      // If the type is not an integer, just skip the bound.
718      if (!bound_type->Is(typer_->cache_.kInteger)) continue;
719      // If the type is not inhabited, then we can take the initial value.
720      if (!bound_type->IsInhabited()) {
721        max = initial_type->Max();
722        break;
723      }
724      double bound_max = bound_type->Max();
725      if (bound.kind == InductionVariable::kStrict) {
726        bound_max -= 1;
727      }
728      max = std::min(max, bound_max + increment_max);
729    }
730    // The upper bound must be at least the initial value's upper bound.
731    max = std::max(max, initial_type->Max());
732  } else if (increment_max <= 0) {
733    // decreasing sequence
734    max = initial_type->Max();
735    for (auto bound : induction_var->lower_bounds()) {
736      Type* bound_type = TypeOrNone(bound.bound);
737      // If the type is not an integer, just skip the bound.
738      if (!bound_type->Is(typer_->cache_.kInteger)) continue;
739      // If the type is not inhabited, then we can take the initial value.
740      if (!bound_type->IsInhabited()) {
741        min = initial_type->Min();
742        break;
743      }
744      double bound_min = bound_type->Min();
745      if (bound.kind == InductionVariable::kStrict) {
746        bound_min += 1;
747      }
748      min = std::max(min, bound_min + increment_min);
749    }
750    // The lower bound must be at most the initial value's lower bound.
751    min = std::min(min, initial_type->Min());
752  } else {
753    // Shortcut: If the increment can be both positive and negative,
754    // the variable can go arbitrarily far, so just return integer.
755    return typer_->cache_.kInteger;
756  }
757  if (FLAG_trace_turbo_loop) {
758    OFStream os(stdout);
759    os << std::setprecision(10);
760    os << "Loop (" << NodeProperties::GetControlInput(node)->id()
761       << ") variable bounds in "
762       << (arithmetic_type == InductionVariable::ArithmeticType::kAddition
763               ? "addition"
764               : "subtraction")
765       << " for phi " << node->id() << ": (" << min << ", " << max << ")\n";
766  }
767  return Type::Range(min, max, typer_->zone());
768}
769
770Type* Typer::Visitor::TypeEffectPhi(Node* node) {
771  UNREACHABLE();
772  return nullptr;
773}
774
775Type* Typer::Visitor::TypeLoopExit(Node* node) {
776  UNREACHABLE();
777  return nullptr;
778}
779
780Type* Typer::Visitor::TypeLoopExitValue(Node* node) { return Operand(node, 0); }
781
782Type* Typer::Visitor::TypeLoopExitEffect(Node* node) {
783  UNREACHABLE();
784  return nullptr;
785}
786
787Type* Typer::Visitor::TypeEnsureWritableFastElements(Node* node) {
788  return Operand(node, 1);
789}
790
791Type* Typer::Visitor::TypeMaybeGrowFastElements(Node* node) {
792  return Operand(node, 1);
793}
794
795Type* Typer::Visitor::TypeTransitionElementsKind(Node* node) {
796  UNREACHABLE();
797  return nullptr;
798}
799
800Type* Typer::Visitor::TypeCheckpoint(Node* node) {
801  UNREACHABLE();
802  return nullptr;
803}
804
805Type* Typer::Visitor::TypeBeginRegion(Node* node) {
806  UNREACHABLE();
807  return nullptr;
808}
809
810
811Type* Typer::Visitor::TypeFinishRegion(Node* node) { return Operand(node, 0); }
812
813
814Type* Typer::Visitor::TypeFrameState(Node* node) {
815  // TODO(rossberg): Ideally FrameState wouldn't have a value output.
816  return Type::Internal();
817}
818
819Type* Typer::Visitor::TypeStateValues(Node* node) { return Type::Internal(); }
820
821Type* Typer::Visitor::TypeTypedStateValues(Node* node) {
822  return Type::Internal();
823}
824
825Type* Typer::Visitor::TypeObjectState(Node* node) { return Type::Internal(); }
826
827Type* Typer::Visitor::TypeTypedObjectState(Node* node) {
828  return Type::Internal();
829}
830
831Type* Typer::Visitor::TypeCall(Node* node) { return Type::Any(); }
832
833
834Type* Typer::Visitor::TypeProjection(Node* node) {
835  Type* const type = Operand(node, 0);
836  if (type->Is(Type::None())) return Type::None();
837  int const index = static_cast<int>(ProjectionIndexOf(node->op()));
838  if (type->IsTuple() && index < type->AsTuple()->Arity()) {
839    return type->AsTuple()->Element(index);
840  }
841  return Type::Any();
842}
843
844Type* Typer::Visitor::TypeTypeGuard(Node* node) {
845  Type* const type = Operand(node, 0);
846  return typer_->operation_typer()->TypeTypeGuard(node->op(), type);
847}
848
849Type* Typer::Visitor::TypeDead(Node* node) { return Type::None(); }
850
851// JS comparison operators.
852
853
854Type* Typer::Visitor::JSEqualTyper(Type* lhs, Type* rhs, Typer* t) {
855  if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return t->singleton_false_;
856  if (lhs->Is(Type::NullOrUndefined()) && rhs->Is(Type::NullOrUndefined())) {
857    return t->singleton_true_;
858  }
859  if (lhs->Is(Type::Number()) && rhs->Is(Type::Number()) &&
860      (lhs->Max() < rhs->Min() || lhs->Min() > rhs->Max())) {
861    return t->singleton_false_;
862  }
863  if (lhs->IsHeapConstant() && rhs->Is(lhs)) {
864    // Types are equal and are inhabited only by a single semantic value,
865    // which is not nan due to the earlier check.
866    return t->singleton_true_;
867  }
868  return Type::Boolean();
869}
870
871
872Type* Typer::Visitor::JSNotEqualTyper(Type* lhs, Type* rhs, Typer* t) {
873  return Invert(JSEqualTyper(lhs, rhs, t), t);
874}
875
876
877static Type* JSType(Type* type) {
878  if (type->Is(Type::Boolean())) return Type::Boolean();
879  if (type->Is(Type::String())) return Type::String();
880  if (type->Is(Type::Number())) return Type::Number();
881  if (type->Is(Type::Undefined())) return Type::Undefined();
882  if (type->Is(Type::Null())) return Type::Null();
883  if (type->Is(Type::Symbol())) return Type::Symbol();
884  if (type->Is(Type::Receiver())) return Type::Receiver();  // JS "Object"
885  return Type::Any();
886}
887
888
889Type* Typer::Visitor::JSStrictEqualTyper(Type* lhs, Type* rhs, Typer* t) {
890  if (!JSType(lhs)->Maybe(JSType(rhs))) return t->singleton_false_;
891  if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return t->singleton_false_;
892  if (lhs->Is(Type::Number()) && rhs->Is(Type::Number()) &&
893      (lhs->Max() < rhs->Min() || lhs->Min() > rhs->Max())) {
894    return t->singleton_false_;
895  }
896  if ((lhs->Is(t->singleton_the_hole_) || rhs->Is(t->singleton_the_hole_)) &&
897      !lhs->Maybe(rhs)) {
898    return t->singleton_false_;
899  }
900  if (lhs->IsHeapConstant() && rhs->Is(lhs)) {
901    // Types are equal and are inhabited only by a single semantic value,
902    // which is not nan due to the earlier check.
903    return t->singleton_true_;
904  }
905  return Type::Boolean();
906}
907
908
909Type* Typer::Visitor::JSStrictNotEqualTyper(Type* lhs, Type* rhs, Typer* t) {
910  return Invert(JSStrictEqualTyper(lhs, rhs, t), t);
911}
912
913
914// The EcmaScript specification defines the four relational comparison operators
915// (<, <=, >=, >) with the help of a single abstract one.  It behaves like <
916// but returns undefined when the inputs cannot be compared.
917// We implement the typing analogously.
918Typer::Visitor::ComparisonOutcome Typer::Visitor::JSCompareTyper(Type* lhs,
919                                                                 Type* rhs,
920                                                                 Typer* t) {
921  lhs = ToPrimitive(lhs, t);
922  rhs = ToPrimitive(rhs, t);
923  if (lhs->Maybe(Type::String()) && rhs->Maybe(Type::String())) {
924    return ComparisonOutcome(kComparisonTrue) |
925           ComparisonOutcome(kComparisonFalse);
926  }
927  lhs = ToNumber(lhs, t);
928  rhs = ToNumber(rhs, t);
929
930  // Shortcut for NaNs.
931  if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return kComparisonUndefined;
932
933  ComparisonOutcome result;
934  if (lhs->IsHeapConstant() && rhs->Is(lhs)) {
935    // Types are equal and are inhabited only by a single semantic value.
936    result = kComparisonFalse;
937  } else if (lhs->Min() >= rhs->Max()) {
938    result = kComparisonFalse;
939  } else if (lhs->Max() < rhs->Min()) {
940    result = kComparisonTrue;
941  } else {
942    // We cannot figure out the result, return both true and false. (We do not
943    // have to return undefined because that cannot affect the result of
944    // FalsifyUndefined.)
945    return ComparisonOutcome(kComparisonTrue) |
946           ComparisonOutcome(kComparisonFalse);
947  }
948  // Add the undefined if we could see NaN.
949  if (lhs->Maybe(Type::NaN()) || rhs->Maybe(Type::NaN())) {
950    result |= kComparisonUndefined;
951  }
952  return result;
953}
954
955
956Type* Typer::Visitor::JSLessThanTyper(Type* lhs, Type* rhs, Typer* t) {
957  return FalsifyUndefined(JSCompareTyper(lhs, rhs, t), t);
958}
959
960
961Type* Typer::Visitor::JSGreaterThanTyper(Type* lhs, Type* rhs, Typer* t) {
962  return FalsifyUndefined(JSCompareTyper(rhs, lhs, t), t);
963}
964
965
966Type* Typer::Visitor::JSLessThanOrEqualTyper(Type* lhs, Type* rhs, Typer* t) {
967  return FalsifyUndefined(Invert(JSCompareTyper(rhs, lhs, t), t), t);
968}
969
970
971Type* Typer::Visitor::JSGreaterThanOrEqualTyper(
972    Type* lhs, Type* rhs, Typer* t) {
973  return FalsifyUndefined(Invert(JSCompareTyper(lhs, rhs, t), t), t);
974}
975
976// JS bitwise operators.
977
978
979Type* Typer::Visitor::JSBitwiseOrTyper(Type* lhs, Type* rhs, Typer* t) {
980  return NumberBitwiseOr(ToNumber(lhs, t), ToNumber(rhs, t), t);
981}
982
983
984Type* Typer::Visitor::JSBitwiseAndTyper(Type* lhs, Type* rhs, Typer* t) {
985  return NumberBitwiseAnd(ToNumber(lhs, t), ToNumber(rhs, t), t);
986}
987
988
989Type* Typer::Visitor::JSBitwiseXorTyper(Type* lhs, Type* rhs, Typer* t) {
990  return NumberBitwiseXor(ToNumber(lhs, t), ToNumber(rhs, t), t);
991}
992
993
994Type* Typer::Visitor::JSShiftLeftTyper(Type* lhs, Type* rhs, Typer* t) {
995  return NumberShiftLeft(ToNumber(lhs, t), ToNumber(rhs, t), t);
996}
997
998
999Type* Typer::Visitor::JSShiftRightTyper(Type* lhs, Type* rhs, Typer* t) {
1000  return NumberShiftRight(ToNumber(lhs, t), ToNumber(rhs, t), t);
1001}
1002
1003
1004Type* Typer::Visitor::JSShiftRightLogicalTyper(Type* lhs, Type* rhs, Typer* t) {
1005  return NumberShiftRightLogical(ToNumber(lhs, t), ToNumber(rhs, t), t);
1006}
1007
1008
1009// JS arithmetic operators.
1010
1011Type* Typer::Visitor::JSAddTyper(Type* lhs, Type* rhs, Typer* t) {
1012  lhs = ToPrimitive(lhs, t);
1013  rhs = ToPrimitive(rhs, t);
1014  if (lhs->Maybe(Type::String()) || rhs->Maybe(Type::String())) {
1015    if (lhs->Is(Type::String()) || rhs->Is(Type::String())) {
1016      return Type::String();
1017    } else {
1018      return Type::NumberOrString();
1019    }
1020  }
1021  // The addition must be numeric.
1022  return NumberAdd(ToNumber(lhs, t), ToNumber(rhs, t), t);
1023}
1024
1025Type* Typer::Visitor::JSSubtractTyper(Type* lhs, Type* rhs, Typer* t) {
1026  return NumberSubtract(ToNumber(lhs, t), ToNumber(rhs, t), t);
1027}
1028
1029Type* Typer::Visitor::JSMultiplyTyper(Type* lhs, Type* rhs, Typer* t) {
1030  return NumberMultiply(ToNumber(lhs, t), ToNumber(rhs, t), t);
1031}
1032
1033Type* Typer::Visitor::JSDivideTyper(Type* lhs, Type* rhs, Typer* t) {
1034  return NumberDivide(ToNumber(lhs, t), ToNumber(rhs, t), t);
1035}
1036
1037Type* Typer::Visitor::JSModulusTyper(Type* lhs, Type* rhs, Typer* t) {
1038  return NumberModulus(ToNumber(lhs, t), ToNumber(rhs, t), t);
1039}
1040
1041
1042// JS unary operators.
1043
1044
1045Type* Typer::Visitor::TypeJSTypeOf(Node* node) {
1046  return Type::InternalizedString();
1047}
1048
1049
1050// JS conversion operators.
1051
1052
1053Type* Typer::Visitor::TypeJSToBoolean(Node* node) {
1054  return TypeUnaryOp(node, ToBoolean);
1055}
1056
1057Type* Typer::Visitor::TypeJSToInteger(Node* node) {
1058  return TypeUnaryOp(node, ToInteger);
1059}
1060
1061Type* Typer::Visitor::TypeJSToLength(Node* node) {
1062  return TypeUnaryOp(node, ToLength);
1063}
1064
1065Type* Typer::Visitor::TypeJSToName(Node* node) {
1066  return TypeUnaryOp(node, ToName);
1067}
1068
1069Type* Typer::Visitor::TypeJSToNumber(Node* node) {
1070  return TypeUnaryOp(node, ToNumber);
1071}
1072
1073Type* Typer::Visitor::TypeJSToObject(Node* node) {
1074  return TypeUnaryOp(node, ToObject);
1075}
1076
1077Type* Typer::Visitor::TypeJSToString(Node* node) {
1078  return TypeUnaryOp(node, ToString);
1079}
1080
1081// JS object operators.
1082
1083
1084Type* Typer::Visitor::TypeJSCreate(Node* node) { return Type::Object(); }
1085
1086
1087Type* Typer::Visitor::TypeJSCreateArguments(Node* node) {
1088  return Type::OtherObject();
1089}
1090
1091
1092Type* Typer::Visitor::TypeJSCreateArray(Node* node) {
1093  return Type::OtherObject();
1094}
1095
1096
1097Type* Typer::Visitor::TypeJSCreateClosure(Node* node) {
1098  return Type::Function();
1099}
1100
1101
1102Type* Typer::Visitor::TypeJSCreateIterResultObject(Node* node) {
1103  return Type::OtherObject();
1104}
1105
1106Type* Typer::Visitor::TypeJSCreateKeyValueArray(Node* node) {
1107  return Type::OtherObject();
1108}
1109
1110Type* Typer::Visitor::TypeJSCreateLiteralArray(Node* node) {
1111  return Type::OtherObject();
1112}
1113
1114
1115Type* Typer::Visitor::TypeJSCreateLiteralObject(Node* node) {
1116  return Type::OtherObject();
1117}
1118
1119
1120Type* Typer::Visitor::TypeJSCreateLiteralRegExp(Node* node) {
1121  return Type::OtherObject();
1122}
1123
1124
1125Type* Typer::Visitor::TypeJSLoadProperty(Node* node) {
1126  return Type::NonInternal();
1127}
1128
1129
1130Type* Typer::Visitor::TypeJSLoadNamed(Node* node) {
1131  return Type::NonInternal();
1132}
1133
1134Type* Typer::Visitor::TypeJSLoadGlobal(Node* node) {
1135  return Type::NonInternal();
1136}
1137
1138// Returns a somewhat larger range if we previously assigned
1139// a (smaller) range to this node. This is used  to speed up
1140// the fixpoint calculation in case there appears to be a loop
1141// in the graph. In the current implementation, we are
1142// increasing the limits to the closest power of two.
1143Type* Typer::Visitor::Weaken(Node* node, Type* current_type,
1144                             Type* previous_type) {
1145  static const double kWeakenMinLimits[] = {
1146      0.0, -1073741824.0, -2147483648.0, -4294967296.0, -8589934592.0,
1147      -17179869184.0, -34359738368.0, -68719476736.0, -137438953472.0,
1148      -274877906944.0, -549755813888.0, -1099511627776.0, -2199023255552.0,
1149      -4398046511104.0, -8796093022208.0, -17592186044416.0, -35184372088832.0,
1150      -70368744177664.0, -140737488355328.0, -281474976710656.0,
1151      -562949953421312.0};
1152  static const double kWeakenMaxLimits[] = {
1153      0.0, 1073741823.0, 2147483647.0, 4294967295.0, 8589934591.0,
1154      17179869183.0, 34359738367.0, 68719476735.0, 137438953471.0,
1155      274877906943.0, 549755813887.0, 1099511627775.0, 2199023255551.0,
1156      4398046511103.0, 8796093022207.0, 17592186044415.0, 35184372088831.0,
1157      70368744177663.0, 140737488355327.0, 281474976710655.0,
1158      562949953421311.0};
1159  STATIC_ASSERT(arraysize(kWeakenMinLimits) == arraysize(kWeakenMaxLimits));
1160
1161  // If the types have nothing to do with integers, return the types.
1162  Type* const integer = typer_->cache_.kInteger;
1163  if (!previous_type->Maybe(integer)) {
1164    return current_type;
1165  }
1166  DCHECK(current_type->Maybe(integer));
1167
1168  Type* current_integer = Type::Intersect(current_type, integer, zone());
1169  Type* previous_integer = Type::Intersect(previous_type, integer, zone());
1170
1171  // Once we start weakening a node, we should always weaken.
1172  if (!IsWeakened(node->id())) {
1173    // Only weaken if there is range involved; we should converge quickly
1174    // for all other types (the exception is a union of many constants,
1175    // but we currently do not increase the number of constants in unions).
1176    Type* previous = previous_integer->GetRange();
1177    Type* current = current_integer->GetRange();
1178    if (current == nullptr || previous == nullptr) {
1179      return current_type;
1180    }
1181    // Range is involved => we are weakening.
1182    SetWeakened(node->id());
1183  }
1184
1185  double current_min = current_integer->Min();
1186  double new_min = current_min;
1187  // Find the closest lower entry in the list of allowed
1188  // minima (or negative infinity if there is no such entry).
1189  if (current_min != previous_integer->Min()) {
1190    new_min = -V8_INFINITY;
1191    for (double const min : kWeakenMinLimits) {
1192      if (min <= current_min) {
1193        new_min = min;
1194        break;
1195      }
1196    }
1197  }
1198
1199  double current_max = current_integer->Max();
1200  double new_max = current_max;
1201  // Find the closest greater entry in the list of allowed
1202  // maxima (or infinity if there is no such entry).
1203  if (current_max != previous_integer->Max()) {
1204    new_max = V8_INFINITY;
1205    for (double const max : kWeakenMaxLimits) {
1206      if (max >= current_max) {
1207        new_max = max;
1208        break;
1209      }
1210    }
1211  }
1212
1213  return Type::Union(current_type,
1214                     Type::Range(new_min, new_max, typer_->zone()),
1215                     typer_->zone());
1216}
1217
1218
1219Type* Typer::Visitor::TypeJSStoreProperty(Node* node) {
1220  UNREACHABLE();
1221  return nullptr;
1222}
1223
1224
1225Type* Typer::Visitor::TypeJSStoreNamed(Node* node) {
1226  UNREACHABLE();
1227  return nullptr;
1228}
1229
1230
1231Type* Typer::Visitor::TypeJSStoreGlobal(Node* node) {
1232  UNREACHABLE();
1233  return nullptr;
1234}
1235
1236
1237Type* Typer::Visitor::TypeJSDeleteProperty(Node* node) {
1238  return Type::Boolean();
1239}
1240
1241Type* Typer::Visitor::TypeJSHasProperty(Node* node) { return Type::Boolean(); }
1242
1243Type* Typer::Visitor::TypeJSInstanceOf(Node* node) { return Type::Boolean(); }
1244
1245Type* Typer::Visitor::TypeJSOrdinaryHasInstance(Node* node) {
1246  return Type::Boolean();
1247}
1248
1249// JS context operators.
1250
1251
1252Type* Typer::Visitor::TypeJSLoadContext(Node* node) {
1253  ContextAccess const& access = ContextAccessOf(node->op());
1254  switch (access.index()) {
1255    case Context::PREVIOUS_INDEX:
1256    case Context::NATIVE_CONTEXT_INDEX:
1257      return Type::OtherInternal();
1258    case Context::CLOSURE_INDEX:
1259      return Type::Function();
1260    default:
1261      return Type::Any();
1262  }
1263}
1264
1265
1266Type* Typer::Visitor::TypeJSStoreContext(Node* node) {
1267  UNREACHABLE();
1268  return nullptr;
1269}
1270
1271
1272Type* Typer::Visitor::TypeJSCreateFunctionContext(Node* node) {
1273  return Type::OtherInternal();
1274}
1275
1276Type* Typer::Visitor::TypeJSCreateCatchContext(Node* node) {
1277  return Type::OtherInternal();
1278}
1279
1280Type* Typer::Visitor::TypeJSCreateWithContext(Node* node) {
1281  return Type::OtherInternal();
1282}
1283
1284Type* Typer::Visitor::TypeJSCreateBlockContext(Node* node) {
1285  return Type::OtherInternal();
1286}
1287
1288Type* Typer::Visitor::TypeJSCreateScriptContext(Node* node) {
1289  return Type::OtherInternal();
1290}
1291
1292// JS other operators.
1293
1294
1295Type* Typer::Visitor::TypeJSCallConstruct(Node* node) {
1296  return Type::Receiver();
1297}
1298
1299Type* Typer::Visitor::JSCallFunctionTyper(Type* fun, Typer* t) {
1300  if (fun->IsHeapConstant() && fun->AsHeapConstant()->Value()->IsJSFunction()) {
1301    Handle<JSFunction> function =
1302        Handle<JSFunction>::cast(fun->AsHeapConstant()->Value());
1303    if (function->shared()->HasBuiltinFunctionId()) {
1304      switch (function->shared()->builtin_function_id()) {
1305        case kMathRandom:
1306          return Type::PlainNumber();
1307        case kMathFloor:
1308        case kMathCeil:
1309        case kMathRound:
1310        case kMathTrunc:
1311          return t->cache_.kIntegerOrMinusZeroOrNaN;
1312        // Unary math functions.
1313        case kMathAbs:
1314        case kMathExp:
1315        case kMathExpm1:
1316          return Type::Union(Type::PlainNumber(), Type::NaN(), t->zone());
1317        case kMathAcos:
1318        case kMathAcosh:
1319        case kMathAsin:
1320        case kMathAsinh:
1321        case kMathAtan:
1322        case kMathAtanh:
1323        case kMathCbrt:
1324        case kMathCos:
1325        case kMathFround:
1326        case kMathLog:
1327        case kMathLog1p:
1328        case kMathLog10:
1329        case kMathLog2:
1330        case kMathSin:
1331        case kMathSqrt:
1332        case kMathTan:
1333          return Type::Number();
1334        case kMathSign:
1335          return t->cache_.kMinusOneToOneOrMinusZeroOrNaN;
1336        // Binary math functions.
1337        case kMathAtan2:
1338        case kMathPow:
1339        case kMathMax:
1340        case kMathMin:
1341          return Type::Number();
1342        case kMathImul:
1343          return Type::Signed32();
1344        case kMathClz32:
1345          return t->cache_.kZeroToThirtyTwo;
1346        // Date functions.
1347        case kDateGetDate:
1348          return t->cache_.kJSDateDayType;
1349        case kDateGetDay:
1350          return t->cache_.kJSDateWeekdayType;
1351        case kDateGetFullYear:
1352          return t->cache_.kJSDateYearType;
1353        case kDateGetHours:
1354          return t->cache_.kJSDateHourType;
1355        case kDateGetMilliseconds:
1356          return Type::Union(Type::Range(0.0, 999.0, t->zone()), Type::NaN(),
1357                             t->zone());
1358        case kDateGetMinutes:
1359          return t->cache_.kJSDateMinuteType;
1360        case kDateGetMonth:
1361          return t->cache_.kJSDateMonthType;
1362        case kDateGetSeconds:
1363          return t->cache_.kJSDateSecondType;
1364        case kDateGetTime:
1365          return t->cache_.kJSDateValueType;
1366        // Number functions.
1367        case kNumberIsFinite:
1368        case kNumberIsInteger:
1369        case kNumberIsNaN:
1370        case kNumberIsSafeInteger:
1371          return Type::Boolean();
1372        case kNumberParseFloat:
1373          return Type::Number();
1374        case kNumberParseInt:
1375          return t->cache_.kIntegerOrMinusZeroOrNaN;
1376        case kNumberToString:
1377          return Type::String();
1378        // String functions.
1379        case kStringCharCodeAt:
1380          return Type::Union(Type::Range(0, kMaxUInt16, t->zone()), Type::NaN(),
1381                             t->zone());
1382        case kStringCharAt:
1383        case kStringConcat:
1384        case kStringFromCharCode:
1385        case kStringSubstr:
1386        case kStringToLowerCase:
1387        case kStringToUpperCase:
1388          return Type::String();
1389
1390        case kStringIterator:
1391        case kStringIteratorNext:
1392          return Type::OtherObject();
1393
1394        case kArrayEntries:
1395        case kArrayKeys:
1396        case kArrayValues:
1397        case kTypedArrayEntries:
1398        case kTypedArrayKeys:
1399        case kTypedArrayValues:
1400        case kArrayIteratorNext:
1401          return Type::OtherObject();
1402
1403        // Array functions.
1404        case kArrayIndexOf:
1405        case kArrayLastIndexOf:
1406          return Type::Range(-1, kMaxSafeInteger, t->zone());
1407        case kArrayPush:
1408          return t->cache_.kPositiveSafeInteger;
1409
1410        // Object functions.
1411        case kObjectHasOwnProperty:
1412          return Type::Boolean();
1413
1414        // Function functions.
1415        case kFunctionHasInstance:
1416          return Type::Boolean();
1417
1418        // Global functions.
1419        case kGlobalDecodeURI:
1420        case kGlobalDecodeURIComponent:
1421        case kGlobalEncodeURI:
1422        case kGlobalEncodeURIComponent:
1423        case kGlobalEscape:
1424        case kGlobalUnescape:
1425          return Type::String();
1426        case kGlobalIsFinite:
1427        case kGlobalIsNaN:
1428          return Type::Boolean();
1429        default:
1430          break;
1431      }
1432    }
1433  }
1434  return Type::NonInternal();
1435}
1436
1437
1438Type* Typer::Visitor::TypeJSCallFunction(Node* node) {
1439  // TODO(bmeurer): We could infer better types if we wouldn't ignore the
1440  // argument types for the JSCallFunctionTyper above.
1441  return TypeUnaryOp(node, JSCallFunctionTyper);
1442}
1443
1444
1445Type* Typer::Visitor::TypeJSCallRuntime(Node* node) {
1446  switch (CallRuntimeParametersOf(node->op()).id()) {
1447    case Runtime::kInlineIsJSReceiver:
1448      return TypeUnaryOp(node, ObjectIsReceiver);
1449    case Runtime::kInlineIsSmi:
1450      return TypeUnaryOp(node, ObjectIsSmi);
1451    case Runtime::kInlineIsArray:
1452    case Runtime::kInlineIsDate:
1453    case Runtime::kInlineIsTypedArray:
1454    case Runtime::kInlineIsRegExp:
1455      return Type::Boolean();
1456    case Runtime::kInlineCreateIterResultObject:
1457      return Type::OtherObject();
1458    case Runtime::kInlineSubString:
1459    case Runtime::kInlineStringCharFromCode:
1460      return Type::String();
1461    case Runtime::kInlineToInteger:
1462      return TypeUnaryOp(node, ToInteger);
1463    case Runtime::kInlineToLength:
1464      return TypeUnaryOp(node, ToLength);
1465    case Runtime::kInlineToNumber:
1466      return TypeUnaryOp(node, ToNumber);
1467    case Runtime::kInlineToObject:
1468      return TypeUnaryOp(node, ToObject);
1469    case Runtime::kInlineToString:
1470      return TypeUnaryOp(node, ToString);
1471    case Runtime::kHasInPrototypeChain:
1472      return Type::Boolean();
1473    default:
1474      break;
1475  }
1476  // TODO(turbofan): This should be Type::NonInternal(), but unfortunately we
1477  // have a few weird runtime calls that return the hole or even FixedArrays;
1478  // change this once those weird runtime calls have been removed.
1479  return Type::Any();
1480}
1481
1482
1483Type* Typer::Visitor::TypeJSConvertReceiver(Node* node) {
1484  return Type::Receiver();
1485}
1486
1487
1488Type* Typer::Visitor::TypeJSForInNext(Node* node) {
1489  return Type::Union(Type::Name(), Type::Undefined(), zone());
1490}
1491
1492
1493Type* Typer::Visitor::TypeJSForInPrepare(Node* node) {
1494  STATIC_ASSERT(Map::EnumLengthBits::kMax <= FixedArray::kMaxLength);
1495  Type* const cache_type =
1496      Type::Union(Type::SignedSmall(), Type::OtherInternal(), zone());
1497  Type* const cache_array = Type::OtherInternal();
1498  Type* const cache_length = typer_->cache_.kFixedArrayLengthType;
1499  return Type::Tuple(cache_type, cache_array, cache_length, zone());
1500}
1501
1502
1503Type* Typer::Visitor::TypeJSLoadMessage(Node* node) { return Type::Any(); }
1504
1505
1506Type* Typer::Visitor::TypeJSStoreMessage(Node* node) {
1507  UNREACHABLE();
1508  return nullptr;
1509}
1510
1511Type* Typer::Visitor::TypeJSLoadModule(Node* node) { return Type::Any(); }
1512
1513Type* Typer::Visitor::TypeJSStoreModule(Node* node) {
1514  UNREACHABLE();
1515  return nullptr;
1516}
1517
1518Type* Typer::Visitor::TypeJSGeneratorStore(Node* node) {
1519  UNREACHABLE();
1520  return nullptr;
1521}
1522
1523Type* Typer::Visitor::TypeJSGeneratorRestoreContinuation(Node* node) {
1524  return Type::SignedSmall();
1525}
1526
1527Type* Typer::Visitor::TypeJSGeneratorRestoreRegister(Node* node) {
1528  return Type::Any();
1529}
1530
1531Type* Typer::Visitor::TypeJSStackCheck(Node* node) { return Type::Any(); }
1532
1533// Simplified operators.
1534
1535Type* Typer::Visitor::TypeBooleanNot(Node* node) { return Type::Boolean(); }
1536
1537Type* Typer::Visitor::TypeNumberEqual(Node* node) { return Type::Boolean(); }
1538
1539Type* Typer::Visitor::TypeNumberLessThan(Node* node) { return Type::Boolean(); }
1540
1541Type* Typer::Visitor::TypeNumberLessThanOrEqual(Node* node) {
1542  return Type::Boolean();
1543}
1544
1545Type* Typer::Visitor::TypeSpeculativeNumberEqual(Node* node) {
1546  return Type::Boolean();
1547}
1548
1549Type* Typer::Visitor::TypeSpeculativeNumberLessThan(Node* node) {
1550  return Type::Boolean();
1551}
1552
1553Type* Typer::Visitor::TypeSpeculativeNumberLessThanOrEqual(Node* node) {
1554  return Type::Boolean();
1555}
1556
1557Type* Typer::Visitor::TypePlainPrimitiveToNumber(Node* node) {
1558  return TypeUnaryOp(node, ToNumber);
1559}
1560
1561Type* Typer::Visitor::TypePlainPrimitiveToWord32(Node* node) {
1562  return Type::Integral32();
1563}
1564
1565Type* Typer::Visitor::TypePlainPrimitiveToFloat64(Node* node) {
1566  return Type::Number();
1567}
1568
1569// static
1570Type* Typer::Visitor::ReferenceEqualTyper(Type* lhs, Type* rhs, Typer* t) {
1571  if (lhs->IsHeapConstant() && rhs->Is(lhs)) {
1572    return t->singleton_true_;
1573  }
1574  return Type::Boolean();
1575}
1576
1577
1578Type* Typer::Visitor::TypeReferenceEqual(Node* node) {
1579  return TypeBinaryOp(node, ReferenceEqualTyper);
1580}
1581
1582Type* Typer::Visitor::TypeStringEqual(Node* node) { return Type::Boolean(); }
1583
1584Type* Typer::Visitor::TypeStringLessThan(Node* node) { return Type::Boolean(); }
1585
1586Type* Typer::Visitor::TypeStringLessThanOrEqual(Node* node) {
1587  return Type::Boolean();
1588}
1589
1590Type* Typer::Visitor::StringFromCharCodeTyper(Type* type, Typer* t) {
1591  return Type::String();
1592}
1593
1594Type* Typer::Visitor::StringFromCodePointTyper(Type* type, Typer* t) {
1595  return Type::String();
1596}
1597
1598Type* Typer::Visitor::TypeStringCharCodeAt(Node* node) {
1599  return typer_->cache_.kUint16;
1600}
1601
1602Type* Typer::Visitor::TypeStringFromCharCode(Node* node) {
1603  return TypeUnaryOp(node, StringFromCharCodeTyper);
1604}
1605
1606Type* Typer::Visitor::TypeStringFromCodePoint(Node* node) {
1607  return TypeUnaryOp(node, StringFromCodePointTyper);
1608}
1609
1610Type* Typer::Visitor::TypeCheckBounds(Node* node) {
1611  Type* index = Operand(node, 0);
1612  Type* length = Operand(node, 1);
1613  index = Type::Intersect(index, Type::Integral32(), zone());
1614  if (!index->IsInhabited() || !length->IsInhabited()) return Type::None();
1615  double min = std::max(index->Min(), 0.0);
1616  double max = std::min(index->Max(), length->Max() - 1);
1617  if (max < min) return Type::None();
1618  return Type::Range(min, max, zone());
1619}
1620
1621Type* Typer::Visitor::TypeCheckHeapObject(Node* node) {
1622  Type* type = Operand(node, 0);
1623  return type;
1624}
1625
1626Type* Typer::Visitor::TypeCheckIf(Node* node) {
1627  UNREACHABLE();
1628  return nullptr;
1629}
1630
1631Type* Typer::Visitor::TypeCheckMaps(Node* node) {
1632  UNREACHABLE();
1633  return nullptr;
1634}
1635
1636Type* Typer::Visitor::TypeCheckNumber(Node* node) {
1637  Type* arg = Operand(node, 0);
1638  return Type::Intersect(arg, Type::Number(), zone());
1639}
1640
1641Type* Typer::Visitor::TypeCheckSmi(Node* node) {
1642  Type* arg = Operand(node, 0);
1643  return Type::Intersect(arg, Type::SignedSmall(), zone());
1644}
1645
1646Type* Typer::Visitor::TypeCheckString(Node* node) {
1647  Type* arg = Operand(node, 0);
1648  return Type::Intersect(arg, Type::String(), zone());
1649}
1650
1651Type* Typer::Visitor::TypeCheckFloat64Hole(Node* node) {
1652  Type* type = Operand(node, 0);
1653  return type;
1654}
1655
1656Type* Typer::Visitor::TypeCheckTaggedHole(Node* node) {
1657  Type* type = Operand(node, 0);
1658  type = Type::Intersect(type, Type::NonInternal(), zone());
1659  return type;
1660}
1661
1662Type* Typer::Visitor::TypeConvertTaggedHoleToUndefined(Node* node) {
1663  Type* type = Operand(node, 0);
1664  if (type->Maybe(Type::Hole())) {
1665    // Turn "the hole" into undefined.
1666    type = Type::Intersect(type, Type::NonInternal(), zone());
1667    type = Type::Union(type, Type::Undefined(), zone());
1668  }
1669  return type;
1670}
1671
1672Type* Typer::Visitor::TypeAllocate(Node* node) { return Type::Any(); }
1673
1674Type* Typer::Visitor::TypeLoadField(Node* node) {
1675  return FieldAccessOf(node->op()).type;
1676}
1677
1678Type* Typer::Visitor::TypeLoadBuffer(Node* node) {
1679  switch (BufferAccessOf(node->op()).external_array_type()) {
1680#define TYPED_ARRAY_CASE(ElemType, type, TYPE, ctype, size) \
1681  case kExternal##ElemType##Array:                          \
1682    return Type::Union(typer_->cache_.k##ElemType, Type::Undefined(), zone());
1683    TYPED_ARRAYS(TYPED_ARRAY_CASE)
1684#undef TYPED_ARRAY_CASE
1685  }
1686  UNREACHABLE();
1687  return nullptr;
1688}
1689
1690
1691Type* Typer::Visitor::TypeLoadElement(Node* node) {
1692  return ElementAccessOf(node->op()).type;
1693}
1694
1695Type* Typer::Visitor::TypeLoadTypedElement(Node* node) {
1696  switch (ExternalArrayTypeOf(node->op())) {
1697#define TYPED_ARRAY_CASE(ElemType, type, TYPE, ctype, size) \
1698  case kExternal##ElemType##Array:                          \
1699    return typer_->cache_.k##ElemType;
1700    TYPED_ARRAYS(TYPED_ARRAY_CASE)
1701#undef TYPED_ARRAY_CASE
1702  }
1703  UNREACHABLE();
1704  return nullptr;
1705}
1706
1707Type* Typer::Visitor::TypeStoreField(Node* node) {
1708  UNREACHABLE();
1709  return nullptr;
1710}
1711
1712
1713Type* Typer::Visitor::TypeStoreBuffer(Node* node) {
1714  UNREACHABLE();
1715  return nullptr;
1716}
1717
1718
1719Type* Typer::Visitor::TypeStoreElement(Node* node) {
1720  UNREACHABLE();
1721  return nullptr;
1722}
1723
1724Type* Typer::Visitor::TypeStoreTypedElement(Node* node) {
1725  UNREACHABLE();
1726  return nullptr;
1727}
1728
1729Type* Typer::Visitor::TypeObjectIsCallable(Node* node) {
1730  return TypeUnaryOp(node, ObjectIsCallable);
1731}
1732
1733Type* Typer::Visitor::TypeObjectIsNumber(Node* node) {
1734  return TypeUnaryOp(node, ObjectIsNumber);
1735}
1736
1737
1738Type* Typer::Visitor::TypeObjectIsReceiver(Node* node) {
1739  return TypeUnaryOp(node, ObjectIsReceiver);
1740}
1741
1742
1743Type* Typer::Visitor::TypeObjectIsSmi(Node* node) {
1744  return TypeUnaryOp(node, ObjectIsSmi);
1745}
1746
1747Type* Typer::Visitor::TypeObjectIsString(Node* node) {
1748  return TypeUnaryOp(node, ObjectIsString);
1749}
1750
1751Type* Typer::Visitor::TypeObjectIsUndetectable(Node* node) {
1752  return TypeUnaryOp(node, ObjectIsUndetectable);
1753}
1754
1755Type* Typer::Visitor::TypeArrayBufferWasNeutered(Node* node) {
1756  return Type::Boolean();
1757}
1758
1759// Heap constants.
1760
1761Type* Typer::Visitor::TypeConstant(Handle<Object> value) {
1762  if (Type::IsInteger(*value)) {
1763    return Type::Range(value->Number(), value->Number(), zone());
1764  }
1765  return Type::NewConstant(value, zone());
1766}
1767
1768}  // namespace compiler
1769}  // namespace internal
1770}  // namespace v8
1771